Lattice algorithm 2026-11-05
In the geometry of numbers, a lattice algorithm works with a Euclidean lattice, usually specified by linearly independent vectors whose integer linear combinations form
The basis of a Euclidean lattice is not unique. For example, and generate the same Euclidean lattice as and : replace the second vector by itself minus 100 times the first. This integer linear combination is reversible, so it changes the representation without changing the set of Euclidean lattice points.
Lattice reduction seeks a more useful basis of a Euclidean lattice, with shorter and less nearly dependent vectors. The Lenstra-Lenstra-Lovász lattice basis reduction algorithm combines integer basis changes with Gram-Schmidt orthogonalization and comparisons controlling the quality of the result. It is a polynomial-time example, but it does not generally return an exactly shortest vector.[ref] Better bases make geometric searches and lattice-based cryptography analysis more practical. The geometry and the sizes of the integer coordinates both matter: a small number of arithmetic steps need not imply a small bit complexity.
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.