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.