2009/01/01 by Phong Q. Nguyễn, Damien Stehlé · 1 citation
Computer Science · Mathematics · #Cryptography and Data Security #Cryptography and Residue Arithmetic #Complexity and Algorithms in Graphs #Mathematics #Combinatorics #Lattice reduction #Integer (computer science) #Euclidean algorithm #Binary logarithm #Orthogonalization #Dimension (graph theory) #Hermite polynomials #Algorithm #Discrete mathematics #Mathematical analysis
paper · doi:10.1137/070705702
openalex publication_date 2009/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Lenstra–Lenstra–Lovász lattice basis reduction algorithm (called LLL or \rm L3) is a fundamental tool in computational number theory and theoretical computer science, which can be viewed as an efficient algorithmic version of Hermite's inequality on Hermite's constant. Given an integer d-dimensional lattice basis with vectors of Euclidean norm less than B in an n-dimensional space, the \rm L3 algorithm outputs a reduced basis in O(d3n \rm log B\cdotM(d \rm log B)) bit operations, where M(k) denotes the time required to multiply k-bit integers. This worst-case complexity is problematic for applications where d or/and \rm log B are often large. As a result, the original \rm L3 algorithm is almost never used in practice, except in tiny dimension. Instead, one applies floating-point variants where the long-integer arithmetic required by Gram–Schmidt orthogonalization is replaced by floating-point arithmetic. Unfortunately, this is known to be unstable in the worst case: the usual floating-point \rm L3 algorithm is not even guaranteed to terminate, and the output basis may not be \rm L3-reduced at all. In this article, we introduce the \rm L2 algorithm, a new and natural floating-point variant of the \rm L3 algorithm which provably outputs \rm L3-reduced bases in polynomial time O(d2n(d+\rm log B) \rm log B\cdotM(d)). This is the first \rm L3 algorithm whose running time (without fast integer arithmetic) provably grows only quadratically with respect to \rm log B, like Euclid's gcd algorithm and Lagrange's two-dimensional algorithm.