Introduction to Cryptography with Coding Theory, 3rd Edition

23.2 Lattice Reduction

23.2.1 Two-Dimensional Lattices

Let $v_1\text{,}{v}_2$ form the basis of a two-dimensional lattice. Our first goal is to replace this basis with what will be called a reduced basis.

If $\parallel v_1\parallel >\parallel v_2\parallel$, then swap $v_1$ and $v_2$, so we may assume that $\parallel v_1\parallel \le \parallel v_2\parallel$. Ideally, we would like to replace $v_2$ with a vector $v_2^{\ast }$ perpendicular to $v_1$. As in the Gram-Schmidt process from linear algebra, the vector

$$\begin{array}{r}{v}_2^{\ast }=v_2-{\displaystyle \frac{v_1\cdot v_2}{v_1\cdot v_1}}{v}_1\end{array}$$(23.1)

is perpendicular to $v_1$. But this vector might not lie in the lattice. Instead, let $t$ be the closest integer to $(v_1\cdot v_2)/(v_1\cdot v_1)$ (for definiteness, take $0$ to be the closest integer to $\pm \frac{1}{2}$, and $\pm 1$ to be closest to $\pm \frac{3}{2}$, etc.). Then we replace the basis $\{v_1\text{,}{v}_2\}$ with the basis

$$\{v_1\text{,}{v}_2-t{v}_1\}\text{.}$$

We then repeat the process with this new ...