 Lenstra–Lenstra–Lovász lattice basis reduction algorithm

For an integer basis of a Euclidean lattice, the algorithm uses integer column operations and swaps to obtain a size-reduced basis with Gram-Schmidt coefficients $|{\mu }_{ij}|\le 1/2$ and the condition $\delta \Vert b_i^{\ast }{\Vert }^2\le \Vert b_{i+1}^{\ast }{\Vert }^2+{\mu }_{i+1,i}^2\Vert b_i^{\ast }{\Vert }^2$. It preserves the lattice and exposes short vectors and near-relations. It is useful for improving proven Diophantine bounds by encoding scaled logarithms in integer coordinates. A certified lower bound for every nonzero lattice vector is ${\min }_i\Vert b_i^{\ast }\Vert$: in a nonzero integer linear combination, project onto the last nonzero Gram-Schmidt direction. Better-reduced bases improve this lower bound. Rounding and logarithm errors must still be bounded before turning it into a certified lower bound for a logarithmic form.

The Lenstra–Lenstra–Lovász (LLL) algorithm is a polynomial-time algorithm for lattice basis reduction. It is named after its creators Arjen K. Lenstra, Hendrik W. Lenstra Jr., and László Lovász, who introduced it in 1982. The algorithm is significant in computational number theory and has applications in areas such as cryptography, coding theory, integer programming, and combinatorial optimization. ### Key Concepts 1.