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.
At termination, and . For the basis , subtracting twice the first vector gives , which is shorter and becomes the first vector. The method exploits the nearest-integer projection rather than a continuous orthogonal projection that might leave the lattice.

Articles by others on the same topic (1)

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.