Lenstra-Lenstra-Lovasz algorithm

A lattice reduction algorithm, named after discoverers Lenstra, Lenstra, and Lovasz, 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. 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.

Ferguson-Forcade algorithm | HJLS algorithm | integer relation | lattice reduction | PSLQ algorithm | PSOS algorithm