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.
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.