## What LLL really means

The following theorem is not too difficult to prove.

Let be an LLL reduced basis for a lattice . Let denote the absolute value of the determinant of any matrix whose rows are basis for . Then the vectors are nearly orthogonal'' and short'' in the sense of the following theorem:

Theorem 2.5.3   We have
1. ,
2. For , we have

3. The vector is very short in the sense that

and for every nonzero we have

4. More generally, for any linearly independent , we have

for .

Perhaps the most amazing thing about the idea of an LLL reduced basis is that there is an algorithm (in fact many) that given a basis for a lattice produce an LLL reduced basis for , and do so quickly, i.e., in polynomial time in the number of digits of the input. The current optimal implementation (and practically optimal algorithms) for computing LLL reduced basis are due to Damien Stehle, and are included standard in Magma in Sage. Stehle's code is amazing - it can LLL reduce a random lattice in for in a matter of minutes!!

sage: A = random_matrix(ZZ, 200)
sage: t = cputime()
sage: B = A.LLL()
sage: cputime(t)     # random output
3.0494159999999999


There is even a very fast variant of Stehle's implementation that computes a basis for that is very likely LLL reduced but may in rare cases fail to be LLL reduced.

sage: t = cputime()
sage: B = A.LLL(algorithm="fpLLL:fast")   # not tested
sage: cputime(t)      # random output
0.96842699999999837


William Stein 2012-09-24