= Lagrange lattice reduction
{c}
= Gauss/Lagrange reduction
{synonym}
For two independent <basis vectors> $b_1,b_2$ of a <Euclidean lattice>, arrange $\|b_1\|\leq\|b_2\|$, set $q$ to a nearest <integer> to $\langle b_1,b_2\rangle/\|b_1\|^2$, and replace $b_2$ by $b_2-qb_1$. Swap and repeat if the second <vector> has become shorter. These are invertible integer basis operations, so the <lattice> is preserved.
At termination, $\|b_1\|\leq\|b_2\|$ and $|\langle b_1,b_2\rangle|\leq\|b_1\|^2/2$. For the basis $(2,0),(3,1)$, subtracting twice the first <vector> gives $(-1,1)$, 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.
Back to article page