An LLL Algorithm with Quadratic Complexity

The Lenstra–Lenstra–Lovász lattice basis reduction algorithm (called LLL or L³) 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 L³ algorithm outputs a reduced basis in O(d³n\, log\,B(d\, 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 log\,B are often large. As a result, the original L³ 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 L³ algorithm is not even guaranteed to terminate, and the output basis may not be L³-reduced at all. In this article, we introduce the L² algorithm, a new and natural floating-point variant of the L³ algorithm which provably outputs L³-reduced bases in polynomial time O(d²n(d+ log\,B)\, log\,B(d)). This is the first L³ algorithm whose running time (without fast integer arithmetic) provably grows only quadratically with respect to log\,B, like Euclid's gcd algorithm and Lagrange's two-dimensional algorithm.