LenstraLenstraLovász

Lenstra–Lenstra–Lovász lattice basis reduction algorithm (LLL) is a foundational polynomial-time algorithm for lattice basis reduction. Given a basis for a lattice in R^n, LLL outputs a reduced basis of relatively short and nearly orthogonal vectors. The algorithm was introduced in 1982 by Hendrik W. Lenstra, Arjen Lenstra, and László Lovász. It relies on Gram-Schmidt orthogonalization, periodic size reductions, and the Lovász condition with a parameter δ in (1/4, 1). The produced basis satisfies provable length bounds, and the running time is polynomial in n and the bit-length of the input.

LLL has numerous applications in computational number theory, algebra, and cryptography. It can be used to factor polynomials with rational coefficients by lifting the problem to a lattice, to find short integer relations among real numbers (closely related to the PSLQ algorithm), and to perform lattice-based cryptanalytic tasks. It also underpins methods such as Coppersmith’s technique for finding small roots of polynomials modulo integers, and has been used to attack certain knapsack- or subset-sum–based cryptosystems.

Impact and extensions: LLL changed how researchers address problems involving Diophantine approximation and integer relations, providing a practical, polynomial-time tool with wide-ranging consequences. Several refinements and generalizations exist, including the BKZ family of block-reduce algorithms, which trade some speed for stronger reduction in higher dimensions.