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).
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).
