The Lenstra-Lenstra-Lovasz, or LLL, lattice basis reduction algorithm is a polynomial time lattice reduction algorithm invented by Arjen Lenstra, Hendrik Lenstra and Laszlo Lovasz in 1982. Given a basis with integer coordinates for a lattice, the algorithm computes a reduced basis that is short and nearly orthogonal in polynomial time; its original applications were polynomial time algorithms for factorizing polynomials with rational coefficients, for finding simultaneous rational approximations to real numbers, and for solving the integer linear programming problem in fixed dimensions.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.