= Lattice algorithm
In the <geometry of numbers>, a <lattice algorithm> works with a <Euclidean lattice>, usually specified by <linear independence>[linearly independent] vectors $b_1,\ldots,b_m$ whose <integer linear combinations> form
$$
\Lambda=\left\{\sum_{i=1}^m z_i b_i:z_i\in\mathbb Z\right\}.
$$
The <basis of a Euclidean lattice> is not unique. For example, $(1,0)$ and $(100,1)$ generate the same <Euclidean lattice> as $(1,0)$ and $(0,1)$: 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>[polynomial-time] example, but it does not generally return an exactly shortest vector.<Factoring Polynomials with Rational Coefficients by Arjen K. Lenstra and others>[Section1, basis reduction]{ref} Better bases make geometric searches and <lattice-based cryptography> analysis more practical. The geometry and the sizes of the <integer>[integer coordinates] both matter: a small number of <arithmetic operation>[arithmetic steps] need not imply a small <bit complexity>.
Back to article page
