Computing Atlas

How Computing Was Built
Sign In
Text size
100%
Theme

Switch Atlas

Algorithm

Lenstra-Lenstra-Lovasz Algorithm

Numerical Algorithm

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.

Connections

Credited To

Arjen K. Lenstra, Pioneers
Source Lenstra-Lenstra-Lovász lattice basis reduction algorithm (Wikipedia)
Laszlo Lovasz, Pioneers
Source Lenstra-Lenstra-Lovász lattice basis reduction algorithm (Wikipedia)

In Field

Algorithms and Complexity Theory, Fields
Source Lenstra-Lenstra-Lovász lattice basis reduction algorithm (Wikipedia)

Invented By

Arjen K. Lenstra, Pioneers
Source Lenstra-Lenstra-Lovász lattice basis reduction algorithm (Wikipedia)
Laszlo Lovasz, Pioneers
Source Lenstra-Lenstra-Lovász lattice basis reduction algorithm (Wikipedia)
Sources
Lenstra-Lenstra-Lovász lattice basis reduction algorithm (Wikipedia)
  • Credited To: Laszlo Lovasz, Lead sentence
    Lenstra-Lenstra-Lovász (LLL) lattice basis reduction algorithm is a polynomial time lattice reduction algorithm invented by Arjen Lenstra, Hendrik Lenstra and László Lovász in 1982. Given a basis \mathbf{B} = \{ \mathbf{b}_1,\mathbf{b}_2, \dots, \mathbf{
  • Credited To: Arjen K. Lenstra, Lead sentence
    Lenstra-Lenstra-Lovász (LLL) lattice basis reduction algorithm is a polynomial time lattice reduction algorithm invented by Arjen Lenstra, Hendrik Lenstra and László Lovász in 1982. Given a basis \mathbf{B} = \{ \mathbf{b}_1,\mathbf{b}_2, \dots, \mathbf{
  • Invented By: Laszlo Lovasz, Lead sentence
    Lenstra-Lenstra-Lovász (LLL) lattice basis reduction algorithm is a polynomial time lattice reduction algorithm invented by Arjen Lenstra, Hendrik Lenstra and László Lovász in 1982. Given a basis \mathbf{B} = \{ \mathbf{b}_1,\mathbf{b}_2, \dots, \mathbf{
  • Invented By: Arjen K. Lenstra, Lead sentence
    Lenstra-Lenstra-Lovász (LLL) lattice basis reduction algorithm is a polynomial time lattice reduction algorithm invented by Arjen Lenstra, Hendrik Lenstra and László Lovász in 1982. Given a basis \mathbf{B} = \{ \mathbf{b}_1,\mathbf{b}_2, \dots, \mathbf{
  • In Field: Algorithms and Complexity Theory, Lead paragraph
View the Source
Comments (0)
No comments yet. Be the first to share a thought.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.