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.
For two independent basis vectors of a Euclidean lattice, arrange , set to a nearest integer to , and replace by . Swap and repeat if the second vector has become shorter. These are invertible integer basis operations, so the lattice is preserved.
Articles by others on the same topic
Lattice reduction is a mathematical technique used primarily in the field of computational number theory and cryptography. It refers to the process of finding a more "compact" basis for a lattice, which is a discrete subgroup of Euclidean space generated by a set of vectors (basis vectors). The aim is to reduce the lengths of the basis vectors and to make them more orthogonal.