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 . M(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 . M(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.

EXPLOR_STEP=$WICRI_ROOT/Wicri/Asie/explor/AustralieFrV1/Data/Main/Merge

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 008111 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 008111 | SxmlIndent | more

{{Explor lien
   |wiki=    Wicri/Asie
   |area=    AustralieFrV1
   |flux=    Main
   |étape=   Merge
   |type=    RBID
   |clé=     Pascal:10-0286974
   |texte=   AN LLL ALGORITHM WITH QUADRATIC COMPLEXITY
}}