= Lenstra-Lenstra-Lovász lattice basis reduction algorithm
{c}
{title2=$\delta=3/4,\quad|\mu_{ij}|\le1/2$}
{wiki=Lenstra–Lenstra–Lovász_lattice_basis_reduction_algorithm}
= LLL algorithm
{c}
{synonym}
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}|\le1/2$ and the condition $\delta\|b_i^*\|^2\le\|b_{i+1}^*\|^2+\mu_{i+1,i}^2\|b_i^*\|^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\|b_i^*\|$: 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>.
Back to article page
