0
$\begingroup$

Given a basis set B (say $m \times n$), denote the lattice by L(B), also given a unit vector $\vec{d} = \frac{1}{\lambda_1}\vec{u}$, say $\vec{u}$ is the unique shortest vector of L(B). In other words, we know the direction of the shortest vector.

The question is: can we solve exact/approx SVP using any of the existing algorithms?

A natural idea of using binary search doesn't seem to work, because say currently, the step is testing some value $\lambda$, then

  • if $\lambda \cdot \vec{d} \in L(B)$, we can be sure that $\lambda_1 \leq \lambda$;
  • however, if $\lambda \cdot \vec{d} \notin L(B)$, then either $\lambda_1 < \lambda$ or $\lambda_1 > \lambda$ is possible.

Any helpful thoughts or pointers will be greatly appreciated.

$\endgroup$

1 Answer 1

1
$\begingroup$

Express $\vec{d}$ as a linear combination of the basis $B$, this can be done efficiently by taking projections of $\vec{d}$ along each of the basis vectors. Thus we will have $\vec{d} = B \vec{x}$ for some $\vec{x} \in \mathbb{R}^n$. Now find the smallest $\lambda \in \mathbb{R}$ such that $\lambda \vec{x} \in \mathbb{Z}^n$. Also it is guaranteed that there exists such a $\lambda$.

Suppose $\lambda\vec{x}=(z_1,\ldots,z_n)\in\mathbb{Z}^n$, then $\lambda z_1^{-1}\vec{x}=(1,z_2z_1^{-1},\ldots, z_nz_1^{-1})\in\mathbb{Q}^n$. Thus if $\vec{x} = (x_1, \ldots, x_n)$, then $x_1^{-1}\vec{x}=(1,r_2,\ldots, r_n)$ where $r_i=z_iz_1^{-1}$. Now if the rational $r_i$ is written as $p_i/q_i$ such that $\mathrm{gcd}(p_i,q_i)=1$, then we get our required $\lambda$ to be $\mathrm{lcm}(q_2,\ldots, q_n)\cdot x_1^{-1}$.

Thus given the direction of the shortest vector, SVP can be solved efficiently.

$\endgroup$
5
  • $\begingroup$ Yes, you are right. So my question is basically about how to find such value efficiently. $\endgroup$
    – n00d1es
    Jan 8, 2023 at 14:39
  • $\begingroup$ I just edited my answer. $\endgroup$
    – QED
    Jan 8, 2023 at 15:53
  • $\begingroup$ Yeah, I can see that if the coefficients are rational numbers, this works. But in general, can we assume that? or the poly-size input (which includes the set of basis) already implies that? $\endgroup$
    – n00d1es
    Jan 9, 2023 at 16:04
  • $\begingroup$ The coefficients has to be rational after multiplying by $x_1^{-1}$. Can you see that? $\endgroup$
    – QED
    Jan 9, 2023 at 16:29
  • $\begingroup$ This is because if the first coordinate of $c_1\vec{x}$ is same as the first coordinate of $c_2\vec{x}$, then $c_1=c_2$, and in particular, $c_1 x_i = c_2 x_i$ for all $i$, i.e., every coordinate is same. Hence $r_i = x_1^{-1} x_i = \lambda z_1^{-1} x_i = z_i z_1^{-1}$, which has to be rational, even if $x_i$ is not. $\endgroup$
    – QED
    Jan 10, 2023 at 3:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .