Question

Let $v_1,\ldots,v_n$ be linearly independent vector in $\mathbb{R}^n$, and let $\Lambda=\oplus_i^n \mathbb{Z}v_i$. The question is, given a vector $w$ find the element $v$ of the lattice $\Lambda$ closest to $w$. It is assumed that an inner product structure has been imposed on $\mathbb{R}^n$. This is called the CVP (for closest vector problem).

I've found various algorithms that can find the closest vector, but is there a particular algorithm that is especially simple to understand and to program? I want to test a few low dimensional examples, and easy to write computer code would be preferable.

Any suggestion?

Answer 1

A nice rahter-simple option would be Babai's Nearest Plane Algorithm. This is an approximation algorithm which outputs a vector of the lattice which is "close" the given target $w$. The accuracy of the approximation depends on the rank $n$ of the lattice. The good things are: the algorithm runs in polynomial-time and it is fairly easy to implement.

Input: Basis $B\in\mathbb{Z}^{m\times n}, w\in\mathbb{Z}^{m}$

Output: A vector $x\in \mathcal{L}(B)$ such that $\lVert x - w\rVert \leq 2^{\frac{n}{2}} \:\text{dist}(w,\mathcal{L}(B))$

1. Run $\delta$-LLL on $B$ with $\delta=3/4$.

2. $b \leftarrow w$

   for $j = n$ to $1$ do

   $\qquad b=b-c_j b_j$ where $c_j = \lceil \langle b, \tilde{b}_j \rangle / \langle \tilde{b}_j, \tilde{b}_j \rangle\rfloor$

   Output $x:=w-b$

Above, $\delta$-LLL denotes the Lenstra-Lenstra-Lovasz algorithm, used as a subroutine to obtain a $\delta$-LLL Reduced Basis $\lbrace b_1,\ldots,b_n \rbrace$ of your original basis $\lbrace v_j \rbrace$. The vectors $\lbrace \tilde{b}_j \rbrace$ are the Gram-Schmidt orthogonalization of the LLL basis.

It seems that this algorithm is normally the first to be taught in university courses. I read these algorithms and definitions in Oded Regev's course about Lattices in Computer Science.

For exacts algorithms, this short review might be helpful. Alternatively, this text is more technical but rather complete.