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