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:

- ,
- For
, we have
- The vector is very short in the sense that
- More generally, for any linearly independent
, we have

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