Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

23.2 Lattice Reduction

23.2.1 Two-Dimensional Lattices

Let $v_{1}, v_{2}$ $v_{1}, 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 $∥ v_{1} ∥ > ∥ v_{2} ∥$ $∥ v_{1} ∥ > ∥ v_{2} ∥$ , then swap $v_{1}$ $v_{1}$ and $v_{2}$ $v_{2}$ , so we may assume that $∥ v_{1} ∥ \leq ∥ v_{2} ∥$ $∥ v_{1} ∥ \leq ∥ v_{2} ∥$ . Ideally, we would like to replace $v_{2}$ $v_{2}$ with a vector $v_{2}^{*}$ $v_{2}^{*}$ perpendicular to $v_{1}$ $v_{1}$ . As in the Gram-Schmidt process from linear algebra, the vector

\begin{array}{rcl} v_{2}^{*} = v_{2} - \frac{v_{1} \cdot v_{2}}{v_{1} \cdot v_{1}} v_{1} \end{array}

$\begin{array}{rcl} v_{2}^{*} = v_{2} - \frac{v_{1} \cdot v_{2}}{v_{1} \cdot v_{1}} v_{1} \end{array}$ (23.1)

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

{v_{1}, v_{2} - t v_{1}} .

${v_{1}, v_{2} - t v_{1}} .$

We then repeat the process with this new basis.

We say that the basis ${v_{1}, v_{2}}$ ${v_{1}, v_{2}}$ is reduced if

∥ v_{1} ∥ \leq ∥ v_{2} ∥ and - \frac{1}{2} \leq \frac{v_{1} \cdot v_{2}}{v_{1} \cdot v_{1}} \leq \frac{1}{2} .

$∥ v_{1} ∥ \leq ∥ v_{2} ∥ and - \frac{1}{2} \leq \frac{v_{1} \cdot v_{2}}{v_{1} \cdot v_{1}} \leq \frac{1}{2} .$

The above reduction process stops exactly when we obtain a reduced basis, since this means that $t = 0$ $t = 0$ .

23.2-1 Full Alternative Text

An illustration shows a non-reduced basis.

23.2-2 Full Alternative Text

In the figures, the first basis is reduced because $v_{2}$ $v_{2}$ is longer than $v_{1}$ $v_{1}$ and the projection of $v_{2}$ $v_{2}$ onto $v_{1}$ $v_{1}$ is less than half the length of $v_{1}$ $v_{1}$ . The second basis is nonreduced because the projection of $v_{2}$ $v_{2}$ onto $v_{1}$ $v_{1}$ is too long. It is easy to see that a basis ${v_{1}, v_{2}}$ ${v_{1}, v_{2}}$ is reduced when $v_{2}$ $v_{2}$ is at least as long as $v_{1}$ $v_{1}$ and $v_{2}$ $v_{2}$ lies within the dotted lines of the figures.

Example

Let’s start with $v_{1} = (31, 59)$ $v_{1} = (31, 59)$ and $v_{2} = (37, 70)$ $v_{2} = (37, 70)$ . We have $∥ v_{1} ∥ < ∥ v_{2} ∥$ $∥ v_{1} ∥ < ∥ v_{2} ∥$ , so we do not swap the two vectors. Since

\frac{v_{1} \cdot v_{2}}{v_{1} \cdot v_{1}} = \frac{5277}{4442},

$\frac{v_{1} \cdot v_{2}}{v_{1} \cdot v_{1}} = \frac{5277}{4442},$

we take $t = 1$ $t = 1$ . The new basis is

\begin{matrix} v_{1}^{^{'}} = v_{1} = (31, 59) & and & v_{2}^{^{'}} = v_{2} - v_{1} = (6, 11) . \end{matrix}

$\begin{matrix} v_{1}^{^{'}} = v_{1} = (31, 59) & and & v_{2}^{^{'}} = v_{2} - v_{1} = (6, 11) . \end{matrix}$

Swap $v_{1}^{^{'}}$ $v_{1}^{^{'}}$ and $v_{2}^{^{'}}$ $v_{2}^{^{'}}$ and rename the vectors to obtain a basis

\begin{matrix} v_{1}^{^{''}} = (6, 11) & and & v_{2}^{^{''}} = (31, 59) . \end{matrix}

$\begin{matrix} v_{1}^{^{''}} = (6, 11) & and & v_{2}^{^{''}} = (31, 59) . \end{matrix}$

We have

\frac{v_{1}^{^{''}} ​ \cdot ​ v_{2}^{^{''}}}{v_{1}^{^{''}} \cdot ​ v_{1}^{^{''}}} = \frac{835}{157},

$\frac{v_{1}^{^{''}} \cdot v_{2}^{^{''}}}{v_{1}^{^{''}} \cdot v_{1}^{^{''}}} = \frac{835}{157},$

so we take $t = 5$ $t = 5$ . This yields vectors

\begin{matrix} (6, 11) & and & (1, 4) = (31, 59) - 5 ​ \cdot ​ (6, 11) . \end{matrix}

$\begin{matrix} (6, 11) & and & (1, 4) = (31, 59) - 5 \cdot (6, 11) . \end{matrix}$

Swap these and name them $v_{1}^{(3)} = (1, 4)$ $v_{1}^{(3)} = (1, 4)$ and $v_{2}^{(3)} = (6, 11)$ $v_{2}^{(3)} = (6, 11)$ . We have

\frac{v_{1}^{(3)} \cdot v_{2}^{(3)}}{v_{1}^{(3)} \cdot v_{1}^{(3)}} = \frac{50}{17},

$\frac{v_{1}^{(3)} \cdot v_{2}^{(3)}}{v_{1}^{(3)} \cdot v_{1}^{(3)}} = \frac{50}{17},$

so $t = 3$ $t = 3$ . This yields, after a swap,

\begin{matrix} v_{1}^{r} = (3, - 1) & and & v_{2}^{r} = (1, 4) . \end{matrix}

$\begin{matrix} v_{1}^{r} = (3, - 1) & and & v_{2}^{r} = (1, 4) . \end{matrix}$

Since $∥ v_{1}^{r} ∥ \leq ∥ v_{2}^{r} ∥$ $∥ v_{1}^{r} ∥ \leq ∥ v_{2}^{r} ∥$ and

\frac{v_{1}^{r} \cdot v_{2}^{r}}{v_{1}^{r} \cdot v_{1}^{r}} = - \frac{1}{10},

$\frac{v_{1}^{r} \cdot v_{2}^{r}}{v_{1}^{r} \cdot v_{1}^{r}} = - \frac{1}{10},$

the basis ${v_{1}^{r}, v_{2}^{r}}$ ${v_{1}^{r}, v_{2}^{r}}$ is reduced.

A natural question is whether this process always produces a reduced basis. The answer is yes, as we prove in the following theorem. Moreover, the first vector in the reduced basis is a shortest vector for the lattice.

We summarize the discussion in the following.

Theorem

Let ${v_{1}, v_{2}}$ ${v_{1}, v_{2}}$ be a basis for a two-dimensional lattice in $R^{2}$ $R^{2}$ . Perform the following algorithm:

If $∥ v_{1} ∥ > ∥ v_{2} ∥$ $∥ v_{1} ∥ > ∥ v_{2} ∥$ , swap $v_{1}$ $v_{1}$ and $v_{2}$ $v_{2}$ so that $∥ v_{1} ∥ \leq ∥ v_{2} ∥$ $∥ v_{1} ∥ \leq ∥ v_{2} ∥$ .
Let $t$ $t$ be the closest integer to $(v_{1} \cdot v_{2}) / (v_{1} \cdot v_{1})$ $(v_{1} \cdot v_{2}) / (v_{1} \cdot v_{1})$ .
If $t = 0$ $t = 0$ , stop. If $t \neq 0$ $t \neq 0$ , replace $v_{2}$ $v_{2}$ with $v_{2} - t v_{1}$ $v_{2} - t v_{1}$ and return to step 1.

The algorithm stops in finite time and yields a reduced basis ${v_{1}^{r}, v_{2}^{r}}$ ${v_{1}^{r}, v_{2}^{r}}$ of the lattice. The vector $v_{1}^{r}$ $v_{1}^{r}$ is a shortest nonzero vector for the lattice.

Proof

First we prove that the algorithm eventually stops. As in Equation 23.1, let $μ = (v_{1} \cdot v_{2}) / (v_{1} \cdot v_{1})$ $μ = (v_{1} \cdot v_{2}) / (v_{1} \cdot v_{1})$ and let $v_{2}^{*} = v_{2} - μ v_{1}$ $v_{2}^{*} = v_{2} - μ v_{1}$ . Then

v_{2} - t v_{1} = v_{2}^{*} + (μ - t) v_{1} .

$v_{2} - t v_{1} = v_{2}^{*} + (μ - t) v_{1} .$

Since $v_{1}$ $v_{1}$ and $v_{2}^{*}$ $v_{2}^{*}$ are orthogonal, the Pythagorean theorem yields

∥ v_{2} - t v_{1} ∥^{2} = ∥ v_{2}^{*} ∥^{2} + ∥ (μ - t) v_{1} ∥^{2} = ∥ v_{2}^{*} ∥^{2} + (μ - t)^{2} ∥ v_{1} ∥^{2} .

$∥ v_{2} - t v_{1} ∥^{2} = ∥ v_{2}^{*} ∥^{2} + ∥ (μ - t) v_{1} ∥^{2} = ∥ v_{2}^{*} ∥^{2} + (μ - t)^{2} ∥ v_{1} ∥^{2} .$

Also, since $v_{2} = v_{2}^{*} + μ v_{1}$ $v_{2} = v_{2}^{*} + μ v_{1}$ , and again since $v_{1}$ $v_{1}$ and $v_{2}^{*}$ $v_{2}^{*}$ are orthogonal,

∥ v_{2} ∥^{2} = ∥ v_{2}^{*} ∥^{2} + μ^{2} ∥ v_{1} ∥^{2} .

$∥ v_{2} ∥^{2} = ∥ v_{2}^{*} ∥^{2} + μ^{2} ∥ v_{1} ∥^{2} .$

Note that if $- 1 / 2 \leq μ \leq 1 / 2$ $- 1 / 2 \leq μ \leq 1 / 2$ then $t = 0$ $t = 0$ and $μ - t = μ$ $μ - t = μ$ . Otherwise, $| μ - t | \leq 1 / 2 t | μ |$ $| μ - t | \leq 1 / 2 t | μ |$ . Therefore, if $t \neq 0$ $t \neq 0$ , we have $| μ - t | < | μ |$ $| μ - t | < | μ |$ , which implies that

∥ v_{2} - t v_{1} ∥^{2} = ∥ v_{2}^{*} ∥^{2} + (μ - t)^{2} ∥ v_{1} ∥^{2} < ∥ v_{2}^{*} ∥^{2} + μ^{2} ∥ v_{1} ∥^{2} = ∥ v_{2} ∥^{2} .

$∥ v_{2} - t v_{1} ∥^{2} = ∥ v_{2}^{*} ∥^{2} + (μ - t)^{2} ∥ v_{1} ∥^{2} < ∥ v_{2}^{*} ∥^{2} + μ^{2} ∥ v_{1} ∥^{2} = ∥ v_{2} ∥^{2} .$

Therefore, if the process continues forever without yielding a reduced basis, then the lengths of the vectors decrease indefinitely. However, there are only finitely many vectors in the lattice that are shorter than the original basis vector $v_{2}$ $v_{2}$ . Therefore, the lengths cannot decrease forever, and a reduced basis must be found eventually.

To prove that the vector $v_{1}$ $v_{1}$ in a reduced basis is a shortest nonzero vector for the lattice, let $a v_{1} + b v_{2}$ $a v_{1} + b v_{2}$ be any nonzero vector in the lattice, where $a$ $a$ and $b$ $b$ are integers. Then

∥ a v_{1} + b v_{2} ∥^{2} = (a v_{1} + b v_{2}) \cdot (a v_{1} + b v_{2}) = a^{2} ∥ v_{1} ∥^{2} + b^{2} ∥ v_{2} ∥^{2} + 2 a b v_{1} \cdot v_{2} .

$∥ a v_{1} + b v_{2} ∥^{2} = (a v_{1} + b v_{2}) \cdot (a v_{1} + b v_{2}) = a^{2} ∥ v_{1} ∥^{2} + b^{2} ∥ v_{2} ∥^{2} + 2 a b v_{1} \cdot v_{2} .$

Because ${v_{1}, v_{2}}$ ${v_{1}, v_{2}}$ is reduced,

- \frac{1}{2} v_{1} \cdot v_{1} \leq v_{1} \cdot v_{2} \leq \frac{1}{2} v_{1} \cdot v_{1},

$- \frac{1}{2} v_{1} \cdot v_{1} \leq v_{1} \cdot v_{2} \leq \frac{1}{2} v_{1} \cdot v_{1},$

which implies that $2 a b v_{1} \cdot v_{2} \geq - | a b | ∥ v_{1} ∥^{2}$ $2 a b v_{1} \cdot v_{2} \geq - | a b | ∥ v_{1} ∥^{2}$ . Therefore,

\begin{array}{l} {‖ a v_{1} + b v_{2} ‖}^{2} & = & (a v_{1} + b v_{2}) \cdot (a v_{1} + b v_{2}) \\ = & a^{2} {‖ v_{1} ‖}^{2} + 2 a b v_{1} \cdot v_{2} + b^{2} {‖ v_{2} ‖}^{2} \\ \geq & a^{2} {‖ v_{1} ‖}^{2} - | a b | {‖ v_{1} ‖}^{2} + b^{2} {‖ v_{2} ‖}^{2} \\ \geq & a^{2} {‖ v_{1} ‖}^{2} - | a b | {‖ v_{1} ‖}^{2} + b^{2} {‖ v_{1} ‖}^{2}, \end{array}

$\begin{array}{l} {‖ a v_{1} + b v_{2} ‖}^{2} & = & (a v_{1} + b v_{2}) \cdot (a v_{1} + b v_{2}) \\ = & a^{2} {‖ v_{1} ‖}^{2} + 2 a b v_{1} \cdot v_{2} + b^{2} {‖ v_{2} ‖}^{2} \\ \geq & a^{2} {‖ v_{1} ‖}^{2} - | a b | {‖ v_{1} ‖}^{2} + b^{2} {‖ v_{2} ‖}^{2} \\ \geq & a^{2} {‖ v_{1} ‖}^{2} - | a b | {‖ v_{1} ‖}^{2} + b^{2} {‖ v_{1} ‖}^{2}, \end{array}$

since $∥ v_{2} ∥^{2} \geq ∥ v_{1} ∥^{2}$ $∥ v_{2} ∥^{2} \geq ∥ v_{1} ∥^{2}$ by assumption. Therefore,

∥ a v_{1} + b v_{2} ∥^{2} \geq (a^{2} - | a b | + b^{2}) ∥ v_{1} ∥^{2} .

$∥ a v_{1} + b v_{2} ∥^{2} \geq (a^{2} - | a b | + b^{2}) ∥ v_{1} ∥^{2} .$

But $a^{2} - | a b | + b^{2}$ $a^{2} - | a b | + b^{2}$ is an integer. Writing it as $(| a | - \frac{1}{2} | b |)^{2} + \frac{1}{4} | b |^{2}$ $(| a | - \frac{1}{2} | b |)^{2} + \frac{1}{4} | b |^{2}$ , we see that it is nonnegative, and it equals 0 if and only if $a = b = 0$ $a = b = 0$ . Since $a v_{1} + b v_{2} \neq 0$ $a v_{1} + b v_{2} \neq 0$ , we must have $a^{2} - | a b | + b^{2} \geq 1$ $a^{2} - | a b | + b^{2} \geq 1$ . Therefore,

∥ a v_{1} + b v_{2} ∥^{2} \geq ∥ v_{1} ∥^{2},

$∥ a v_{1} + b v_{2} ∥^{2} \geq ∥ v_{1} ∥^{2},$

so $v_{1}$ $v_{1}$ is a shortest nonzero vector.

23.2.2 The LLL algorithm

Lattice reduction in dimensions higher than two is much more difficult. One of the most successful algorithms was invented by A. Lenstra, H. Lenstra, and L. Lovász and is called the LLL algorithm. In many problems, a short vector is needed, and it is not necessary that the vector be the shortest. The LLL algorithm takes this approach and looks for short vectors that are almost as short as possible. This modified approach makes the algorithm run very quickly (in what is known as polynomial time). The algorithm performs calculations similar to those in the two-dimensional case, but the steps are more technical, so we omit details, which can be found in [Cohen], for example. The result is the following.

Theorem

Let $L$ $L$ be the $n$ $n$ -dimensional lattice generated by $v_{1}, \dots, v_{n}$ $v_{1}, \dots, v_{n}$ in $R^{n}$ $R^{n}$ . Define the determinant of the lattice to be

D = | \det (v_{1}, ..., v_{n}) | .

$D = | \det (v_{1}, ..., v_{n}) | .$

(This can be shown to be independent of the choice of basis. It is the volume of the parallelepiped spanned by $v_{1}, \dots, v_{n}$ $v_{1}, \dots, v_{n}$ .) Let $λ$ $λ$ be the length of a shortest nonzero vector in $L$ $L$ . The LLL algorithm produces a basis ${b_{1}, \dots, b_{n}}$ ${b_{1}, \dots, b_{n}}$ of $L$ $L$ satisfying

$∥ b_{1} ∥ \leq 2^{(n - 1) / 4} D^{1 / n}$ $∥ b_{1} ∥ \leq 2^{(n - 1) / 4} D^{1 / n}$
$∥ b_{1} ∥ \leq 2^{(n - 1) / 2} λ$ $∥ b_{1} ∥ \leq 2^{(n - 1) / 2} λ$
$∥ b_{1} ∥ ∥ b_{2} ∥ \dots ∥ b_{n} ∥ \leq 2^{n (n - 1) / 4} D$ $∥ b_{1} ∥ ∥ b_{2} ∥ \dots ∥ b_{n} ∥ \leq 2^{n (n - 1) / 4} D$ .

Statement (2) says that $b_{1}$ $b_{1}$ is close to being a shortest vector, at least when the dimension $n$ $n$ is small. Statement (3) says that the new basis vectors are in some sense close to being orthogonal. More precisely, if the vectors $b_{1}, \dots, b_{n}$ $b_{1}, \dots, b_{n}$ are orthogonal, then the volume $D$ $D$ equals the product $∥ b_{1} ∥ ∥ b_{2} ∥ \dots ∥ b_{n} ∥$ $∥ b_{1} ∥ ∥ b_{2} ∥ \dots ∥ b_{n} ∥$ . The fact that this product is no more than $2^{n (n - 1) / 4}$ $2^{n (n - 1) / 4}$ times $D$ $D$ says that the vectors are mostly close to orthogonal.

The running time of the LLL algorithm is less than a constant times $n^{6} {log}^{3} B$ $n^{6} {log}^{3} B$ , where $n$ $n$ is the dimension and $B$ $B$ is a bound on the lengths of the original basis vectors. In practice it is much faster than this bound. This estimate shows that the running time is quite good with respect to the size of the vectors, but potentially not efficient when the dimension gets large.

Example

Let’s consider the lattice generated by (31, 59) and (37, 70), which we considered earlier when looking at the two-dimensional algorithm. The LLL algorithm yields the same result, namely $b_{1} = (3, - 1)$ $b_{1} = (3, - 1)$ and $b_{2} = (1, 4)$ $b_{2} = (1, 4)$ . We have $D = 13$ $D = 13$ and $λ = \sqrt{10}$ $λ = \sqrt{10}$ (given by $∥ (3, - 1) ∥$ $∥ (3, - 1) ∥$ , for example). The statements of the theorem are

$∥ b_{1} ∥ = \sqrt{10} \leq 2^{1 / 4} \sqrt{13}$ $∥ b_{1} ∥ = \sqrt{10} \leq 2^{1 / 4} \sqrt{13}$
$∥ b_{1} ∥ = \sqrt{10} \leq 2^{1 / 2} \sqrt{10}$ $∥ b_{1} ∥ = \sqrt{10} \leq 2^{1 / 2} \sqrt{10}$
$∥ b_{1} ∥ ∥ b_{2} ∥ = \sqrt{10} \sqrt{17} \leq 2^{1 / 2} 13$ $∥ b_{1} ∥ ∥ b_{2} ∥ = \sqrt{10} \sqrt{17} \leq 2^{1 / 2} 13$ .

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 23.2 Lattice Reduction

Create new playlist

Sign In

Sign Up

Table of Contents for
23.2 Lattice Reduction