LLL Algorithm

A lattice reduction algorithm, named after discoverers Lenstra, Lenstra, and Lovasz (1982), that produces a lattice basis of "short" vectors. It was noticed by Lenstra et al. (1982) that the algorithm could be used to obtain factors of univariate polynomials, which amounts to the determination of integer relations. However, this application of the algorithm, which later came to be one of its primary applications, was not stressed in the original paper.

For a complexity analysis of the LLL algorithm, see Storjohann (1996).

The Wolfram Language command LatticeReduce[matrix] implements the LLL algorithm to perform lattice reduction. The Wolfram Language's implementation requires the input to consist of rational numbers, so Rationalize may need to be called first.

More recently, other algorithms such as PSLQ, which can be significant faster than LLL, have been developed for finding integer relations. PSLQ achieves its performance because of clever techniques that allow machine arithmetic to be used at many intermediate steps, whereas LLL must use moderate precision (although generally not as much as the HJLS algorithm).

REFERENCES:

Bailey, D. H.; Borwein, J. M.; Calkin, N. J.; Girgensohn, R.; Luke, D. R.; and Moll, V. H. "Integer Relation Detection." §2.2 in Experimental Mathematics in Action. Wellesley, MA: A K Peters, pp. 29-31, 2007.

Borwein, J. and Bailey, D. Mathematics by Experiment: Plausible Reasoning in the 21st Century. Wellesley, MA: A K Peters, pp. 51-52, 2003.

Borwein, J. M. and Corless, R. M. "Emerging Tools for Experimental Mathematics." Amer. Math. Monthly 106, 899-909, 1999.

Borwein, J. M. and Lisonek, P. "Applications of Integer Relation Algorithms." Disc. Math. 217, 65-82, 2000.

Centre for Experimental & Constructive Mathematics. "Integer Relations." https://www.cecm.sfu.ca/projects/IntegerRelations/.

Cohen, H. A Course in Computational Algebraic Number Theory. New York: Springer-Verlag, 1993.

Lenstra, A. K.; Lenstra, H. W.; and Lovasz, L. "Factoring Polynomials with Rational Coefficients." Math. Ann. 261, 515-534, 1982.

Matthews, K. "Keith Matthews' LLL Page." https://www.numbertheory.org/lll.html.

Mignotte, M. Mathematics for Computer Algebra. New York: Springer-Verlag, 1991.

Storjohann, A. "Faster Algorithms for Integer Lattice Basis Reduction." Technical Report 249. Zurich, Switzerland: Department Informatik, ETH. July 30, 1996.

Zimmerman, P. "LLL Using Exact Multiprecision Arithmetic.." https://www.loria.fr/~zimmerma/free/lll.c.