Lattice reduction Created 2026-10-20 Updated 2026-11-05
Lattice reduction replaces a basis of a Euclidean lattice by another basis of the same lattice with shorter, more nearly orthogonal vectors. If the basis columns form , every replacement with an integer unimodular matrix preserves the lattice. Arbitrary real changes of basis generally do not.
For columns and , subtracting one hundred times the first from the second gives the orthogonal basis . In two dimensions Lagrange lattice reduction repeatedly performs such integer corrections and swaps. In higher dimensions the LLL algorithm gives a useful efficiently computable reduction condition; it does not in general return a globally shortest basis.