Short vectors in lattices
The LLL is an algorithm devised in 1982 to find short vectors in a lattice in polynomial time with respect to the dimension of the lattice. It is a known fact that finding the shortest vector is an NP-hard problem and therefore the only known algorithms to find the shortest vector require exponential time on the dimension of the lattice. The LLL algorithm does not find the shortest vector in a lattice but finds a vector short enough. The seminar paper for this algorithm is:
A. K. Lenstra, H. W. Lenstra, Jr. and L. Lovász, Factoring Polynomials with Rational Coefficients, Math. Ann. 261 (1982)
A clear introduction can be found in the book
J. von zur Gathen and J. Gerhard, Modern computer algebra, Second edition, Cambridge Univ. Press, Cambridge (2003)
The above applet is meant as an educational tool to visualize the inner working of the algorithm. The first matrix represent the actual known basis of the lattice. The second matrix represents the coefficients of the Gram-Schmidt orthogonalization process and the last column represents the square norm of the orthogonalized Gram-Schmidt vectors. The least squared norm is a bound on the squared norm of the smallest vector in the lattice.
By clicking on the vectors of the lattice basis you can select two of them that will be highlighted. The buttons on the bottom have the following purpouse:
Reset zeros all the component of the lattice basis.
Random generates a random lattice whose vector components are all bounded by 16.
The first slide bar indicates the dimension of the lattice.
Reduce will use the top highlighted vector to reduce the component of the bottom highlighted vector in the direction of the Gram vector corresponding to the first vector.
Swap will swap the two highlighted vectors.
Insert will cycle all the vectors between the two highlighted vectors by inserting the< bottom one at the top.
The second slide bar select the sensitivity of the Lovasz algorithm when it comes to swap two of the vectors.
Lovasz will apply the classical LLL algorithm by reducing and swapping the vectors of the lattice basis.
Schnorr will apply a slightly enhanced version of the LLL algorithm that will also take advantage of the insert operation.