The above formula is infinite if and only if *y*1 ≡ *y*2 ≡ 0(mod *p*). If *y*1 ≡ *y*2 ≡ 0(mod *p*), then *y*2 2 − *y*2 1 = (*y*2 − *y*1)(*y*2 + *y*1) will be divided by *pr*+1. Therefore, Equation (6.26) contains 3*x* 2 1 + *a* ≡ 0(mod *p*). It's impossible. Because *x* 3 + *ax* + *b*(mod *p*) has no multiple roots, *x*1 cannot be the roots of *x* 3 + *ax* + *b* and derivative 3*x* 2 under mod *p*. This proves that Formula (6.25) holds under the assumption.

Conversely, if Eq. (6.25) holds, we prove that the denominator of *P*1 + *P*2 and *n* are coprime. Fixed *p*|*n*, if *x*1 ≡ *x*2(mod *p*), from equation (6.4), the denominator of *P*1 + *P*2 and *p* are coprime. Might as well make *x*1 ≡ *x*2(mod *p*), then *y*2 ≡ ±*y*1(mod *p*). Because *P*1 mod *p* + *P*2 mod *p* = 0, we have *y*2 ≡ *y*1 ≡ 0(mod *p*). First assume *P*2 = *P*1, then Equation (6.5) and the fact of *y*1 ≡ 0(mod *p*) prove that the denominator of *P*1 + *P*2 = 2*P*1 and *p* is coprime. Finally, let *P*2 = *P*1, we write *x*2 = *x*1 + *t pr*, (*t*, *p*) = 1, using the congruence of Formula (6.26), there are

$$\frac{y\_2^2 - y\_1^2}{x\_2 - x\_1} \equiv 3x\_1^2 + a(\text{mod } p).$$

Because *p y*2 + *y*1 ≡ 2*y*1(mod *p*), so the denominator of

$$\frac{\mathbf{y}\_2^2 - \mathbf{y}\_1^2}{(\mathbf{y}\_2 + \mathbf{y}\_1)(\mathbf{x}\_2 - \mathbf{x}\_1)} = \frac{\mathbf{y}\_2 - \mathbf{y}\_1}{\mathbf{x}\_2 - \mathbf{x}\_1}$$

cannot be divided by *p*, by (6.4), the denominator of *P*1 + *P*2 cannot be divided by *p*. Since *p*|*n* is arbitrary, we complete the proof of the whole theorem.

Lenstra algorithm.

Let *n* be an odd compound number, we hope to find a nontrivial factor *d* of *n*, *d*|*n*, 1 < *d* < *n*, so there is factorization *n* = *d* · *n d* . Previously, we have introduced the random selection of an elliptic curve *CE* on rational number field Q and a point *P* on *CE* . Lenstra's algorithm hopes to factorize *n* by (*CE* , *P*). There is no doubt that the Lenstra algorithm to be explained below is also a probability algorithm. If (*CE* , *P*) cannot be factorized successfully, as long as the probability of failure is *p* < 1, select another elliptic curve and a point above. If this continues, after randomly and independently selecting *n* elliptic curves, the probability of successful factorization of *n*,

$$P\{n = d \cdot \frac{n}{d}\} \ge 1 - p''(p < 1).$$

When *n* is sufficiently large, the success probability of Lenstra algorithm can be infinitely close to 1. Therefore, the so-called Lenstra algorithm can be simply summarized as an algorithm that factorizes *n* by using any rational elliptic curve (*CE* , *P*), and its failure probability is *p* < 1.

Let (*CE* , *P*) be a given rational elliptic curve, and *B* and *C* be the positive upper bound of selection. Let *k* be divided by some small prime powers, to be exact,

$$k = \prod\_{1 \le l \le B} l^{\alpha l},\tag{6.27}$$

where α*l* is the largest index satisfying *l* α*l* ≤ *C*. Thus α*l* = [log*C* log *l* ].

Next, we calculate *k P*(mod *n*), by (6.4) and (6.5), if *x*2 − *x*1 and 2*y*1 have a rational number whose denominator and *n* are not prime, for example *d* = (*x*2 − *x*1, *n*), 1 < *d* < *n*; Then we have factorization *n* = *d* · *n d* . If *d* = *n*, then re select point *P* on rational elliptic curves *CE* and *CE* . By Theorem 6.2, *d* > 1 appears in these rational numbers *x*2 − *x*1 and *y*1 if and only if there is a *k*1, such that

$$k\_1 \cdot (P \bmod p) = 0, \forall \ p | n.$$

From the selection of equation *k* in (6.27), there is a maximum probability *k*1|*k*, thus

$$k \cdot (P \bmod p) = 0, \forall \ p \vert n.$$

Therefore, in Lenstra algorithm, by calculating the rational point *k P*, there is a great probability that there is a certain *p*, *p*|*n* such that

$$k(P \bmod p) = 0, \, p|n, \,\, \text{is a prime number.}\tag{6.28}$$

By Theorem 6.2, let *P* = (*x*1, *y*1), (*k* − 1)*P* = (*x*2, *y*2), thus *d* = (*x*2 − *x*1, *n*) > 1 or (2*y*1, *n*) = *d* > 1, we obtain the nontrivial factorization of *n*.

From the above Lenstra algorithm, the key problem is to calculate *k* · *P*. Using the continuous doubling method given in Lemma 6.10, we only need to calculate 2*P*, 2(2*P*), 2(4*P*), . . . , 2α2 *P*, 3(2α2 *P*), 3(3 · 2α2 *P*)··· 3α3 2α2 *P*, this continues until ( 1<*l*≤*B l* α*l*)*P*, i.e., *k P*.

For the probability estimation and computational complexity of Lenstra algorithm, see 1986 of reference 6.

#### **Exercise 6**

5. Calculate the order of points on the following rational elliptic curves: (*i*) *P* = (0, 16),*CE* : *y*2 = *x* 3 + 256; (*ii*) *P* = ( 1 2 , 1 2 ),*CE* : *y*2 = *x* 3 + *x* 4 ; (*iii*) *P* = (3, 8),*CE* : *y*2 = *x* 3 − 43*x* + 16; (*i*v) *P* = (0, 0),*CE* : *y*2 + *y* = *x* 3 − *x* 2.

	- (*c*) *y*2 + *y* = *x* 3, when *q* ≡ 2(mod 3).

9. The deterministic algorithm can map the embedding of plaintext units to any F*q*− elliptic curve. Please give the specific algorithm process for the following elliptic curves:

(1) *CE* : *y*2 = *x* 3 − *x*, when *q* ≡ 3(mod 4), (2) *CE* : *y*2 + *y* = *x* 3, when *q* ≡ 2(mod 3).

10. Let *CE* be an elliptic curve on the finite field F*p*, and *Nr* represents the number of midpoint of *CE* in the finite field F*pr* , then (*i*) If *p* > 3, when *r* > 1, *Nr* is not prime.

(*ii*)When *p* = 2, 3, a counterexample is given to show that *Nr* is a prime number.

	- (*i*) *nk* is a prime, if and only if there is an integer *a*, *a*22*k*−1 ≡ −1(mod *nk* ).
	- (*ii*) If *nk* is a prime, then *a* ∈ Z∗ *nk* over 50% has the congruence property of (*i*).
	- (*iii*) When *k* > 1, we can always choose *a* = 3, 5, or *a* = 7.

# **References**

Fulton, W. (1969). *Algebraic curves*. Benjamin.

**Open Access** This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

# **Chapter 7 Lattice-Based Cryptography**

# **7.1 Geometry of Numbers**

Let R*n* be an *n*-dimensional Euclidean space and *x* = (*x*1, *x*2,..., *xn*) ∈ R*n* be an *n*-dimensional vector, *x* can be a row vector or a column vector, depending on the situation. If *x* ∈ Z*n*, then *x* is called a integral point. R*m*×*n* is all *m* × *n*-dimensional matrices on R. *x* = (*x*1, *x*2,..., *xn*) ∈ R*n*, *y* = (*y*1, *y*2,..., *yn*) ∈ R*n*, define the inner product of *x* and *y* as

$$
\langle \mathbf{x}, \mathbf{y} \rangle = \sum\_{i=1}^{n} x\_i \mathbf{y}\_i. \tag{7.1}
$$

The length |*x*| of vector *x* is defined as

$$|\mathbf{x}| = \sqrt{\langle \mathbf{x}, \mathbf{x} \rangle} = \sum\_{i=1}^{n} x\_i^2. \tag{7.2}$$

λ ∈ R, then λ · *x* is defined as

$$
\lambda \ge (\lambda x\_1, \lambda x\_2, \dots, \lambda x\_n). \tag{7.3}
$$

If the inner product *x*, *y* = 0 of two vectors *x* and *y*, *x* and *y* are said to be orthogonal, denote as *x*⊥*y*.

# **Lemma 7.1** *Let x*, *y* ∈ R*n,* λ ∈ R *is any real number, then*

253

*(iv) (Pythagorean theorem) If and only if x*⊥*y, we have*

$$\|\mathbf{x} \pm \mathbf{y}\|^2 = |\mathbf{x}|^2 + |\mathbf{y}|^2.$$

*Proof* (i) and (ii) can be derived directly from the definition. To prove (iii), let *x* = (*x*1, *x*2,..., *xn*), *y* = (*y*1, *y*2,..., *yn*) ∈ R*n*, by Holder inequality: ¨

$$\left|\sum\_{i=1}^n \boldsymbol{\chi}\_i \boldsymbol{\text{y}}\_i\right| \le \left[\left(\sum\_{i=1}^n \boldsymbol{\chi}\_i^2\right)\left(\sum\_{i=1}^n \boldsymbol{\text{y}}\_i^2\right)\right]^{\frac{1}{2}}.$$

So there is

$$\begin{aligned} |\mathbf{x} + \mathbf{y}|^2 &= \sum\_{i=1}^n (\mathbf{x}\_i + \mathbf{y}\_i)^2 = \sum\_{i=1}^n \mathbf{x}\_i^2 + 2\sum\_{i=1}^n \mathbf{x}\_i \mathbf{y}\_i + \sum\_{i=1}^n \mathbf{y}\_i^2 \\ &\le \sum\_{i=1}^n \mathbf{x}\_i^2 + 2\left|\sum\_{i=1}^n \mathbf{x}\_i \mathbf{y}\_i\right| + \sum\_{i=1}^n \mathbf{y}\_i^2 \\ &\le \left(\sqrt{\sum\_{i=1}^n \mathbf{x}\_i^2} + \sqrt{\sum\_{i=1}^n \mathbf{y}\_i^2}\right)^2 = (|\mathbf{x}| + |\mathbf{y}|)^2,\end{aligned}$$

so (iii) holds. Then, by the definition of inner product,

$$
\langle \mathbf{x} \pm \mathbf{y}, \mathbf{x} \pm \mathbf{y} \rangle = \langle \mathbf{x}, \mathbf{x} \rangle \pm 2 \langle \mathbf{x}, \mathbf{y} \rangle + \langle \mathbf{y}, \mathbf{y} \rangle,
$$

if *x*⊥*y*, then

$$\|\mathbf{x} \pm \mathbf{y}\|^2 = |\mathbf{x}|^2 + |\mathbf{y}|^2.$$

Conversely, if *x* is not orthogonal to *y*, then *x*, *y* = 0, thus

$$\|\mathbf{x} \pm \mathbf{y}\|^2 \neq \|\mathbf{x}\|^2 + \|\mathbf{y}\|^2.$$

Lemma 7.1 holds.

From Pythagorean theorem, for orthogonal vector *x*⊥*y*, we have the following conclusion,

$$|\mathbf{x} + \mathbf{y}| = |\mathbf{x} - \mathbf{y}|, \text{ if } \mathbf{x} \perp \mathbf{y}. \tag{7.4}$$

**Definition 7.1** Let *R* ⊂ R*n* be a subset, 0 ∈ *R*, *R* is called a symmetric convex body of R*n*, if

(i) *x* ∈ *R*,⇒ −*x* ∈ *R* (Symmetry);

(ii) Let *x*, *y* ∈ *R*, λ ≥ 0, μ ≥ 0, and λ + μ = 1, then λ*x* + μ*y* ∈ *R* (Convexity).

#### 7.1 Geometry of Numbers 255

The following example is a famous example of a symmetric convex body defined by a set of linear inequalities. Let *A* ∈ R*m*×*n* be an *m* × *n*-order matrix, *c* = (*c*1, *c*2,..., *cn*) ∈ R*n*, and ∀ *ci* ≥ 0, *R*(*A*, *c*) is defined as the set of solutions of *x* = (*x*1, *x*2,..., *xn*) ∈ R*n* defined by the following *m* linear inequalities, let *A* = (*ai j*)*m*×*n*,

$$\left| \sum\_{j=1}^{n} a\_{ij} x\_j \right| \le c\_i, \quad 1 \le i \le m. \tag{7.5}$$

We have

**Lemma 7.2** *For any A* ∈ R*m*×*n, and any positive vector c* = (*c*1, *c*2,..., *cn*) ∈ R*n, then R*(*A*, *c*) *is a symmetric convex body in* R*n.*

*Proof* Obviously zero vector *x* = (0, 0,..., 0) ∈ *R*(*A*, *c*), and if *x* ∈ *R*(*A*, *c*) ⇒ −*x* ∈ *R*(*A*, *c*). So we only prove the convexity of *R*(*A*, *c*). Suppose *x*, *y* ∈ *R*(*A*, *c*), let

$$z = \lambda x + \mu y, \lambda > 0, \mu > 0, \lambda + \mu = 1.$$

Then for any 1 ≤ *i* ≤ *m*, we have

$$\begin{aligned} &|a\_{i1}z\_1 + a\_{i2}z\_2 + \cdots + a\_{in}z\_n| \\ &\le \lambda |a\_{i1}\mathbf{x}\_1 + a\_{i2}\mathbf{x}\_2 + \cdots + a\_{in}\mathbf{x}\_n| + \mu |a\_{i1}\mathbf{y}\_1 + a\_{i2}\mathbf{y}\_2 + \cdots + a\_{in}\mathbf{y}\_n| \\ &\le \lambda c\_i + \mu c\_i = c\_i. \end{aligned}$$

So there is *z* = λ*x* + μ*y* ∈ *R*(*A*, *c*). Thus, *R*(*A*, *c*) is a symmetrical convex body. Lemma 7.2 holds.

**Lemma 7.3** *Let R* ⊂ R*n be a symmetrical convex body, x* ∈ *R, then when* |λ| ≤ 1*, we have* λ*x* ∈ *R.*

*Proof* By convexity, let

$$
\rho = \frac{1}{2}(1+\lambda), \ \sigma = \frac{1}{2}(1-\lambda).
$$

Then ρ ≥ 0, σ ≥ 0, and ρ + σ = 1. So there is

$$
\rho \ge +\sigma(-\mathbf{x}) = \lambda \mathbf{x} \in \mathcal{A}.
$$

The Lemma holds.

**Lemma 7.4** *If x*, *y* ∈ *R, then* λ*x* + μ*y* ∈ *R, where* λ,μ *are real numbers, and satisfies* |λ|+|μ| ≤ 1*.*

*Proof* Let η1 be the sign of λ and η2 be the sign of μ, then by Lemma 7.3,

$$\begin{aligned} \mathbf{x}' &= \eta\_1 (|\lambda| + |\mu|) \mathbf{x} \in \mathcal{R}, \\ \mathbf{y}' &= \eta\_2 (|\lambda| + |\mu|) \mathbf{y} \in \mathcal{R}. \end{aligned}$$

Let ρ = |λ| |λ|+|μ| , σ = |μ| |λ|+|μ| , then ρ + σ = 1. By definition, we have

$$
\lambda x + \mu \mathbf{y} = \rho x' + \sigma \mathbf{y}' \in \mathcal{K},
$$

thus the Lemma holds. And this result is not difficult to be extended to the case of *n* variables.

**Lemma 7.5** (Blichfeldt) *Let R* ⊂ R*n be any region in* R*n and V be the volume of R. If V* > 1*, then there are two different vectors x* ∈ *R*, *x* ∈ *R so that x* − *x is an integral point (thus a nonzero integral point).*

*Proof* For ∀*x* = (*x*1, *x*2,..., *xn*) ∈ R*n*, we define

$$\mathbf{f}\left[\left[\mathbf{x}\right]\right] = \left(\left[\mathbf{x}\_1\right], \left[\mathbf{x}\_2\right], \dots, \left[\mathbf{x}\_n\right]\right) \in \mathbb{Z}^n \tag{7.6}$$

and

$$\{\mathbf{x}\} = (\delta\_1, \delta\_2, \dots, \delta\_n) \in \mathbb{Z}'',\tag{7.7}$$

where [*xi*] is the square bracket function of *xi* and δ*i* is the nearest integer to *xi* .

For each integral point *u* ∈ Z*n*, define

$$\mathcal{R}\_{\boldsymbol{\mu}} = \{ \boldsymbol{\mathfrak{x}} \in \mathcal{R} | [\![\![\boldsymbol{\mathfrak{x}}]\!] = \boldsymbol{\mathfrak{x}} \}$$

and

$$D\_u = \{ \mathbf{x} - \boldsymbol{\mu} | \mathbf{x} \in \mathcal{R}\_u \}.$$

Because *Ru*1 ∩ *Ru*2 = ∅, if *u*1 = *u*2. Thus by *R* = *u Ru*,

$$\begin{aligned} \Rightarrow V &= \text{Vol}(\mathcal{R}) = \sum\_{u} \text{Vol}(\mathcal{R}\_{u}) \\ &= \sum\_{u} V\_{u} > 1, \end{aligned}$$

where *Vu* = Vol(*Ru*). Thus *Vu* = Vol(*Du*). If *Du* is disjoint, then

$$\sum\_{\boldsymbol{u}} V\_{\boldsymbol{u}} = \text{Vol}\left(\bigcup\_{\boldsymbol{u}} D\_{\boldsymbol{u}}\right) \subset [0,1) \times \dots \times [0,1).$$

There is

$$\sum\_{u} V\_{u} \le 1,$$

so there is a contradiction. Therefore, there must be two different integral points *u* and *u* (*u* = *u* ) ⇒ *Du* ∩ *Du* = 0, that is *x* − *u* = *x* − *u* ⇒ *x* − *x* = *u* − *u* ∈ Z*n*. The Lemma holds.

**Lemma 7.6** (Minkowski) *Let R be a symmetric convex body, and the volume of R*

$$V = \text{Vol}(\mathcal{R}) > 2^n,$$

*then R contains at least one nonzero integer point.*

*Proof* Let

$$\frac{1}{2}\mathcal{R} = \left\{\frac{1}{2}\mathbf{x}|\mathbf{x} \in \mathcal{R}\right\}.$$

Thus

$$\text{Vol}\left(\frac{1}{2}\mathcal{A}\right) = \frac{1}{2^n}V > 1,$$

by Lemma 7.5, there are integral points where *x* , *x* ∈ 1 2*R* ⇒ *x* − *x* = *u* is nonzero. We prove *u* ∈ *R*. Write *x* = 1 2 *y*, *x* = 1 2 *z*, where *y*,*z* ∈ *R*. Then

$$
\mu = \frac{1}{2}\mathbf{y} - \frac{1}{2}\mathbf{z}, \quad \mathbf{y} \in \mathcal{R}, \; \mathbf{z} \in \mathcal{R}.
$$

By Lemma 7.4, then *u* ∈ *R*. The Lemma holds.

*Remark 7.1* The aboveMinkowski's conclusion cannot be improved, that is *V* > 2*n*, it cannot be improved to *V* ≥ 2*n*. A counterexample is

$$\mathcal{A} = \{ \mathbf{x} \in \mathbb{R}^n | \mathbf{x} = (\mathbf{x}\_1, \mathbf{x}\_2, \dots, \mathbf{x}\_n), \forall \, |\mathbf{x}\_i| < 1 \}.$$

Obviously Vol(*R*) = 2*n*, but there is no nonzero integer point in ordinary *R*.

When Vol(*R*) = 2*n*, in order to make a symmetric convex body *R* still have nonzero integral points, we need to make some supplementary constraints on *R*, first, we consider the bounded region. Let *R* ⊂ R*n*, call *R* bounded, if

$$\mathcal{A} = \{ \mathbf{x} = (\mathbf{x}\_1, \mathbf{x}\_2, \dots, \mathbf{x}\_n) \in \mathbb{R}^n | |\mathbf{x}\_i| \le B, 1 \le i \le n \},$$

where *B* is a bounded constant.

**Lemma 7.7** *Let A*∈R*n*×*n be a reversible matrix, d* = |det(*A*)| > 0*, c* = (*c*1, *c*2,..., *cn*) ∈ R*n is a positive vector, that is* ∀ *ci* > 0*, then the symmetric convex body R*(*A*, *c*) *defined by Eq. (7.5) is bounded and its volume*

$$\text{Vol}(\mathcal{R}(A, c)) = 2^n d^{-1} c\_1 c\_2 \cdots c\_n.$$

*Proof* Let *A* = (*ai j*)*n*×*n*. Write *Ax* = *y*, then *x* = *A*−1 *y*. And let *A*−1 = (*bi j*)*n*×*n*, then for any *xi* , there is

$$|\mathbf{x}\_i| = \left| \sum\_{j=1}^n b\_{ij} y\_j \right| \le \sum\_{j=1}^n |b\_{ij}| \cdot c\_j \le B,$$

where *B* is a bounded constant. Therefore, *R*(*A*, *c*) is a bounded set. Obviously

$$\text{Vol}(\mathcal{R}(A,c)) = \int\limits\_{\mathbf{x} = (\mathbf{x}\_1, \mathbf{x}\_2, \dots, \mathbf{x}\_n) \in \mathcal{R}(A,c)} \text{d}\mathbf{x}\_1 \text{d}\mathbf{x}\_2 \cdots \text{d}\mathbf{x}\_n,$$

do variable replacement *Ax* = *y*, then

$$\mathrm{d}x = \mathrm{d}x\_1 \cdots \mathrm{d}x\_n = \frac{1}{|\mathrm{det}(A)|} \mathrm{d}y\_1 \mathrm{d}y\_2 \cdots \mathrm{d}y\_n.$$

Thus

$$\begin{aligned} \text{Vol}(\mathcal{R}(A, c)) &= \frac{1}{|\text{det}(A)|} \int\_{-c\_1}^{c\_1} \cdots \int\_{-c\_n}^{c\_n} \text{d}\mathbf{y}\_1 \text{d}\mathbf{y}\_2 \cdots \text{d}\mathbf{y}\_n \\ &= 2^n d^{-1} \prod\_{i=1}^n c\_i, \end{aligned}$$

Lemma 7.7 holds.

*Remark 7.2* In (7.5), "≤" is changed to "<" to define *R*(*A*, *c*), and the above lemma is still holds.

Now consider the general situation, let *A* = (*ai j*)*m*×*n*. If *m* > *n*, and rank(*A*) ≥ *n*, then *R*(*A*, *c*) defined by Eq. (7.5) is still a bounded region. Obviously if *m* < *n*, or *m* = *n*, rank(*A*) < *n*, then *R*(*A*, *c*) is an unbounded region, and *V* = ∞. Therefore, we have the following Corollary.

**Corollary 7.1** *Let A* = (*ai j*)*m*×*n, m* < *n or m* = *n,* det(*A*) = 0*, then for any small positive vector c* = (*c*1, *c*2,..., *cn*), 0 < *ci* < ε*, R*(*A*, *c*) *contains a nonzero integer point. In other words, the following m inequalities*

$$\left| \sum\_{j=1}^{n} a\_{ij} x\_j \right| < \varepsilon, \ l \le i \le m.$$

*There exists a nonzero integer solution x* = (*x*1, *x*2,..., *xn*) ∈ Z*n.*

*Proof* When ε > 0 given, then Vol(*R*(*A*, *c*)) = ∞ > 2*n*. By Lemma 7.6, *R*(*A*, *c*) contains at least one nonzero zero point.

Let *A* ∈ R*m*×*n* be a matrix of order *m* × *n*, *c* = (*c*1, *c*2,..., *cn*) ∈ R*n* is a positive vector, that is ∀ *ci* > 0, write *A* = (*ai j*)*m*×*n*, *R* (*A*, *c*)is defined as the set of solutions *x* = (*x*1, *x*2,..., *xn*) of the following linear inequality:

$$\begin{cases} \left| \sum\_{j=1}^{n} a\_{1j} x\_j \right| \le c\_1, \\\\ \left| \sum\_{j=1}^{n} a\_{ij} x\_j \right| < c\_i, \ i = 2, \dots, m. \end{cases} \tag{7.8}$$

When *A* ∈ R*n*×*n* is a reversible square matrix, we discuss the nonzero integral point in symmetric convex body *R* (*A*, *c*).

**Lemma 7.8** *If A* ∈ R*n*×*n is a reversible matrix and c* = (*c*1, *c*2,..., *cn*) *is a positive vector, when*

$$c\_1 c\_2 \cdots c\_n \ge |\det(A)|,\tag{7.9}$$

*Then R* (*A*, *c*) *contains a nonzero integer point.*

*Proof* When *c*1*c*2 ··· *cn* > |det(*A*)|, because of

$$\text{Vol}(\mathcal{R}'(A, c)) = \frac{2^n c\_1 c\_2 \cdots c\_n}{|\text{det}(A)|} > 2^n,$$

by Lemma 7.6 and 7.7, then the proposition holds, we only discuss the case when the equal sign of formula (7.9) holds.

Let ε be any positive real number, 0 <ε< 1, then by Lemma 7.7, there is a nonzero integral solution *x*(ε) = (*x*(ε) 1 , *x*(ε) 2 ,..., *x*(ε) *n* ) ∈ Z*n* satisfies

$$\begin{cases} \left| \sum\_{j=1}^{n} a\_{1j} x\_j^{(\boldsymbol{\epsilon})} \right| \le c\_1 + \varepsilon \le c\_1 + 1, \\\\ \left| \sum\_{j=1}^{n} a\_{ij} x\_j^{(\boldsymbol{\epsilon})} \right| < c\_i, \ 2 \le i \le n. \end{cases} \tag{7.10}$$

And there is an upper bound *B* independent of ε, which satisfies

$$|\mathbf{x}\_j^{(\iota)}| \le B, \quad 1 \le j \le n.$$

The integral point *x*(ε) satisfying the above bounded condition is finite, so there must be a nonzero integral point *x* = 0, which holds (7.10) for any ε > 0. Let ε → 0, then the Lemma holds.

In the following discussion, we make the following restrictions on *R* ⊂ R*n*:

*R* is a symmetric convex body, *R* is bounded, and *R* is a closed subset of R*n*.

(7.11) Obviously, when *A* is an *n*-order reversible square matrix, for any positive vector *c* = (*c*1, *c*2,..., *cn*), *R*(*A*, *c*)satisfies the above restriction (7.11), but *R* (*A*, *c*) does not because *R* (*A*, *c*) is not closed.

**Definition 7.2** If *R* ⊂ R*n* satisfies the restriction (7.11), then for any *x* ∈ R*n*, define the distance function *F*(*x*) as

$$F(\mathbf{x}) = F\_{\mathcal{R}}(\mathbf{x}) = \inf \{ \lambda | \lambda > 0, \lambda^{-1} \mathbf{x} \in \mathcal{R} \}. \tag{7.12}$$

By definition, it is obvious that we have the following ordinary conclusions:

$$F(\mathbf{x}) = \max\_{1 \le i \le n} c\_i^{-1} \left| \sum\_{j=1}^n a\_{ij} x\_j \right|. \tag{G1.12'}$$

Property (i) can be derived from the boundedness of *R*, and property (ii) can be derived directly from the definition of *R*(*A*, *c*). Later we will see that 0 ≤ *F*(*x*) < ∞ holds for all *x* ∈ R*n*. The main property of distance function *F*(*x*) is the following Lemma.

**Lemma 7.9** *If F*(*x*) *is a distance function defined by R satisfying the constraints, then*

*(iii) F*(*x* + *y*) ≤ *F*(*x*) + *F*(*y*), ∀ *x*, *y* ∈ R*n.*

*Proof* Since *R* is closed, by the definition, *F*−1(*x*)*x* ∈ *R*. Thus, if λ ≥ *F*(*x*), by Lemma 7.3, then

$$
\lambda^{-1}x = \frac{F(\mathbf{x})}{\lambda} \cdot F^{-1}(\mathbf{x})\mathbf{x}, \ \left|\frac{F(\mathbf{x})}{\lambda}\right| \le 1.
$$

We have λ−1*x* ∈ *R* ⇒ *x* ∈ λ*R*. Conversely, if λ < *F*(*x*) ⇒ λ−1*x* ∈/ *R*. So when *x* ∈ λ−*R*, there must be λ ≥ *F*(*x*), (i) holds.

(ii) is ordinary. Because |λ| −1*F*−1(*x*)λ*x* ∈ *R*. There is

$$F(\lambda x) \le |\lambda| F(x).$$

Conversely, let δ = *F*(λ*x*), because of δ−1λ*x* ∈ *R*, you might as well let λ > 0, thus

$$F(\mathbf{x}) \le \frac{\delta}{\lambda} \implies \lambda F(\mathbf{x}) \le F(\lambda \mathbf{x}).$$

So there is *F*(λ*x*) = |λ|*F*(*x*), (ii) holds.

To prove (iii), we let μ1 = *F*(*x*), μ2 = *F*(*y*), =⇒ μ−1 1 *x* ∈ *R*, μ−1 2 *y* ∈ *R*. By Lemma 7.4, we have

$$(\mu\_1 + \mu\_2)^{-1}(\mathbf{x} + \mathbf{y}) = \frac{\mu\_1}{\mu\_1 + \mu\_2}(\mu\_1^{-1}\mathbf{x}) + \frac{\mu\_2}{\mu\_1 + \mu\_2}(\mu\_2^{-1}\mathbf{y}) \in \mathcal{R}.$$

Thus

$$F(\mathbf{x} + \mathbf{y}) \le \mu\_1 + \mu\_2.$$

The Lemma holds.

Let the volume of *R* ∈ R*n* be *V* > 0, there are *n* linearly independent vectors {α1, α2,...,α*n*} in *R* to form a set of bases of R*n*. For any real number μ1, μ2,...,μ*n*, by Lemma 7.9, we have

$$\begin{aligned} F(\mu\_1\alpha\_1 + \dots + \mu\_n\alpha\_n) &\leq |\mu\_1|F(\alpha\_1) + |\mu\_2|F(\alpha\_2) + \dots + |\mu\_n|F(\alpha\_n) \\ &\leq |\mu\_1| + |\mu\_2| + \dots + |\mu\_n|. \end{aligned}$$

Because α*i* ∈ *R* ⇒ *F*(α*i*) ≤ 1, so the above formula holds. That proves for ∀ *x* ∈ R*n* ⇒ *F*(*x*) ≤ ∞.

**Corollary 7.2** *Let R* ⊂ R*n meet the limiting conditions (7.11), and* Vol(*R*) > 0*, then*

*(i)* ∀ *x* ∈ R*n, there is* λ *such that x* ∈ λ*R;*

*(ii) Let* {α1, α2,...,α*n*} ⊂ *R be a set of bases of* R*n, then*

$$\left\{ \sum\_{i=1}^{n} \mu\_i \alpha\_i ||\mu\_1| + |\mu\_2| + \dots + |\mu\_n| \le 1 \right\} \subset \mathcal{R}.$$

*Proof* Because *F*(*x*) < ∞, so by (i) of Lemma 7.9, we can directly deduce the conclusion of (i) and (ii) given directly by Lemma 7.4.

Now let *j* be a subscript, and we define λ*j* as

λ*j* = min{λ ≥ 0|λ*R* contains *j* linear independent integral points in R*n*}, (7.13)

and λ*j* is called the *j*th continuous minimum of *R*. By Lemma 7.3, λ*R* ⊂ λ *R*, if 0 ≤ λ ≤ λ . Therefore, λ increases continuously, then λ*R* can always contain any set of desired vectors. Therefore, the existence of λ*j* is proof.

By Lemma 7.6, let *V* be the volume of *R*, then Vol(λ*R*) = λ*nV*, for the first continuous minimum λ1, we have the following estimation

$$
\lambda\_1^n V \le 2^n. \tag{7.14}
$$

For λ*j* (*j* ≥ 2), there is no explicit upper bound estimation, but we have the following conclusions.

**Lemma 7.10** *Let R* ⊂ R*n be a convex body satisfying the limiting condition (7.11), V* = Vol(*R*)*,* λ1, λ2,...,λ*n be n continuous minima of R, then we have*

$$\frac{2^n}{n!} \le V\lambda\_1\lambda\_2\cdots\lambda\_n \le 2^n. \tag{7.15}$$

*Proof* We only prove the left inequality of the above formula, and we continuously select the linear independent whole point *x*(1) , *x*(2) ,..., *x*(*j*) such that *x*(*j*) ∈ λ*jR*, and *x*(*j*) *x*(1) , *x*(2) ,..., *x*(*j*−1) is linearly independent. Let *x*(*j*) =(*x j*1, *x j*2,..., *x jn*) ∈ Z*n*. Because matrix *A* = (*x ji*)*n*×*n* is an integer matrix, and det(*A*) = 0, so

$$|\det(A)| \ge 1.$$

By Lemma 7.9, for any constant μ1, μ2,...,μ*n*, we have

$$\begin{aligned} &F(\mu\_1 \mathbf{x}^{(1)} + \mu\_2 \mathbf{x}^{(2)} + \dots + \mu\_n \mathbf{x}^{(n)}) \\ &\le |\mu\_1| F(\mathbf{x}^{(1)}) + |\mu\_2| F(\mathbf{x}^{(2)}) + \dots + |\mu\_n| F(\mathbf{x}^{(n)}) \\ &\le |\mu\_1| \lambda\_1 + |\mu\_2| \lambda\_2 + \dots + |\mu\_n| \lambda\_n. \end{aligned}$$

Thus, if |μ1|λ1 + |μ2|λ2 +···+|μ*n*|λ*n* ≤ 1, then

$$
\mu\_1 \mathbf{x}^{(1)} + \mu\_2 \mathbf{x}^{(2)} + \dots + \mu\_n \mathbf{x}^{(n)} \in \mathcal{R}.
$$

So set

$$\mathcal{A}\mathcal{R}\_1 = \{\mu\_1 \mathbf{x}^{(1)} + \mu\_2 \mathbf{x}^{(2)} + \dots + \mu\_n \mathbf{x}^{(n)} || \mu\_1 | \lambda\_1 + |\mu\_2 | \lambda\_2 + \dots + |\mu\_n | \lambda\_n \le 1\} \subset \mathcal{A}'.$$

The volume of the left set *R*1 is

$$\begin{split} \mathrm{Vol}(\mathcal{R}\_{1}) &= \int \cdots \int \cdots \int\_{|\mu\_{1}|\lambda\_{1} + |\mu\_{2}|\lambda\_{2} + \cdots + |\mu\_{n}|\lambda\_{n} \leq 1} \mathrm{d}\mu\_{1} \mathrm{d}\mu\_{2} \cdots \mathrm{d}\mu\_{n} = \frac{2^{n}|\det(A)|}{n!\lambda\_{1}\cdots\lambda\_{n}} \\ &\geq \frac{2^{n}}{n!\lambda\_{1}\cdots\lambda\_{n}} .\end{split}$$

So there is

$$\frac{\mathcal{Z}^n}{n!\lambda\_1\cdots\lambda\_n} \le \text{Vol}(\mathcal{R}\_1) \le \text{Vol}(\mathcal{R}) = V.$$

Therefore, the left inequality of (7.15) holds. The proof of the right inequality is quite complex and is omitted here. Interested readers can refer to the classic works (1963, 1971) of J. W. S. Cassels.

An important application of the above geometry of numbers is to solve the problem of rational approximation of real numbers, which is called Diophantine approximation in classical number theory. The main conclusion of this section is the following simultaneous rational approximation theorem of *n* real numbers.

**Theorem 7.1** *Let* θ1, θ2,...,θ*n be any n real numbers,* θ*i* = 0*, then for any positive number N* > 1*, there are nonzero positive integers q and p*1, *p*2,..., *pn to satisfy*

$$\begin{cases} |q\theta\_i - p\_i| < N^{-\frac{1}{n}}, & 1 \le i \le n; \\\ |q| \le N. \end{cases} \tag{7.16}$$

*Proof* The proof of the theorem is a simple application of Minkowski's linear type theorem (see Lemma 7.8). Let *A* ∈ R(*n*+1)×(*n*+1) be an (*n* + 1)-order reversible square matrix, defined as

$$A = \begin{pmatrix} -1 & 0 & \cdots & \cdots & 0 & \theta\_1 \\ 0 & -1 & \cdots & \cdots & 0 & \theta\_2 \\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\ 0 & 0 & \cdots & 0 & -1 & \theta\_n \\ 0 & \cdots & \cdots & 0 & 0 & -1 \end{pmatrix}.$$

Obviously |det(*A*)| = 1. Let (*n* + 1)-dimensional positive vector *c* = (*N* − 1 *n* , *N* − 1 *n* , ..., *N* − 1 *n* , *N*), because

$$c\_1 c\_2 \cdots c\_n c\_{n+1} = N^{-1} \cdot N = 1 \ge |\det(A)|\dots$$

So by Lemma 7.8, the symmetric convex body *R* (*A*, *c*) defined by *A* and *c* has a nonzero integral point *x* = (*p*1, *p*2,..., *pn*, *q*) = 0. We prove *q* = 0. Because *x* = 0, if *q* = 0, then *pk* = 0 (1 ≤ *k* ≤ *n*), therefore, the *k*-th inequality in Eq. (7.16) will produce the following contradiction,

$$1 \le |q\theta\_k - p\_k| < N^{-\frac{1}{n}} < 1.$$

So *q* = 0, we complete the proof of Theorem 7.1.

**Corollary 7.3** *Let* θ1,...,θ*n be any n real numbers, then for any* ε > 0*, there is rational number pi q* (1 ≤ *i* ≤ *n*) *satisfies*

$$\left|\theta\_i - \frac{p\_i}{q}\right| < \frac{\varepsilon}{q}.\tag{7.17}$$

*Proof* Any ε > 0 given, let *N* − 1 *n* < ε, Formula (7.17) can be derived directly from Theorem 7.1.

# **7.2 Basic Properties of Lattice**

Lattice is one of the most important concepts in modern cryptography. Most of the so-called anti-quantum computing attacks are lattice based cryptosystems. What is a lattice? In short, a lattice is a geometry in *n*-dimensional Euclidean space R*n*, for example *L* = Z*n* ⊂ R*n*, then Z*n* is a lattice in R*n*, which is called an integer lattice or a trivial lattice. If Z*n* is rotated once, we get the concept of a general lattice in R*n*, which is a geometric description of a lattice, next, we give an algebraic precise definition of a lattice.

**Definition 7.3** Let *L* ⊂ R*n* be a nonempty subset, which is called a lattice in R*n*, if

$$\min\{|x||\mathbf{x}\in L, \mathbf{x}\neq \mathbf{0}\} = \lambda,\tag{7.18}$$

λ = λ(*L*) is called the minimal distance of a lattice *L*.

By Definition 7.3, a lattice is simply a discrete additive subgroup in R*n*, in which the minimum distance λ = λ(*L*) is the most important mathematical quantity of the lattice. Obviously, we have

$$\lambda = \min\{|\mathbf{x} - \mathbf{y}| | \mathbf{x} \in L, \mathbf{y} \in L, \mathbf{x} \neq \mathbf{y} \},\tag{7.19}$$

Equation (7.19) shows the reason why λ is called the minimal distance of a lattice. If *x* ∈ *L* and |*x*| = λ, *x* is called the shortest vector of *L*.

In order to obtain a more explicit and concise mathematical expression of any lattice, we can regard an additive subgroup as a Z-module. First, we prove that any lattice is a finitely generated Z-module.

**Lemma 7.11** *Let L* ⊂ R*n be a lattice and* {α1, α2,...,α*m*} ⊂ *L be a set of vectors in L, then* {α1, α2,...,α*m*}*is linearly independent in* R *if and only if*{α1, α2,...,α*m*} *is linearly independent in* Z*.*

*Proof* If {α1, α2,...,α*m*} is linearly independent in R, it is obviously linearly independent in Z. conversely, if {α1, α2,...,α*m*} is linearly independent in Z, that is, any linear combination

$$a\_1\alpha\_1 + \dots + a\_m\alpha\_m = 0, \quad a\_i \in \mathbb{Z}, i$$

we have *a*1 = *a*2 =···= *am* = 0, then the linear combination in R is equal to 0, that is

$$
\theta\_1 \alpha\_1 + \theta\_2 \alpha\_2 + \dots + \theta\_m \alpha\_m = 0, \ \theta\_i \in \mathbb{R}. \tag{7.20}
$$

We prove θ1 = θ2 =···= θ*m* = 0. By Lemma 7.1, for sufficiently large *N* > 1, there are positive integers *q* = 0 and *p*1, *p*2,..., *pm* such that

$$\begin{cases} |q\theta\_i - p\_i| < N^{-\frac{1}{m}}, & 1 \le i \le m; \\ q \le N. \end{cases}$$

By (7.20), we have

$$\begin{aligned} |p\_1\alpha\_1 + \dots + p\_m\alpha\_m| &= |(q\theta\_1 - p\_1)\alpha\_1 + \dots + (q\theta\_m - p\_m)\alpha\_m| \\ &\le N^{-\frac{1}{m}}(|\alpha\_1| + \dots + |\alpha\_m|) \\ &\le N^{-\frac{1}{m}} \max\_{1 \le i \le m} |\alpha\_i|. \end{aligned}$$

Let λ be the minimal distance of *L* and ε > 0 be a sufficiently small positive number, we choose

$$N > \max\left\{ \varepsilon^{-m}, \max\_{1 \le i \le m} \frac{|\alpha\_i|^m}{\lambda^m} \right\},$$

then *N* − 1 *m* < ε, and

$$N^{-\frac{1}{m}} \max\_{1 \le i \le m} |\alpha\_i| < \lambda.$$

Thus

$$|p\_1\alpha\_1 + \dots + p\_m\alpha\_m| < \lambda\_\dots$$

Notice that *p*1α1 +···+ *pm*α*m* ∈ *L*, so *p*1α1 +···+ *pm*α*m* = 0. Since {α1, α2, ...,α*m*} is linearly independent on Z, *p*1 = *p*2 =···= *pm* = 0 is derived. For any *i*, 1 ≤ *i* ≤ *m*, we get |θ*i*|≤|*q*θ*i*| < *N* − 1 *m* < ε. Since ε is any small positive number, there is θ1 = θ2 =···= θ*m* = 0. This proves that {α1, α2,...,α*m*} is also linearly independent in R. Lemma 7.11 holds.

From the above lemma, any lattice *L* in R*n* is a finitely generated Z-module. Let {β1, β2,...,β*m*} ⊂ *L* be a set of Z-bases in *L*, then *L* as the rank of Z-module satisfies

$$\text{rank}(L) = m \le n,\tag{7.21}$$

and

$$L = \left\{\sum\_{i=1}^{m} a\_i \beta\_i | a\_i \in \mathbb{Z}\right\}.\tag{7.22}$$

If {β1, β2,...,β*m*} is a Z-basis of *L* and each β*i* is regarded as a column vector, then the matrix

$$B = [\beta\_1, \beta\_2, \dots, \beta\_m] \in \mathbb{R}^{n \times m}, \quad \text{rank}(B) = m.$$

Equation (7.22) can be written as

$$L = L(B) = \{ Bx | x \in \mathbb{Z}^m \} \subset \mathbb{R}^n. \tag{7.23}$$

We take *L* as the Z-modules, *m* as the rank of lattice *L*, *B* ∈ R*n*×*m* as the generating matrix of lattice *L*, and {β1, β2,...,β*m*} as a set of generating bases of *L*.

If {α1, α2,...,α*m*} ⊂ R*n* is any *m* column vectors in R*n*, the Gram matrix of *A* = [α1, α2,...,α*m*] ∈ R*n*×*m*, {α1, α2,...,α*m*} is defined as

$$T = (\langle \alpha\_i, \alpha\_j \rangle)\_{m \times m} \cdot$$

Obviously, we have *T* = *A A*, where *A* is the transpose matrix of *A*.

**Lemma 7.12** *Let A* ∈ R*n*×*m, b* ∈ R*n (m* ≤ *n is not required), then*

*(i) Let x*0 ∈ R*m be a solution of A Ax* = *A b, then*

$$|A\mathbf{x}\_0 - b|^2 = \min\_{\mathbf{x} \in \mathbb{R}^m} |A\mathbf{x} - b|^2.$$

$$x = \left(A^\prime A\right)^{-1} A^\prime b.$$

*Proof* First we prove (i). Let *x*0 ∈ R*m* satisfies *A Ax*0 = *A b*, then for any *x* ∈ R*m*, we have

$$Ax - b = (Ax\_0 - b) + A(x - x\_0) = \mathcal{Y} + \mathcal{Y}\_1 \in \mathbb{R}^n.$$

We prove that γ and γ1 are two orthogonal vectors in R*n*. Because

$$\begin{aligned} (A(\mathbf{x} - \mathbf{x}\_0))'(A\mathbf{x}\_0 - b) \\ &= (\mathbf{x} - \mathbf{x}\_0)'A'(A\mathbf{x}\_0 - b) \\ &= (\mathbf{x} - \mathbf{x}\_0)'(A'A\mathbf{x}\_0 - A'b) = 0. \end{aligned}$$

So γ ⊥γ1, by Pythagorean theorem, we have

$$|A\mathbf{x} - b|^2 = |A\mathbf{x}\_0 - b|^2 + |A(\mathbf{x} - \mathbf{x}\_0)|^2 \ge |A\mathbf{x}\_0 - b|^2.$$

So (i) holds.

To prove (ii), let *VA* be the solution space of *Ax* = 0 and *VA A* the solution space of *A Ax* = 0, let's prove *VA* = *VA A*. First, there is *VA* ⊂ *VA A*. Conversely, let *x* ∈ *VA A*, that is *A Ax* = 0, then

$$
\alpha' A' A x = 0 \Rightarrow (A\alpha)' A x = \langle A\alpha, A\alpha \rangle = 0.
$$

The above formula holds if and only if *Ax* = 0, so *x* ∈ *VA*. There is *VA* = *VA A*. Notice that

$$\begin{cases} \dim V\_A = m - \text{rank}(A) \\ \dim V\_{A'A} = m - \text{rank}(A'A) .\end{cases}$$

So rank(*A*) = rank(*A A*), (ii) holds. To prove (iii), *b* ∈ R*n* given, then the rank of the augmented matrix of linear equation system *A Ax* = *A b* is

$$\begin{aligned} \text{rank}[A'A, A'b] &= \text{rank}(A'[A, b]) \\ &\le \text{rank}(A') = \text{rank}(A) = \text{rank}(A'A). \end{aligned}$$

Therefore, the augmented matrix and the coefficient matrix have the same rank, so the linear equations have solutions. When rank(*A*) = *m*, then rank(*A A*) = *m*, that is, *A A* is a reversible *m*-order square matrix, thus

$$x = (A^\prime A)^{-1} \cdot A^\prime b, \text{implies the solution is unique.}$$

Lemma 7.12 holds!

**Lemma 7.13** *A* ∈ R*n*×*m, and* rank(*A*) = *m, then A A is a positive definite real symmetric matrix of order m, so there is a real orthogonal matrix P* ∈ R*m*×*m of order m satisfies*

$$P'A'AP = \begin{vmatrix} \delta\_1 \ \cdots \ \cdot & 0 \\ \vdots & \delta\_2 \\ \vdots & \dots \ \cdot & \cdot \\ 0 & & \delta\_m \end{vmatrix},\tag{7.24}$$

*where* δ*i* > 0 *is the m eigenvalues of A A.*

*Proof* rank(*A*) = *m* ⇒ *m* ≤ *n*. Let *T* = *A A*, then *T* is a symmetric matrix of order *m*. Let *x* ∈ R*m* be *m* arguments, quadratic form

$$
\lambda^\prime T x = \mathfrak{x}^\prime A^\prime A x = (A\mathfrak{x})^\prime (A\mathfrak{x}) = \langle A\mathfrak{x}, A\mathfrak{x} \rangle \ge 0.
$$

Because rank(*A*) = *m*, the above formula if and only if when *x* = 0, *x T x* = 0. So *T* is a positive definite matrix. From the knowledge of linear algebra, there is an orthogonal matrix of order *m*, *P* ⇒ *P T P* is a diagonal matrix, that is

$$P'TP = \text{diag}\{\delta\_1, \delta\_2, \dots, \delta\_m\}.$$

Because *P T P* and *T* have the same eigenvalue, δ1, δ2,...,δ*m* is the eigenvalue of *T* , and ∀ δ*i* > 0. The Lemma holds.

Lemma 7.12 is called the least square method in linear algebra, its significance is to find a vector *x*0 with the shortest length in the set {*Ax* − *b*|*x* ∈ R*m*} for a given *n* × *m*-order matrix *A* and a given vector *b* ∈ R*n*. Lemma 7.12 gives an effective algorithm, that is, to solve the linear equations *A Ax* = *A b*, and *x*0 is the solution of the equations, Lemma 7.13 is called the diagonalization of quadratic form. Now, the main results are as follows:

**Theorem 7.2** *Let L* ⊂ R*n be a lattice,* rank(*L*) = *m* (*m* ≤ *n*)*, if and only if there is a real matrix B* ∈ R*n*×*m of order n* × *m,* rank(*B*) = *m, such that*

$$L = \{ B \ge |\boldsymbol{x} \in \mathbb{Z}^m \} = \left\{ \sum\_{i=1}^m a\_i \beta\_i | a\_i \in \mathbb{Z} \right\},\tag{7.25}$$

*where B* = [β1, β2,...,β*m*]*, each* β*i* ∈ R*n is a column vector.*

*Proof* Equation (7.23) proves the necessity of the condition, and we only prove the sufficiency of the condition. If a subset *L* in R*n* is given by Eq. (7.25), it is obvious that *L* is an additive subgroup of R*n*, because any α = *Bx*1, β = *Bx*2, where *x*1, *x*2 ∈ Z*m*, then *x* = *x*1 − *x*2 ∈ Z*n*, and

$$
\alpha - \beta = B(\mathbf{x}\_1 - \mathbf{x}\_2) = B\mathbf{x} \in L.
$$

So we only prove the discreteness of *L*. Let *T* = *B B*, then from Lemma 7.13, *T* is a positive definite real symmetric matrix, let δ1, δ2,...,δ*m* be the eigenvalue of *T* , then

$$\delta = \min\{\delta\_1, \delta\_2, \dots, \delta\_m\} > 0.$$

We prove

$$\min\_{\substack{x \in \mathbb{Z}^n \\ x \neq 0}} |Bx| \ge \sqrt{\delta} > 0. \tag{7.26}$$

By Lemma 7.13, there is an orthogonal matrix *P* of order *m* such that

$$P'TP = \text{diag}\{\delta\_1, \delta\_2, \dots, \delta\_m\}.$$

For any given *x* ∈ Z*m*, *x* = 0. We have

$$\|B\mathbf{x}\|^2 = \mathbf{x}'T\mathbf{x} = \mathbf{x}'P(P'TP)P'\mathbf{x} \ge \delta |P'\mathbf{x}|^2 = \delta |\mathbf{x}|^2.$$

Because *x* = 0, then |*x*| 2 ≥ 1, so

$$\left|B\mathbf{x}\right|^2 \ge \delta, \quad \forall \ \mathbf{x} \in \mathbb{Z}^m, \ \mathbf{x} \ne \mathbf{0}.$$

This shows that the distance between any two different points in *L* is ≥ δ > 0. Therefore, in a sphere with 0 as the center and *r* as the radius, the number of points in *L* is finite. In these finite vectors, there is a α ∈ *L*,⇒

$$|\alpha| = \min\_{\substack{\boldsymbol{x} \in I \\ \boldsymbol{x} \neq \boldsymbol{0}}} |\boldsymbol{x}| = \lambda \ge \delta > 0.$$

According to the definition of lattice, *L* is a lattice in R*n*, the Lemma holds.

It can be directly deduced from the above theorem

**Corollary 7.4** *Let L* = *L*(*B*) ⊂ R*n be a lattice of* rank(*L*) = *m,* λ *be the minimum distance of L, B* ∈ R*n*×*m,* δ *be the minimum eigenvalue of B B, then* λ ≥ √δ*.*

**Definition 7.4** *L* ⊂ R*n* is a lattice, and rank(*L*) = *n*, call *L* is a full rank lattice of R*n*.

By Theorem 7.2, a sufficient and necessary condition for a full rank lattice with *L* as R*n* is the existence of a reversible square matrix *B* ∈ R*n*×*n*, det(*B*) = 0, such that

$$L = L(B) = \left\{ \sum\_{i=1}^{n} a\_i \beta\_i | a\_i \in \mathbb{Z}, \; 1 \le i \le n \right\} = \{ B\mathbf{x} | \mathbf{x} \in \mathbb{Z}^n \}.\tag{7.27}$$

If *L* = *L*(*B*) is a full rank lattice, define *d* = *d*(*L*) as

$$d = d(L) = |\det(B)|,\tag{7.28}$$

call *d* is the determinant of *L*. *d* = *d*(*L*) is the second most important mathematical quantity of a lattice. The lattice we discuss below is always assumed to be a full rank lattice.

For a lattice (full rank lattice), the generating matrix is not unique, but *d* = *d*(*L*) is unique. To prove this, first define the so-called unimodular matrix. Define

$$SL\_n(\mathbb{Z}) = \{ A = (a\_{ij})\_{n \times n} | a\_{ij} \in \mathbb{Z}, \det(A) = \pm 1 \},\tag{7.29}$$

Obviously, *SLn*(Z) forms a group under the multiplication of the matrix, because the *n*-order identity matrix *In* ∈ *SLn*(Z), and *A*1 ∈ *SLn*(Z), *A*2 ∈ *SLn*(Z), then *A* = *A*1*A*2 ∈ *SLn*(Z).

**Lemma 7.14** *L* = *L*(*B*) ⊂ R*n is a lattice (full rank lattice), B*1 ∈ R*n*×*n, then L* = *L*(*B*) = *L*(*B*1)*if and only if there is a unimodular matrix U* ∈ *SLn*(Z) ⇒ *B* = *B*1*U.* *Proof* If *B* = *B*1*U*, *U* ∈ *SLn*(Z), we prove *L*(*B*) = *L*(*B*1). Let α = *B*1*x* ∈ *L*(*B*1), where *x* ∈ Z*n*, then

$$\alpha = B\_1 \mathbf{x} = B\_1 U U^{-1} \mathbf{x} = B U^{-1} \mathbf{x}.$$

Because of *U* −1*x* ∈ Z*n*, then α ∈ *L*(*B*), that is *L*(*B*1) ⊂ *L*(*B*). Similarly, if α = *Bx*, *x* ∈ Z*n*, then

$$\alpha = Bx = B\_1 Ux \text{, where } Ux \in \mathbb{Z}^n.$$

Thus, α ∈ *L*(*B*1), that is *L*(*B*) = *L*(*B*1).

Conversely, if *L*(*B*) = *L*(*B*1), let *B* = [β1, β2,...,β*n*], *B*1 = [α1, α2,...,α*n*], transition matrix

$$(\beta\_1, \beta\_2, \dots, \beta\_n) = (\alpha\_1, \alpha\_2, \dots, \alpha\_n)U.$$

Obviously by β*i* ∈ *L*(*B*1)(1 ≤ *i* ≤ *n*), *U* is an integer matrix. and

$$(\alpha\_1, \alpha\_2, \dots, \alpha\_n) = (\beta\_1, \beta\_2, \dots, \beta\_n) U\_1 \dots$$

Because α*i* ∈ *L*(*B*)(1 ≤ *i* ≤ *n*), *U*1 also is an integer matrix. Because of

$$(\beta\_1, \beta\_2, \dots, \beta\_n) = (\alpha\_1, \alpha\_2, \dots, \alpha\_n)U = (\beta\_1, \beta\_2, \dots, \beta\_n)U\_1U.$$

We have *U*1*U* = *In*, thus det(*U*) = ±1, that is *U* ∈ *SLn*(Z), *B* = *B*1*U*, the Lemma holds.

By Lemma 7.14, *B*, *B*1 are any two generating matrices of a lattice *L*, then

$$|\det(B)| = |\det(B\_1)| = d = d(L).$$

That is, the determinant *d*(*L*) of a lattice is an invariant.

For a lattice (full rank lattice) *L* ⊂ R*n*, the dual lattice of *L* is defined as

$$L^\* = \{ \alpha \in \mathbb{R}^n | \langle \alpha, \beta \rangle \in \mathbb{Z}, \forall \, \beta \in L \}. \tag{7.30}$$

**Lemma 7.15** *Let L* = *L*(*B*) *be a lattice, then the dual lattice of L is L*∗ = *L*((*B*−1) )*, that is, if B is the generating matrix of L, then* (*B*−1) *is the generating matrix of L*∗*.*

*Proof* Let

$$L((B^{-1})') = \{ (B^{-1})' \circ | \, \mathbf{y} \in \mathbb{Z}^n \}.$$

any α ∈ *L*((*B*−1) ), α = (*B*−1) *y*, *y* ∈ Z*n*, β ∈ *L*, β = *Bx*, *x* ∈ Z*n*, then

$$
\langle \alpha, \beta \rangle = \alpha' \beta = \mathbf{y}' B^{-1} B \mathbf{x} = \mathbf{y}' \mathbf{x} \in \mathbb{Z}.
$$

That means *L*((*B*−1) ) ⊂ *L*∗. Conversely, any α ∈ *L*∗, for all β ∈ *L*, there isα, β ∈ Z. So let *B* = [β1, β2,...,β*n*], then

#### 7.2 Basic Properties of Lattice 271

$$\left\langle \alpha, \sum\_{i=1}^{n} x\_i \beta\_i \right\rangle = \sum\_{i=1}^{n} x\_i \langle \alpha, \beta\_i \rangle \in \mathbb{Z}, \forall \ x\_i \in \mathbb{Z},$$

therefore, for each generating vector β*i*(1 ≤ *i* ≤ *n*), there is α, β*i* ∈ Z. Write α = (*y*1, *y*2,..., *yn*),

$$\langle \alpha, \beta\_i \rangle \in \mathbb{Z}, \Longrightarrow \begin{pmatrix} \mathsf{y}\_1 \\ \vdots \\ \mathsf{y}\_n \end{pmatrix} = \begin{pmatrix} \mathsf{x}\_1 \\ \vdots \\ \mathsf{x}\_n \end{pmatrix} \in \mathbb{Z}^n.$$

Thus

$$
\begin{pmatrix} \mathbb{y}\_1 \\ \vdots \\ \mathbb{y}\_n \end{pmatrix} \in (B')^{-1} \begin{pmatrix} x\_1 \\ \vdots \\ x\_n \end{pmatrix}.
$$

That is α ∈ *L*((*B* )−1). Because *B* · *B*−1 = *In*, =⇒ (*B*−1) *B* = *In*, thus (*B*−1) = (*B* )−1. So α ∈ *L*((*B*−1) ), that is *L*∗ ⊂ *L*((*B*−1) ). We have *L*∗ = *L*((*B*−1) ). The Lemma holds.

By Lemma 7.15, we immediately have the following corollary.

**Corollary 7.5** *Let L* = *L*(*B*) *be a full rank lattice, L*∗ *is the dual lattice of L, then*

$$d(L^\*) = d^{-1}(L).$$

An equivalence relation in R*n* can be defined by using a lattice *L*, for all α, β ∈ R*n*, we define

$$\alpha \equiv \beta (\text{mod } L) \Longleftrightarrow \alpha - \beta \in L.$$

Obviously, this is an equivalent relation, called the congruence relation of mod *L*.

**Definition 7.5** Let *F* ⊂ R*n* be a subset, and call *F* the basic region of a lattice (full rank lattice) *L*, if

By definition, the basic neighborhood of a lattice is the representative element set of the additive quotient group R*n*/*L*. Therefore, a basic neighborhood of any *L* forms an additive group under mod *L*.

**Lemma 7.16** *Let L* = *L*(*B*) *be a full rank lattice, then*

272 7 Lattice-Based Cryptography

*(iii)* Vol(*F*) = *d* = *d*(*L*)*.*

*Proof* (i) is trivial, because

$$F\_1 \cong \mathbb{R}^n / L, \, F\_2 \cong \mathbb{R}^n / L, \, \Longrightarrow \, F\_1 \cong F\_2.$$

To prove (ii), let *B* = [β1, β2,...,β*n*], then {β1, β2,...,β*n*} is a set of bases of R*n*, ∀ α ∈ R*n*, α can be expressed as a linear combination of β1, β2,...,β*n*, that is

$$\alpha = \sum\_{i=1}^{n} a\_i \beta\_i, \forall \ a\_i \in \mathbb{R}.$$

Let [α]*B* = "*n i*=1[*ai*]β*i* , {α}*B* = α − [α]*B*, then {α}*B* can be expressed as

$$\{\alpha\}\_B = B \begin{pmatrix} \chi\_1 \\ \chi\_2 \\ \vdots \\ \chi\_n \end{pmatrix}, \text{ where } 0 \le \chi\_i < 1, \quad 1 \le i \le n.$$

That is {α}*B* ∈ *F*. Because α − {α}*B* = [α]*B* ∈ *L*, so for any α ∈ R*n*, there is a {α}*B* ∈ *F*, such that

$$\alpha \equiv \langle \alpha \rangle\_B (\text{mod } L).$$

And two points α = *Bx* and β = *By* in *F*, then

$$
\alpha - \beta = B(\alpha - \mathfrak{y}) = Bz.
$$

where *z* = (*z*1,*z*2,...,*zn*), |*zi*| < 1. So α ≡ β(mod *L*), if α = β. So *F* is a basic neighborhood of *L*.

Let's prove (iii). Because all basic neighborhoods of *L* are isomorphic, they have the same volume, (iii) gives a specific basic region *F* of *L*, so we can only prove Vol(*F*) = *d* = *d*(*L*). Obviously,

$$\text{Vol}(F) = \int\limits\_{\mathbf{y} = (y\_1, y\_2, \dots, y\_n) \in F} \mathbf{d} \mathbf{y}\_1 \mathbf{d} \mathbf{y}\_2 \cdots \mathbf{d} \mathbf{y}\_n$$

make variable substitution *Bx* = *y* and calculate the Jacobi of the vector value

$$\mathbf{d} \mathbf{y}\_1 \mathbf{d} \mathbf{y}\_2 \cdots \mathbf{d} \mathbf{y}\_n = d(\lambda) \mathbf{d} x\_1 \cdots \mathbf{d} x\_n \dots$$

#### 7.2 Basic Properties of Lattice 273

Thus

$$\text{Vol}(F) = \int\_0^1 \cdots \int\_0^1 d(\lambda) \text{d}x\_1 \cdots \text{d}x\_n = d(L).$$

We have completed the proof of Lemma 7.16.

Next, we discuss the gram Schmidt orthogonalization algorithm. If *B* = [β1, β2, ...,β*n*] is the generation matrix of *L*, {β1, β2,...,β*n*} can be transformed into a set of orthogonal bases {β∗ 1 , β∗ 2 ,...,β∗ *n* }, where β∗ 1 = β1, and

$$
\beta\_i^\* = \beta\_i - \sum\_{j=1}^{i-1} \frac{\langle \beta\_i, \beta\_j^\* \rangle}{\langle \beta\_j^\*, \beta\_j^\* \rangle} \beta\_j^\*, \tag{7.31}
$$

{β∗ 1 , β∗ 2 ,...,β∗ *n* } is called the orthogonal basis corresponding to {β1, β2,...,β*n*}. *B*∗ = [β∗ 1 ,...,β∗ *n* ] is the orthogonal matrix corresponding to *B*. For any 1 ≤ *i* ≤ *n*, denote

$$\begin{cases} u\_{ii} = 1, u\_{ij} = 0, \text{when } j > i. \\ u\_{ij} = \frac{\langle \beta\_i, \beta\_j^\* \rangle}{|\beta\_j^\*|^2}, \text{when } 1 \le j \le i \le n. \\ U = (u\_{ij})\_{n \times n}. \end{cases} \tag{7.32}$$

Then *U* is a lower triangular matrix, and

$$
\begin{pmatrix} \beta\_1 \\ \beta\_2 \\ \vdots \\ \beta\_n \end{pmatrix} = U \begin{pmatrix} \beta\_1^\* \\ \beta\_2^\* \\ \vdots \\ \beta\_n^\* \end{pmatrix}. \tag{7.33}
$$

If both sides are transposed at the same time, there is

$$(\beta\_1, \beta\_2, \dots, \beta\_n) = (\beta\_1^\*, \beta\_2^\*, \dots, \beta\_n^\*)U'.\tag{7.34}$$

Therefore, *U* is the transition matrix between two groups of bases.

**Lemma 7.17** *Let L* = *L*(*B*) ⊂ R*n be a lattice, B* = [β1, β2,...,β*n*] *is the generating matrix, B*∗ = [β∗ 1 , β∗ 2 ,...,β∗ *n* ] *is the corresponding orthogonal matrix, d* = *d*(*L*) *is the determinant of L, then we have*

$$d = \prod\_{i=1}^{n} |\beta\_i^\*| \le \prod\_{i=1}^{n} |\beta\_i|. \tag{7.35}$$

*Proof* By (7.24), we have *B* = *B*∗*U*, because det(*U*) = 1, so

$$\det(B) = \det(B^\*).$$

By the definition,

$$\begin{aligned} d^2 &= \det(B^\prime B) = \det(U(B^\*)^\prime B^\* U^\prime) \\ &= \det((B^\*)^\prime B^\*) \\ &= \det(\text{diag}(|\beta\_1^\*|^2, |\beta\_2^\*|^2, \dots, |\beta\_n^\*|^2)). \end{aligned}$$

So there is

$$d = \prod\_{i=1}^{n} |\mathcal{B}\_i^\*| \dots$$

In order to prove the inequality on the right of Eq. (7.35), we only prove

$$|\beta\_i^\*| \le |\beta\_i|, \quad 1 \le i \le n. \tag{7.36}$$

Because β*i* = "*i j*=1 *ui j*β∗ *j* , then

$$\begin{aligned} |\beta\_i|^2 &= \langle \beta\_i, \beta\_i \rangle = \left\langle \sum\_{j=1}^i u\_{ij} \beta\_j^\*, \sum\_{j=1}^i u\_{ij} \beta\_j^\* \right\rangle \\ &= \sum\_{j=1}^i u\_{ij}^2 \langle \beta\_j^\*, \beta\_j^\* \rangle \\ &= \langle \beta\_i^\*, \beta\_i^\* \rangle + \sum\_{j=1}^{i-1} u\_{ij}^2 \langle \beta\_j^\*, \beta\_j^\* \rangle. \end{aligned}$$

Therefore, the inequality on the right of (7.35) holds, the Lemma is proved.

Equation (7.35) is usually called Hadamard inequality, and we give another proof here.

In order to define the concept of continuous minima on a lattice *L*, we record the minimum distance on *L* with λ1. That is λ1 = λ(*L*). Another definition of λ1 is the minimum positive real number *r*, so that the linear space formed by *L* ∩ Ball(0,*r*) is a one-dimensional space, where

$$\text{Ball}(0, r) = \{x \in \mathbb{R}^n | |x| \le r\}$$

is a closed sphere with 0 as the center and *r* as the radius. The concept of *n* continuous minima λ1, λ2,...,λ*n* in *L* can be given.

**Definition 7.6** Let *L* = *L*(*B*) ⊂ R*n* be a full rank lattice, the *i*-th continuous minimum λ*i* is defined as

$$
\lambda\_i = \lambda\_i(L) = \inf \{ r | \dim(\text{span}(L \cap \text{Ball}(0, r))) \ge i \}.
$$

#### 7.2 Basic Properties of Lattice 275

The following lemma is a useful lower bound estimate of the minimum distance λ1.

**Lemma 7.18** *L* = *L*(*B*) ⊂ R*n is a lettice (full rank lattice), B*∗ = [β∗ 1 , β∗ 2 ,...,β∗ *n* ] *is the corresponding orthogonal basis, then*

$$
\lambda\_1 = \lambda(L) \ge \min\_{1 \le i \le n} |\beta\_i^\*|. \tag{7.37}
$$

*Proof* For ∀ *x* ∈ Z*n*, *x* = 0, we prove

$$|\mathcal{B}x| \ge \min\_{1 \le i \le n} |\beta\_i^\*|, \ x \in \mathbb{Z}^n, \ x \ne 0.$$

Let *x* = (*x*1, *x*2,..., *xn*) = 0, *j* be the largest subscript ⇒ *x j* = 0, then

$$|\langle Bx, \beta\_j^\* \rangle| = \left| \left\langle \sum\_{i=1}^j x\_i \beta\_j, \beta\_j^\* \right\rangle \right| = |x\_j| |\beta\_j^\*|^2.$$

Because when *i* < *j*,

$$
\langle \beta\_i, \beta\_j^\* \rangle = 0, \text{ and } \langle \beta\_j, \beta\_j^\* \rangle = \langle \beta\_j^\*, \beta\_j^\* \rangle.
$$

On the other hand,

$$|\langle Bx, \beta\_j^\* \rangle| \le |Bx||\beta\_j^\*|.$$

So

$$|Bx| \ge |x\_j| |\beta\_j^\*| \ge \min\_{1 \le i \le n} |\beta\_i^\*|.$$

Lemma 7.18 holds!

**Corollary 7.6** *The continuous minimum* λ1, λ2,...,λ*n of a lattice L is reachable, that is, it exists* α*i* ∈ *L* ⇒ |α*i*| = λ*i ,* 1 ≤ *i* ≤ *n.*

*Proof* The lattice points contained in ball Ball(0, δ) with center 0 and radius δ (δ > λ*i*) are finite, because in a bounded region (finite volume), if there are infinite lattice points, there must be a convergent subsequence, but the distance between any different two points in *L* is greater than or equal to λ1, which indicates that

$$|L \cap \text{Ball}(0, \delta)| \langle \infty, \,\, \delta \rangle \lambda\_i \rangle$$

has finite lattice points, it's not hard for us to find α1 ∈ *L* ⇒ |α1| = λ1, α2 ∈ *L* ⇒ |α2| = λ2,…,|α*n*| = λ*n*. The Corollary holds.

In Sect. 7.1, the geometry of numbers is relative to the integer lattice Z*n*; next, we extend the main results to the general full rank lattice.

**Lemma 7.19** (Compare with Lemma 7.5) *L* = *L*(*B*) ⊂ R*n is a lattice (full rank lattice), R* ⊂ R*n, if* Vol(*R*) > *d*(*L*)*, then there are two different points in R,* α ∈ *R,* β ∈ *R* ⇒ α − β ∈ *L.*

*Proof* Let *F* be a basic region of *L*, that is

$$F = \{ Bx | \mathbf{x} = (\mathbf{x}\_1, \dots, \mathbf{x}\_n), \mathbf{0} \le |\mathbf{x}\_i| < 1, \, 1 \le i \le n \}.$$

Obviously, R*n* can be divided into the following disjoint subsets,

$$\begin{aligned} \mathbb{R}^n &= \cup\_{\alpha \in L} \{\alpha + \mathbf{y} | \mathbf{y} \in F\}, \\ &= \cup\_{\alpha \in L} \{\alpha + F\}. \end{aligned}$$

For a given lattice point α ∈ *L*, define

$$
\mathcal{R}\_{\alpha} = \mathcal{R} \cap \{\alpha + F\} = \alpha + D\_{\alpha}, D\_{\alpha} \subset F.
$$

Therefore, *R* can be divided into the following disjoint subsets,

$$\mathcal{A} = \cup\_{a \in L} \mathcal{R}\_a,\\ \Rightarrow \text{Vol}(\mathcal{A}) = \sum\_{a \in L} \text{Vol}(\mathcal{R}\_a) = \sum\_{a \in L} \text{Vol}(D\_a).$$

If for any α, β ∈ *L*, α = β, *D*α ∩ *D*β = ∅, then

$$\text{Vol}(\mathcal{A}) = \text{Vol}(\cup\_{a \in L} D\_a) \le \text{Vol}(F) = d(L),$$

contradicts assumptions. So it must exist α, β ∈ *L*, α = β, =⇒ *D*α ∩ *D*β = ∅. Let *x* ∈ *D*α ∩ *D*β, then α + *x* ∈ *R*, β + *x* ∈ *R*. And

$$(\alpha + \mathfrak{x}) - (\beta + \mathfrak{x}) = \alpha - \beta \in L.\,\,\,\,$$

The Lemma holds.

**Lemma 7.20** (Compare with 7.6) *Let L be a full rank lattice, R* ⊂ R*n is a symmetric convex body. And* Vol(*R*) > 2*nd*(*L*)*, then R contains a nonzero lattice point, that is* ∃ α ∈ *L,* α = 0, *such that* α ∈ *R.*

*Proof* Let

$$\frac{1}{2}\mathcal{R} = \{\mathbf{x}|2\mathbf{x} \in \mathcal{R}\}.$$

Then

$$\text{Vol}\left(\frac{1}{2}\mathcal{R}\right) = 2^{-n}\text{Vol}(\mathcal{R}) > d(L).$$

By 7.19, there is *x* ∈ 1 2*R*, *y* ∈ 1 2*R*, =⇒ *x* − *y* ∈ *L*. And because 2*x* ∈ *R*, 2*y* ∈ *R*, *R* is a symmetric convex body, by Lemma 7.4,

#### 7.2 Basic Properties of Lattice 277

$$\frac{1}{2}(2x - 2y) = x - y \in \mathcal{R}.$$

The Lemma holds.

**Corollary 7.7** *Let L be a full rank lattice,* λ(*L*) = λ1 *is the minimum distance of L. Then*

$$
\lambda\_1 = \lambda(L) \le \sqrt{n} (d(L))^{\frac{1}{n}}.\tag{7.38}
$$

*Proof* First we prove

$$\text{Vol}(\text{Ball}(0, r)) \ge \left(\frac{2r}{\sqrt{n}}\right)^n. \tag{7.39}$$

This is because Ball(0,*r*) contains the following cubes

$$\left\{ \mathbf{x} \in \mathbb{R}^n | \mathbf{x} = (\mathbf{x}\_1, \dots, \mathbf{x}\_n), \forall \, |\mathbf{x}\_i| < \frac{r}{\sqrt{n}} \right\} \subset \text{Ball}(0, r).$$

By the definition, there are no nonzero lattice points in open ball Ball(0, λ1), by Lemma 7.20, because Ball(0, λ1) is a symmetrical convex body, there is

$$\text{Vol}(\text{Ball}(0, \lambda\_1)) \le 2^n d(L).$$

Thus

$$\left(\frac{2\lambda\_1}{\sqrt{n}}\right)^n \le 2^n d(L).$$

That is

$$
\lambda\_1 \le \sqrt{n} (d(L))^{\frac{1}{n}}.
$$

The Corollary holds.

Combined with Eq. (7.37), we obtain the estimation of the upper and lower bounds of the minimum distance of a lattice,

$$\min\_{1 \le i \le n} |\beta\_i^\*| \le \lambda(L) \le \sqrt{n} (d(L))^{\frac{1}{n}}.\tag{7.40}$$

**Lemma 7.21** *Let L* ⊂ R*n be a lattice (full rank lattice),* λ1, λ2,...,λ*n is the continuous minimum of L, d* = *d*(*L*) *is the determinant of L, then*

$$
\lambda\_1 \lambda\_2 \dots \lambda\_n \le n^{\frac{n}{2}} d(L). \tag{7.41}
$$

*Proof* Let {α1, α2,...,α*n*} ⊂ *L*, and |α*i*| = λ*i* is a set of bases of R*n*. Let

$$T = \left\{ \mathbf{y} \in \mathbb{R}^n | \sum\_{i=1}^n \left( \frac{\langle \mathbf{y}, \alpha\_i^\* \rangle}{\lambda\_i |\alpha\_i^\*|} \right)^2 < 1 \right\},\tag{7.42}$$

where {α∗ 1 , α∗ 2 ,...,α∗ *n* } is the orthogonal basis corresponding to {α1, α2,...,α*n*}. Let's prove that *T* does not contain any nonzero lattice points. Let *y* ∈ *L*, *y* = 0, let *k* be the largest subscript so that |*y*| ≥ λ*k* , then

$$\mathbf{y} \in \text{Span}(\alpha\_1^\*, \alpha\_2^\*, \dots, \alpha\_k^\*) = \text{Span}(\alpha\_1, \alpha\_2, \dots, \alpha\_k).$$

Because if *y* is linearly independent of α1, α2,...,α*k* , then

$$k+1 \le \dim(\text{Span}(\alpha\_1, \alpha\_2, \dots, \alpha\_k, \text{y}) \cap \text{Ball}(\mathbf{0}, |\mathbf{y}|)).$$

λ*k*+1 ≤ |*y*| is obtained from the definition of λ*k*+1, which contradicts the definition of *k*. By *y* ∈ Span(α1, α2,...,α*k* ),

$$\sum\_{i=1}^{n} \left( \frac{\langle \mathbf{y}, \alpha\_i^\* \rangle}{\lambda\_i |\alpha\_i^\*|} \right)^2 = \sum\_{i=1}^{k} \left( \frac{\langle \mathbf{y}, \alpha\_i^\* \rangle}{\lambda\_i |\alpha\_i^\*|} \right)^2$$

$$\geq \frac{1}{\lambda\_k^2} \sum\_{i=1}^{k} \frac{\langle \mathbf{y}, \alpha\_i^\* \rangle^2}{|\alpha\_i^\*|^2} = \frac{1}{\lambda\_k^2} |\mathbf{y}|^2 \geq 1.$$

Therefore *y* ∈/ *T* , by Lemma 7.20, because *T* is a symmetric convex body, thus

$$\text{Vol}(T) \le 2^n d.$$

On the other hand,

$$\begin{aligned} \text{Vol}(T) &= \left(\prod\_{i=1}^n \lambda\_i\right) \cdot \text{Vol}(\text{Ball}(0, 1)) \\ &\geq \prod\_{i=1}^n \lambda\_i \left(\frac{2}{\sqrt{n}}\right)^n. \end{aligned}$$

So

$$\prod\_{i=1}^n \lambda\_i \le n^{\frac{\pi}{2}} d.$$

Lemma 7.21 holds.

The above lemma shows that the upper bound (7.38) of λ1 is valid for λ*i* in the sense of geometric average.

Finally, we discuss the computational difficulties on the lattice. These problems are the main scientific basis and technical support in the design of trap gate function, and they are also the cornerstone of the security of lattice cryptography.

#### 1. Shortest vector problem SVP

Lattice *L* is a discrete geometry in R*n*, we know that its minimum distance λ1 = λ(*L*) is the length of the shortest vector in *L*. How to find its shortest vector *u*0 ∈ *L*

for any full rank lattice *L*, =⇒

$$|\mu\_0| = \min\_{\mathbf{x} \in L, \mathbf{x} \neq \mathbf{0}} |\mathbf{x}| = \lambda\_1.$$

It is the so-called shortest vector calculation problem. At present, there are insurmountable difficulties in theory and calculation, because we only know the existence of *u*0, but we can't calculate *u*0. Second, the current main research focuses on the approximation of the shortest vector. The so-called shortest vector approximation is to find a nonzero vector *u* ∈ *L* on *L*, =⇒

$$|u| \le r(n)\lambda\_1, \ u \in L, u \ne 0,$$

where *r*(*n*) ≥ 1 is called the approximation coefficient, which only depends on the dimension of lattice *L*.

In 1982, H. W. Lenstra, A. K. Lenstra and L. Lovasz creatively developed a set of algorithms in (1982) to effectively solve the approximation problem of the shortest vector, which is the famous LLL algorithm in lattice theory. The computational complexity of LLL algorithm is polynomial for the whole lattice, and the approximation coefficient *r*(*n*) = 2 *n*−1 2 . How to improve the approximation coefficient in LLL algorithm to the polynomial coefficient of *n* is the main research topic at present. For example, Schnorr's work in 1987 and Gama and Nguyen's work (2008a, 2008b) are very representative, but they are still far from the polynomial function, so the academic circles generally speculate:

Conjecture 1: there is no polynomial algorithm that can approximate the shortest vector so that the approximation coefficient *r*(*n*) is a polynomial function of *n*.

#### 2. Closest vector problem CVP

Let *L* ⊂ R*n* be a lattice, *t* ∈ R*n* is an arbitrary given vector, and it is easy to prove that there is a lattice point *ut* ∈ *L*, =⇒

$$|u\_t - t| = \min\_{\mathbf{x} \in L} |\mathbf{x} - t|,$$

*ut* is called the nearest lattice point (vector) of *t*. When *t* = 0 is a zero vector, *u*0 is the shortest vector of *L*, so the adjacent vector problem is a general form of the shortest vector problem. Similarly, we only know the existence of the adjacent vector *ut* , and there is no definite algorithm to find *ut* instead of the approximation problem of the adjacent vector, *x* ∈ *L*, if

$$|x - t| \le r\_1(n)|u\_t - t|,$$

then *x* is called the approximation coefficient, which is the approximation adjacent vector of *r*1(*n*), in 1986, Babai proposed an effective algorithm to approximate the adjacent vector in Babai (1986), and its approximation coefficient *r*1(*n*) is generally of the same order as the approximation coefficient *r*(*n*) of the shortest vector.

There are many other difficult computational problems on lattice, such as the Successive Shortest vector problem, which is essentially to find a deterministic algorithm to approximate each α*i* ∈ *L*, where |α*i*| = λ*i* is the continuous minimum of *L*. However, SVP and CVP are commonly used in lattice cryptosystem design and analysis, and most of the research is based on the integer lattice.

# **7.3 Integer Lattice and** *q***-Ary Lattice**

**Definition 7.7** A full rank lattice *L* is called an integer lattice, if *L* ⊂ Z*n*, an integer lattice *L* is called a *q*-ary lattice, if *q*Z*n* ⊂ *L* ⊂ Z*n*, where *q* ≥ 1 is a positive integer.

It is easy to see from the definition that a lattice *L* = *L*(*B*) is an integer lattice ⇔ *B* ∈ Z*n*×*n* is an integer square matrix, so the determinant *d* = *d*(*L*) of an entire lattice *L* is a positive integer.

**Lemma 7.22** *Let L* = *L*(*B*) ⊂ Z*n be an integer lattice, d* = *d*(*L*)*is the determinant of L, then d*Z*n* ⊂ *L* ⊂ Z*n, therefore, an integer lattice is always a d-ary lattice* (*d* = *q*)*.*

*Proof* Let α ∈ *d*Z*n*, let's prove that α ∈ *L*, that is, α = *Bx* always has the solution of the entire vector *x* ∈ Z*n*.  Because *B* ∈ Z*n*×*n*, so *B*∗ ∈ Z*n*×*n*, thus *d B*−1 = ±*B*∗ ∈ Z*n*×*n*, write α = *d*β, then β ∈ Z*n*, and

$$\alpha = B^{-1}\alpha = dB^{-1}\beta = \pm B^\*\beta \in \mathbb{Z}^n.$$

Thus α ∈ *L*. That is *d*Z*n* ⊂ *L*, the Lemma holds.

The following lemma is a simple conclusion in algebra. For completeness, we prove the following.

**Lemma 7.23** *Let L be a q-ary lattice,* Z*q is the residual class rings* mod *q, then*

*Proof* α = (*a*1, *a*2,..., *an*) ∈ Z*n*, β = (*b*1, *b*2,..., *bn*) ∈ Z*n*, if ∀ *ai* ≡ *bi*(mod *q*), we write α ≡ β(mod *q*). For any α ∈ Z*n*, define

$$
\bar{\alpha} = (\bar{a}\_1, \bar{a}\_2, \dots, \bar{a}\_n) \in \mathbb{Z}\_q^n,
$$

where *a*¯*i* is the minimum nonnegative residue of *ai* mod *q*, and thus, we have α ≡ α(¯ mod *q*). Define mapping σ : Z*n* σ −→ Z*n q* as σ (α) = ¯α, this is a surjection, and

$$
\sigma(\alpha + \beta) = \bar{\alpha} + \bar{\beta} = \sigma(\alpha) + \sigma(\beta).
$$

Therefore, σ is a full group homomorphism. Obviously Kerσ = *q*Z*n*, therefore, by the isomorphism theorem of groups, we have

$$
\mathbb{Z}^n / q \mathbb{Z}^n \cong \mathbb{Z}\_q^n.
$$

Because of *q*Z*n* ⊂ *L* ⊂ Z*n*, then by the isomorphism theorem of groups,

$$\mathbb{Z}^{n}/\mathbb{L} \cong \mathbb{Z}^{n}/q\mathbb{Z}^{n}/\mathbb{L}/q\mathbb{Z}^{n} \cong \mathbb{Z}\_{q}^{n}/\mathbb{L}/q\mathbb{Z}^{n}.$$

The Lemma holds.

Next, we will prove that Z*n*/*L* is a finite group. Therefore, we first discuss the elementary transformation of matrix. The so-called elementary transformation of matrix refers to elementary row transformation and elementary column transformation, specifically refers to the following three kinds of elementary transformations:

(1) Transform two rows or two columns of matrix *A*:

 σ*i j*(*A*)-Transform rows *i* and *j* of *A* τ*i j*(*A*)-Transform columns *i* and *j* of *A*

(2) A row or column multiplied by −1 by *A*:

 σ−*i*(*A*)-Multiply row *i* of *A* by − 1 τ−*i*(*A*)-Multiply column *i* of *A* by − 1

(3) Add the *k* times of a row (column) to another row (column), *k* ∈ R, in many cases, we require *k* ∈ Z to be an integer:

> σ*ki*+ *j*(*A*)-Add *k* times of row *i* of *A* to row *j* τ*ki*+ *j*(*A*)-Add *k* times of column *i* of *A* to column *j*

The *n*-order identity matrix is represented by *In*, the matrix obtained by the above elementary transformation of *In* is called elementary matrix. We note that all elementary matrices are unimodular matrices (see (7.29)), and

$$\begin{cases} \sigma\_{ij}(A) = \sigma\_{ij}(I\_n)A, \ \mathsf{τ}\_{ij}(A) = A\mathsf{τ}\_{ij}(I\_n) \\ \sigma\_{-i}(A) = \sigma\_{-i}(I\_n)A, \ \mathsf{τ}\_{-i}(A) = A\mathsf{τ}\_{-i}(I\_n) \\ \sigma\_{ki+j}(A) = \sigma\_{ki+j}(I\_n)A, \ \mathsf{τ}\_{ki+j}(A) = A\mathsf{τ}\_{ki+j}(I\_n) \end{cases} \tag{7.43}$$

That is, elementary row transformation for *A* is equal to multiplying the corresponding elementary matrix from the left, and elementary column transformation for *A* is equal to multiplying the corresponding elementary matrix from the right.

**Lemma 7.24** *Let L* = *L*(*B*) ⊂ Z*n be an integer lattice, then* Z*n*/*L is a finite group, and*

$$|\mathbb{Z}^n/L| = d(L).$$

*Proof* According to the knowledge of linear algebra, an integer square matrix *B* ∈ Z*n* can always be transformed into a lower triangular matrix by elementary row transformation; that is, there is a unimodular matrix *U* ∈ *SLn*(Z), so that

$$UB = \begin{bmatrix} \* & 0 & \cdots & 0 \\ \* & \* & \cdots & 0 \\ \cdot & \cdot & \cdot & \cdot & \cdots \\ \* & \* & \cdots & \cdot & \ast \end{bmatrix}.$$

Then the elementary column transformation of *U B* can always be transformed into an upper triangular matrix, so it is a diagonal matrix; that is, there is a unimodular matrix *U*1 ∈ *SLn*(Z),⇒

$$UBU\_1 = \text{diag}\{\delta\_1, \delta\_2, \dots, \delta\_n\}.$$

where δ*i* = 0, δ*i* ∈ Z, and

$$d(L) = |\det(UBU\_1)| = \prod\_{i=1}^{n} |\delta\_i|.$$

Let *L*(*U BU*1) be an integral lattice generated by *U BU*1, we have quotient group isomorphism

$$\mathbb{Z}^n/L(UBU\_1) \cong \oplus\_{i=1}^n \mathbb{Z}/|\delta\_i|\mathbb{Z} = \oplus\_{i=1}^n \mathbb{Z}\_{|\delta\_i|}.$$

Thus

$$|\mathbb{Z}^n/L(UBU\_1)| = \prod\_{i=1}^n |\delta\_i| = d(L).$$

Because of *L*(*B*) = *L*(*BU*1) and *L*(*B*) ∼= *L*(*U B*), Thus *L*(*B*) ∼= *L*(*U BU*1), so

$$|\mathbb{Z}^n/L(B)| = |\mathbb{Z}^n/L(UBU\_1)| = d(L).$$

Lemma 7.24 holds.

An integer square matrix *B* = (*bi j*)*n*×*n* ∈ Z*n*×*n* is called Hermite normal form matrix, if *B* is an upper triangular matrix, that is *bi j* = 0, 1 ≤ *j* < *i* ≤ *n*, and

$$b\_{li} \ge 1, 0 \le b\_{lj} < b\_{li}, \; 1 \le i < j \le n. \tag{7.44}$$

A Hermite normal form matrix, referred to as HNF matrix.

**Definition 7.8** *L* = *L*(*B*) ⊂ Z*n* is an integer lattice, and *B* is the HNF matrix, which is called the HNF basis of *L*, denote as *B* = HNF(*L*).

The following lemma proves that a whole lattice has a unique HNF basis, so it is reasonable to use HNF(*L*) to represent HNF basis.

**Lemma 7.25** *Let L* ⊂ Z*n be an integer lattice, then there is a unique HNF matrix B* ⇒ *L* = *L*(*B*)*.*

*Proof* Let *L* = *L*(*A*), *A* is the generating matrix of *L*, by using the elementary column transformation, *A* can be transformed into an upper triangular matrix, that is

$$AU\_1 = \begin{bmatrix} c\_{11} \ c\_{12} \ \cdots \ c\_{1n} \\ 0 \ c\_{22} \ \cdots \ c\_{2n} \\ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \\ 0 \ 0 \ \cdots \ c\_{nn} \end{bmatrix}, \quad U\_1 \in SLn(\mathbb{Z})\dots$$

where *Cii* > 0, 1 ≤ *i* ≤ *n*, if *AU*1 is transformed continuously, there is a unimodular matrix *U*2,⇒ *AU*1*U*2 = *B* is the HNF matrix, because *L*(*B*) = *L*(*AU*1*U*2), know that *L* has HNF base *B*.

Let's prove the uniqueness of HNF base *B* if there are two HNF matrices *B*1,*B*2 ⇒ *L*(*B*1) = *L*(*B*2), then from Lemma 7.14, there is a unimodular matrix *U* ∈ *SLn*(Z) such that *B*1 = *B*2*U*; that is, the elementary column transformation defined by formula (7.43) can be continuously implemented on *B*2 to obtain *B*1, but for *B*2, any column transformation τ*i j* ,τ−*i* and τ*ki*+ *j* is not a HNF matrix, so *U* = *In* is a unit matrix, that is *B*1 = *B*2. The Lemma holds.

**Lemma 7.26** *Let L* = *L*(*B*) *be an integer lattice, B* = (*bi j*)*n*×*n is a HNF matrix, B*∗ = [β∗ 1 , β∗ 2 ,...,β∗ *n* ]*is the orthogonal basis corresponding to B* = [β1, β2,...,β*n*]*, then*

$$B^\* = [\beta\_1^\*, \beta\_2^\*, \dots, \beta\_n^\*] = \text{diag}\{b\_{11}, b\_{22}, \dots, b\_{nn}\}$$

*is a diagonal matrix.*

*Proof* We prove β∗ *i* = (0, 0,..., *bii*, 0,..., 0) , induction of *i*, when *i* = 1, β∗ 1 = β1 = (*b*11, 0,..., 0) . The proposition holds, if for *j* ≤ *i*, there isβ∗ *j* = (0, 0,..., *bj j*, 0,..., 0) holds, then when *i* + 1, by (7.31), there is

.

$$\begin{aligned} \boldsymbol{\beta}\_{i+1}^{\*} &= \boldsymbol{\beta}\_{i+1} - \sum\_{j=1}^{i} \frac{\langle \beta\_{i+1}, \beta\_{j}^{\*} \rangle}{|\beta\_{j}^{\*}|^{2}} \boldsymbol{\beta}\_{j}^{\*} \\ &= \beta\_{i+1} - \sum\_{j=1}^{i} \frac{b\_{j(i+1)}}{b\_{jj}} \boldsymbol{\beta}\_{j}^{\*} \\ &= \begin{pmatrix} b\_{1(i+1)} \\ b\_{2(i+1)} \\ \vdots \\ b\_{(i+1)} \\ b\_{(i+1)(i+1)} \\ \vdots \\ b\_{(i+1)(i+1)} \\ 0 \end{pmatrix} - \begin{pmatrix} b\_{1(i+1)} \\ b\_{2(i+1)} \\ \vdots \\ b\_{(i+1)} \\ 0 \\ \vdots \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ \vdots \\ 0 \\ b\_{(i+1)l(i+1)} \\ \vdots \\ 0 \end{pmatrix} \end{aligned}$$

Thus the proposition holds.

Next, we discuss *q*-ary lattices, where *q* ≥ 1 is a positive integer, the following two *q*-ary lattices are often used in lattice cryptosystems.

**Definition 7.9** Let Z*q* be a residue class ring mod *q*, *A* ∈ Z*n*×*m q* , the following two *q*-ary lattices are defined as

$$\Lambda\_q(A) = \{ \mathbf{y} \in \mathbb{Z}^m | \text{there is } \mathbf{x} \in \mathbb{Z}^n \Rightarrow \mathbf{y} \equiv A^\prime \mathbf{x} (\text{mod } q) \}, \tag{7.45}$$

and

$$\Lambda\_q^\perp(A) = \{ \mathbf{y} \in \mathbb{Z}^m | A \mathbf{y} \equiv \mathbf{0} (\text{mod } q) \}. \tag{7.46}$$

By the definition: *q* (*A*) ⊂ Z*m* and ⊥ *q* (*A*) ⊂ Z*m* is an *m*-dimensional integer lattice. And any α ∈ *q*Z*m*, then there is *x* = 0 ∈ Z*m*,⇒ α ≡ *A x*(mod *q*), and *A*α ≡ 0(mod *q*), there is

$$\begin{cases} q\mathbb{Z}^m \subset \Lambda\_q(A) \subset \mathbb{Z}^m\\ q\mathbb{Z}^m \subset \Lambda\_q^\perp(A) \subset \mathbb{Z}^m \end{cases}$$

That is, *q* (*A*) and ⊥ *q* (*A*) are *q*-element lattices of dimension *m*.

**Lemma 7.27** *We have*

$$\begin{cases} \Lambda\_q^\perp(A) = q \Lambda\_q(A)^\* \\ \Lambda\_q(A) = q \Lambda\_q^\perp(A)^\* \end{cases}$$

*Proof* Any α ∈ *q* (*A*)∗, by the definition, then

$$
\langle \mathbf{y}, \boldsymbol{\alpha} \rangle \in \mathbb{Z}, \forall \, \mathbf{y} \in \Lambda\_q(A).
$$

And

$$
\langle \mathbf{y}, \boldsymbol{\alpha} \rangle = \mathbf{y}^{\prime} \boldsymbol{\alpha} \in \mathbb{Z} \Rightarrow \mathbf{y}^{\prime} \boldsymbol{\alpha} \equiv \mathbf{0} (\text{mod } \mathbf{1}) .
$$

There is

$$
\text{y } q\alpha \equiv 0 \\
\text{(mod } q), \forall \text{ y } \in \Lambda\_q(A).
$$

Because *y* ∈ *q* (*A*), thus there is *x* ∈ Z*n* ⇒ *y* ≡ *A x*(mod *q*), from the above formula,

$$\text{a}^{'}Aq\alpha \equiv 0(\text{mod}\,q), \forall \,\text{x} \in \mathbb{Z}^{n}.$$

Thus

$$Aq\alpha \equiv 0(\text{mod}\,q), \Rightarrow q\alpha \in \Lambda\_q^{\perp}(A).$$

We prove

$$q\Lambda\_q(A)^\* \subset \Lambda\_q^\perp(A).$$

Conversely, if *y* ∈ ⊥ *q* (*A*), we have

$$A\mathbf{y} \equiv \mathbf{0} (\text{mod } q) \Rightarrow A\left(\frac{1}{q}\mathbf{y}\right) \equiv \mathbf{0} (\text{mod } \mathbf{l}) .$$

Any α ∈ *q* (*A*), let *x* ∈ Z*n*, α ≡ *A x*(mod *q*), then

$$\left\langle \alpha, \frac{1}{q} \mathbf{y} \right\rangle = \mathbf{x}' A \left( \frac{1}{q} \mathbf{y} \right) \equiv \mathbf{0} (\text{mod } 1), \forall \, \mathbf{x} \in \mathbb{Z}^n.$$

We have

$$\frac{1}{q}\mathbf{y} \in \Lambda\_q(A)^\* \Rightarrow \mathbf{y} \in q\Lambda\_q(A)^\*.$$

That is

$$
\Lambda\_q^\perp(A) \subset q \Lambda\_q(A)^\*.
$$

Thus, ⊥ *q* (*A*) = *q q* (*A*)∗. Similarly, the second equation can be proved.

**Lemma 7.28** *Let q be a prime, A* ∈ Z*n*×*m q* , *m* ≥ *n, and* rank(*A*) = *n, then*

$$|\det(\Lambda\_q^\perp(A))| = q'',\tag{7.47}$$

*and*

$$|\det(\Lambda\_q(A))| = q^{m-n}.\tag{7.48}$$

*Proof* In finite field Z*q* , rank(*A*) = *n*, then the linear equation system *Ay* = 0 has exactly *qm*−*n* solutions, from which we can get

$$|\Lambda\_q^\perp(A)/q\mathbb{Z}^m| = q^{m-n}.$$

By Lemma 7.23,

$$|\mathbb{Z}^m/\Lambda\_q^\perp(A)| = |\mathbb{Z}\_q^m/\Lambda\_q^\perp(A)/q\mathbb{Z}^m| = q^n.$$

By Lemma 7.24,

$$|\det(\Lambda\_q^\perp(A))| = |\mathbb{Z}^m/\Lambda\_q^\perp(A)| = q^n.$$

So (7.47) holds. By Corollary 7.5 of the previous section, we have

$$|\det(\Lambda\_q^\perp(A)^\*)| = q^{-n}.$$

By Lemma 7.27,

$$|\det(\Lambda\_q(A))| = q^m |\det(\Lambda\_q^\perp(A)^\*)| = q^{m-n}.$$

The Lemma holds.

# **7.4 Reduced Basis**

In lattice theory, Reduced basis and corresponding LLL algorithm are the most important contents, which have an important impact on computational algebra, computational number theory and other neighborhoods, and are recognized as one of the most important computational methods in recent 100 years. In order to introduce Reduced basis and LLL algorithm, we recall the gram Schmidt orthogonalization process summarized by Eqs. (7.31)–(7.34). Let {β1, β2,...,β*n*} ⊂ R*n* be a set of bases corresponding to R*n* , {β∗ 1 , β∗ 2 ,...,β∗ *n* } is the corresponding Gram–Schmidt orthogonal basis, where

$$
\beta\_1^\* = \beta\_1, \ \beta\_i^\* = \beta\_i - \sum\_{j=1}^{i-1} \frac{\langle \beta\_i, \beta\_j^\* \rangle}{\langle \beta\_j^\*, \beta\_j^\* \rangle} \beta\_j^\*, \ 1 < i \le n. \tag{7.49}
$$

The above formula can be written as

$$\beta\_i = \sum\_{j=1}^i \frac{\langle \beta\_i, \beta\_j^\* \rangle}{\langle \beta\_j^\*, \beta\_j^\* \rangle} \beta\_j^\*, \ 1 \le i \le n. \tag{7.50}$$

There is

**Lemma 7.29** *Let* {β1, β2,...,β*n*} *be a set of bases of* R*n,* {β∗ 1 , β∗ 2 ,...,β∗ *n* } *is the corresponding Gram–Schmidt orthogonal basis, L*(β1, β2,...,β*k* ) = Span{β1, β2, ...,β*k* } *is a linear subspace extended by* β1, β2,...,β*k , then*

*(i)*

$$L(\beta\_1, \beta\_2, \dots, \beta\_k) = L(\beta\_1^\*, \beta\_2^\*, \dots, \beta\_k^\*), \ 1 \le k \le n. \tag{7.51}$$

*(ii) For* 1 ≤ *i* ≤ *n, there is*

$$\begin{cases} \langle \beta\_i, \beta\_k^\* \rangle = 0, & \text{when } k > i;\\ \langle \beta\_i, \beta\_k \rangle = \langle \beta\_k^\*, \beta\_k^\* \rangle, & \text{when } k = i. \end{cases} \tag{7.52}$$

*(iii)* ∀ *x* ∈ R*n, x* = "*n i*=1 *xi*β∗ *i , then*

$$\chi\_i = \frac{\langle \mathbf{x}, \beta\_i^\* \rangle}{\langle \beta\_i^\*, \beta\_i^\* \rangle}, \ 1 \le i \le n. \tag{7.53}$$

*Proof* The above three properties can be derived directly from Eq. (7.49) or (7.50).

Let *U* = (*Ui j*)*n*×*n*, where

$$U\_{ij} = \frac{\langle \beta\_i, \beta\_j^\* \rangle}{\langle \beta\_j^\*, \beta\_j^\* \rangle}, \Rightarrow U\_{ij} = 0, \text{ when } j > i. \ U\_{ii} = 1. \tag{7.54}$$

Therefore, *U* is the lower triangular matrix with element 1 on the diagonal, and

$$
\begin{bmatrix}
\beta\_1\\\beta\_2\\\vdots\\\beta\_n
\end{bmatrix} = U \begin{bmatrix}
\beta\_1^\*\\\beta\_2^\*\\\vdots\\\beta\_n^\*
\end{bmatrix}.\tag{7.55}
$$

*U* is called the coefficient matrix when {β1, β2,...,β*n*} is orthogonalized.

Let's introduce the concept of orthogonal projection: suppose *V* ⊂ R*k* ⊂ R*n*(1 ≤ *k* ≤ *n*), the orthogonal complement space *V* ⊥ of *V* in R*k* is

$$V^{\perp} = \{ \mathfrak{x} \in \mathbb{R}^{k} | \langle \mathfrak{x}, \alpha \rangle = 0, \forall \, \alpha \in V \}. \tag{7.56}$$

Because R*k* = *V* ⊕ *V* ⊥, so ∀ *x* ∈ R*k* , the only can be expressed as

$$
\alpha = \alpha + \beta, \text{ where } \alpha \in V, \beta \in V^{\perp}.
$$

α is called the orthogonal projection of *x* on subspace *V*, obviously |*x*| 2 = |α| 2 + |β| 2.

**Lemma 7.30** *Let* {β1, β2,...,β*n*} *be a set of bases of* R*n and* {β∗ 1 , β∗ 2 ,...,β∗ *n* } *be the corresponding orthogonal basis,* 1 ≤ *k* ≤ *n, then* β∗ *k is the orthogonal projection of* β*k on the orthogonal complement space V of the subspace L*(β1, β2,...,β*k*−1) *of L*(β1, β2,...,β*k* )*.*

*Proof* When *k* = 1, the proposition is trivial, if *k* > 1, then by Lemma 7.29,

$$L(\beta\_1, \beta\_2, \dots, \beta\_{k-1}) = L(\beta\_1^\*, \beta\_2^\*, \dots, \beta\_{k-1}^\*).$$

Therefore, the orthogonal complement space *V* = *L*(β∗ *k* ) of *L*(β1, β2,...,β*k*−1) in *L*(β1, β2,...,β*k*−1, β*k* ) is a one-dimensional space, because of

$$
\beta\_k = \beta\_k^\* + \sum\_{j=1}^{k-1} \mu\_{kj} \beta\_j^\*,
$$

and

$$\left\langle \rho\_k^\*, \sum\_{j=1}^{k-1} \mu\_{kj} \rho\_j^\* \right\rangle = 0.1$$

So β∗ *k* is the orthogonal projection of β*k* on *V*. The Lemma holds.

Next, we discuss the transformation law of the corresponding orthogonal basis when making the elementary column transformation of the base matrix [β1, β2,...,β*n*].

**Lemma 7.31** *Let* {β1, β2,...,β*n*} ⊂ R*n is a set of bases,* {β∗ 1 , β∗ 2 ,...,β∗ *n* } *is the corresponding orthogonal basis, A* = (*ui j*)*n*×*n is the coefficient matrix. Exchange* β*k*−1 *with* β*k to get a set of bases* {α1, α2,...,α*n*} *of* R*n, where*

$$
\alpha\_{k-1} = \beta\_k, \alpha\_k = \beta\_{k-1}, \alpha\_i = \beta\_i, \text{when } i \neq k - 1, k.
$$

*Let* {α∗ 1 , α∗ 2 ,...,α∗ *n* } *be the corresponding orthogonal basis and A*1 = (v*i j*)*n*×*n be the corresponding coefficient matrix, then we have*

*(i)* α∗ *i* = β∗ *i , if i* = *k* − 1, *k*. *(ii)*

$$\begin{cases} \alpha\_{k-1}^\* = \beta\_k^\* + \mu\_{kk-1} \beta\_{k-1}^\* \\ \alpha\_k^\* = \beta\_{k-1}^\* - \upsilon\_{kk-1} \beta\_{k-1}^\*. \end{cases}$$

*(iii)* v*i j* = *ui j , if* 1 ≤ *j* < *i* ≤ *n, and* {*i*, *j*} + {*k*, *k* − 1} = ∅*. (iv)*

$$\begin{cases} v\_{ik-1} = \mu\_{ik-1} v\_{kk-1} + \mu\_{ik} \frac{|\beta\_k^\*|^2}{|\alpha\_{k-1}^\*|^2}, & i > k, \\ v\_{ik} = \mu\_{ik-1} - \mu\_{ik} \mu\_{kk-1}, & i > k. \end{cases}$$

*(v)* v*k*−1 *j* = *ukj ,*v*kj* = *uk*−1 *j*, 1 ≤ *j* < *k* − 1*.*

*Proof* If 1 ≤ *i* < *k* − 1, or *k* < *i* ≤ *n*, then the orthogonal complement space in *L*(α1, α2,...,α*i*) = *L*(β1, β2, ··· , β*i*),

$$V = L^\perp(\alpha\_1, \alpha\_2, \dots, \alpha\_{i-1}) = L^\perp(\beta\_1, \beta\_2, \dots, \beta\_{i-1}) .$$

Therefore, the orthogonal projection of α∗ *i* as α*i* = β*i* on *V* is the same as that of β∗ *i* as β*i* on *V*, that is α∗ *i* = β∗ *i* (*i* = *k* − 1, *k*), (i) holds.

To prove (ii), because α∗ *k*−1 is the orthogonal projection of β*k* (= α*k*−1) on the orthogonal complement space *L*(β∗ *k*−1) of *L*(β1, β2,...,β*k*−2), because of

$$\begin{aligned} \beta\_k^\* &= \beta\_k - \sum\_{j=1}^{k-1} \mu\_{kj} \beta\_j^\* \\ &= \beta\_k - \mu\_{kk-1} \beta\_{k-1}^\* - \sum\_{j=1}^{k-2} \mu\_{kj} \beta\_j^\*, \end{aligned}$$

and *L*(β1, β2,...,β*k*−2) = *L*(β∗ 1 , β∗ 2 ,...,β*k*−2)∗, there is

$$
\alpha\_{k-1}^\* = \beta\_k^\* + \mu\_{kk-1} \beta\_{k-1}^\*.
$$

Similarly, α∗ *k* is the orthogonal projection of β∗ *k*−1 on *L*(α∗ *k*−1), thus

$$
\alpha\_k^\* = \beta\_{k-1}^\* - \upsilon\_{kk-1} \alpha\_{k-1}^\*.
$$

where

$$\begin{split} \upsilon\_{kk-1} &= \frac{\langle \beta^\*\_{k-1}, \alpha^\*\_{k-1} \rangle}{|\alpha^\*\_{k-1}|^2} \\ &= \frac{\langle \beta^\*\_{k-1}, u\_{kk-1} \beta^\*\_{k-1} \rangle}{|\alpha^\*\_{k-1}|^2} \\ &= u\_{kk-1} \frac{|\beta^\*\_{k-1}|^2}{|\alpha^\*\_{k-1}|^2}, \end{split}$$

thus (ii) holds. Similarly, other properties can be proved. Lemma 7.31 holds.

**Lemma 7.32** *Let* {β1, β2,...,β*n*} *be a set of bases of* R*n,* {β∗ 1 , β∗ 2 ,...,β∗ *n* } *be the corresponding orthogonal basis, and A* = (*ui j*)*n*×*n be the coefficient matrix. For any k* ≥ 2*, if we replace* β*k with* β*k* − *r*β*k*−1 *and keep the other* β*i unchanged* (*i* = *k*)*, we get a new set of bases.*

$$\{\alpha\_1, \alpha\_2, \dots, \alpha\_n\} = \{\beta\_1, \beta\_2, \dots, \beta\_{k-1}, \beta\_k - r\beta\_{k-1}, \beta\_{k+1}, \dots, \beta\_n\}.$$

*Let* {α∗ 1 , α∗ 2 ,...,α∗ *n* } *be the corresponding orthogonal basis and A*1 = (v*i j*)*n*×*n the corresponding coefficient matrix, then we have*

*(i)* α∗ *i* = β∗ *i ,* ∀ 1 ≤ *i* ≤ *n, that is,* β∗ *i remains unchanged. (ii)* v*i j* = *ui j , if* 1 ≤ *j* < *i* ≤ *n, i* = *k*. *(iii)* v*kj* = *ukj* − *r uk*−1,*j*, if *j* < *k* − 1

$$\dot{\left(v\_{kk-1} - \dot{u}\_{kk-1} - r\right)} = \dot{u}\_{kk-1} - r, \quad \text{if } \dot{j} = k - 1.$$

*Proof* When *i* < *k*, or *i* > *k*, α∗ *i* = β∗ *i* is trivial, to prove (i), only prove when *i* = *k*. Because α∗ *k* is the orthogonal projection of α*k* = β*k* − *r*β*k*−1 in the orthogonal complement space *L*(α∗ *k* ) = *L*(β∗ *k* ) of *L*(β1, β2,...,β*k*−1) = *L*(α1, α2,...,α*k*−1),

$$\begin{aligned} \beta\_k^\* &= \beta\_k - \sum\_{j=1}^{k-1} \mu\_{kj} \beta\_j^\* \\ &= \beta\_k - r\beta\_{k-1} - \left(\sum\_{j=1}^{k-2} \mu\_{kj} \beta\_j^\* + (\mu\_{kk-1} - r)\beta\_{k-1}^\*\right), \\ &= \alpha\_k - \left(\sum\_{j=1}^{k-2} \mu\_{kj} \beta\_j^\* + (\mu\_{kk-1} - r)\beta\_{k-1}^\*\right). \end{aligned}$$

This proves that α∗ *k* = β∗ *k* . Thus (i) holds. To prove (ii), when *i* = *k*, we have

$$v\_{ij} = \frac{\langle \alpha\_i, \alpha\_j^\* \rangle}{|\alpha\_j^\*|^2} = \frac{\langle \beta\_i, \beta\_j^\* \rangle}{|\beta\_j^\*|^2} = \mu\_{ij},$$

that is (ii) holds. When *i* = *k*,

$$\begin{split} v\_{kj} &= \frac{\langle \alpha\_k, \alpha\_j^\* \rangle}{|\alpha\_j^\*|^2} \\ &= \frac{\langle \beta\_k - r\beta\_{k-1}, \beta\_j^\* \rangle}{|\alpha\_j^\*|^2} (1 \le j < k \le n) \\ &= \frac{\langle \beta\_k, \beta\_j^\* \rangle}{|\beta\_j^\*|^2} - r \frac{\langle \beta\_{k-1}, \beta\_j^\* \rangle}{|\beta\_j^\*|^2} \\ &= u\_{kj} - r u\_{k-1j} .\end{split}$$

The above formula holds for all 1 ≤ *j* ≤ *k* − 1, thus (iii) holds, the Lemma holds.

Next, we introduce the concept of a set of Reduced bases of R*n*.

**Definition 7.10** Let {β1, β2,...,β*n*} ⊂ R be a set of bases, {β∗ 1 , β∗ 2 ,...,β∗ *n* } be the corresponding orthogonal basis, *A* = (*ui j*)*n*×*n* be the coefficient matrix, and {β1, β2,...,β*n*−1} be a set of Reduced bases of R*n*, if

$$\begin{cases} \text{ (i) } |u\_{ij}| \le \frac{1}{2}, \forall \ 1 \le j < i \le n. \\\ \text{ (ii) } |\beta\_i^\* - u\_{kk-1}\beta\_{i-1}^\*|^2 \ge \frac{3}{4}|\beta\_{i-1}^\*|^2, \forall \ 1 < i \le n. \end{cases} \tag{7.57}$$

A set of Reduced bases of R*n* is sometimes called Lovisz Reduced bases, which is of great significance in lattice theory. The important result of this section is that any lattice *L* in R*n* has Reduced bases, and the method to calculate the Reduced bases is the famous LLL algorithm.

**Theorem 7.3** *Let L* ⊂ R*n be a lattice(full rank lattice), then there is a generating matrix B* = [β1, β2,...,β*n*] *of L, where* {β1, β2,...,β*n*} *is a Reduced basis of* R*n and will also be a Reduced basis of lattice L* = *L*(*B*)*.*

*Proof* Let *B* = [β1, β2,...,β*n*], *L* = *L*(*B*), first we prove

$$|u\_{kk-1}| \le \frac{1}{2}, \forall \ 1 \le k. \tag{7.58}$$

If there is a *k* > 1, then the above formula does not hold, let *r* be the nearest integer of *ukk*−1, obviously,

$$|\mu\_{kk-1} - r| \le \frac{1}{2}.$$

In {β1, β2,...,β*n*}, replace β*k* with β*k* − *r*β*k*−1, thus by Lemma 7.32,

$$
\mu\_{kj} \to \mu\_{kj} - r\mu\_{k-1j}, \ 1 \le j \le k.
$$

Specially, when *j* = *k* − 1,

$$
\mu\_{kk-1} \to \mu\_{kk-1} - r,
$$

under the new basis, all β*i* and *ui j*(1 ≤ *j* < *i* = *k*) remain unchanged, so Eq. (7.58) holds under the new basis.

In the second step of LLL algorithm, we prove that

$$|\beta\_k^\* - u\_{kk-1}\beta\_{k-1}^\*|^2 \ge \frac{3}{4}|\beta\_{k-1}^\*|^2, \forall \ 1 < k \le n. \tag{7.59}$$

By (7.4),

$$\left| \beta\_k^\* + \mu\_{kk-1} \beta\_{k-1}^\* \right|^2 = \left| \beta\_k^\* - \mu\_{kk-1} \beta\_{k-1}^\* \right|^2.$$

Therefore, the sign in the absolute value on the right of Eq. (7.59) can be changed arbitrarily. If there is a *k*, 1 < *k* ≤ *n* such that (7.59) does not hold, that is

$$\left| \beta\_k^\* + \mu\_{kk-1} \beta\_{k-1}^\* \right|^2 < \frac{3}{4} |\beta\_{k-1}^\*|^2. \tag{7.60}$$

In this case, if β*k* and β*k*−1 are exchanged and the other β*i* remains unchanged, there is a new set of bases {α1, α2,...,α*n*}, the corresponding orthogonal basis {α∗ 1 , α∗ 2 ,...,α∗ *n* } and the coefficient matrix *A*1 = (v*i j*)*n*×*n*, where

$$
\alpha\_i = \beta\_i(i \neq k - 1, k), \ \alpha\_{k-1} = \beta\_k, \ \alpha\_k = \beta\_{k-1}.
$$

Let's prove that under the new base {α1, α2,...,α*n*}, there is

$$\left|\alpha\_{k}^{\*} + \upsilon\_{kk-1}\alpha\_{k-1}^{\*}\right|^{2} \geq \frac{3}{4} \left|\alpha\_{k-1}^{\*}\right|^{2},\tag{7.61}$$

by Lemma 7.31,

$$\begin{cases} \alpha\_{k-1}^\* = \beta\_k^\* + \mu\_{kk-1} \beta\_{k-1}^\* \\ \alpha\_k^\* = \beta\_{k-1}^\* - \upsilon\_{kk-1} \beta\_{k-1}^\*. \end{cases}$$

By (7.60), we have

$$\left|\alpha\_{k-1}^\*\right|^2 < \frac{3}{4} |\alpha\_k^\* + \upsilon\_{kk-1} \alpha\_{k-1}^\*|^2.$$

That is

$$|\alpha\_k^\* + \upsilon\_{kk-1} \alpha\_{k-1}^\*|^2 > \frac{4}{3} |\alpha\_{k-1}^\*|^2 > \frac{3}{4} |\alpha\_{k-1}^\*|^2.$$

Thus (7.61) holds. Using the above method continuously, it can be proved that formula (7.59) is valid for ∀ *k* > 1, however, when *k* is replaced by *k* − 1, the new β∗ *k*−1 is replaced by

$$
\beta\_{k-1}^\* \to \beta\_{k-1}^\* + \mu\_{k-1k-2} \beta\_{k-2}^\* = \overline{\beta\_{k-1}^\*}.
$$

We have to prove (7.59), it remains unchanged when *k* − 1 is used instead of *k*. In fact,

$$\begin{split} |\beta\_{k}^{\*} + u\_{kk-1}\overline{\beta}\_{k-1}^{\*}|^{2} &= |\beta\_{k}^{\*} + u\_{kk-1}(\beta\_{k-1}^{\*} + u\_{k-1k-2}\beta\_{k-2}^{\*})|^{2} \\ &= |\beta\_{k}^{\*} + u\_{kk-1}\beta\_{k-1}^{\*}|^{2} + |u\_{kk-1}u\_{k-1k-2}\beta\_{k-2}^{\*}|^{2} \\ &\geq \frac{3}{4} (|\beta\_{k-1}^{\*}|^{2} + u\_{kk-1}^{2}|u\_{k-1k-2}\beta\_{k-2}^{\*}|^{2}) \\ &\geq \frac{3}{4} (|\beta\_{k-1}^{\*}|^{2} + |u\_{k-1k-2}\beta\_{k-2}^{\*}|^{2}) \\ &= \frac{3}{4} |\beta\_{k-1}^{\*} + u\_{k-1k-2}\beta\_{k-2}^{\*}|^{2} \\ &= \frac{3}{4} |\overline{\beta\_{k-1}^{\*}}|^{2}. \end{split}$$

Therefore, Eq. (7.59) does not change when the transformation of commutative vector is carried out continuously; that is, Eq. (7.59) holds for all *k*, 1 < *k* ≤ *n*.

The third step of the LLL algorithm, let's prove that

$$|\mu\_{kj}| \le \frac{1}{2}, \forall \ 1 \le j \prec k \le n. \tag{7.62}$$

When *j* = *k* − 1, (7.58) is the (7.62). For given *k*, 1 < *k* ≤ *n*, if (7.62) does not hold, let *l* be the largest subscript ⇒ |*ukl*| > 1 2 . Let *r* be the nearest integer to *ukl* , then |*ukl* − *r*| ≤ 1 2 . Replace β*k* with β*k* − *r*β*l* , from Lemma 7.32, all β∗ *i* remain unchanged and the coefficient matrix is changed to:

$$\begin{aligned} \boldsymbol{u}\_{kj} &= \boldsymbol{u}\_{kj} - r\boldsymbol{u}\_{lj}, \; 1 \le j < l, \\ \boldsymbol{u}\_{kl} &= \boldsymbol{u}\_{kl} - r. \end{aligned}$$

While the other *ui j* remains unchanged, at this time,

$$|\mu\_{kl} - r| = |v\_{kl}| \le \frac{1}{2}.$$

So we have Eq. (7.62) for all 1 ≤ *j* < *k* ≤ *n*.

The above matrix transformation is equivalent to multiplying a unimodular matrix from the right, so the Reduced basis *B* ⇒ *L* = *L*(*B*) of lattice *L* is finally obtained. We complete the proof of Theorem 7.3.

**Lemma 7.33** *Let L* = *L*(*B*) *be a lattice, B is a Reduced basis of L, and B*∗ = [β∗ 1 , β∗ 2 ,...,β∗ *n* ] *is the corresponding orthogonal basis, then for any* 1 ≤ *j* < *i* ≤ *n, we have*

$$|\beta\_j^\*|^2 \le 2^{i-j} |\beta\_i^\*|^2.$$

*Proof* Because *B* = [β1, β2,...,β*n*] is a Reduced basis, then

$$\left|\beta\_k^\* + \mu\_{kk-1} \beta\_{k-1}^\*\right|^2 \ge \frac{3}{4} |\beta\_{k-1}^\*|^2.$$

Thus

$$|\beta\_k^\* + u\_{kk-1}\beta\_{k-1}^\*|^2 = |\beta\_k^\*|^2 + u\_{kk-1}^2|\beta\_{k-1}^\*|^2 \ge \frac{3}{4}|\beta\_{k-1}^\*|^2.$$

There is

$$\begin{aligned} |\beta\_k^\*|^2 &= \frac{3}{4} |\beta\_{k-1}^\*|^2 - \mu\_{kk-1}^2 |\beta\_{k-1}^\*|^2 \\ &\ge \frac{3}{4} |\beta\_{k-1}^\*|^2 - \frac{1}{4} |\beta\_{k-1}^\*|^2 \\ &= \frac{1}{2} |\beta\_{k-1}^\*|^2. \end{aligned}$$

So when 1 ≤ *j* < *i* ≤ *n* given, we have

$$\begin{aligned} |\beta\_i^\*|^2 &\geq \frac{1}{2} |\beta\_{i-1}^\*|^2 \\ &\geq \frac{1}{4} |\beta\_{i-2}^\*|^2 \\ &\geq \dotsb \\ &\geq 2^{-(i-j)} |\beta\_j^\*|^2, \end{aligned}$$

thus

$$|\beta\_j^\*|^2 \le 2^{i-j} |\beta\_i^\*|^2.$$

*Remark 7.3* In the definition of Reduced base, the coefficient 3 4 on the left of the second inequality of (7.57) can be replaced by any δ, where 1 4 <δ< 1. Specially, Babai pointed out in (1986) that the second inequality of Eq. (7.57) can be replaced by the following weaker inequality,

$$|\beta\_i^\*| \le \frac{1}{2} |\beta\_{i-1}^\*|. \tag{7.63}$$

Let's discuss the computational complexity of the LLL algorithm. Let *B* = {β1, β2,...,β*n*} be any set of bases, for any 0 ≤ *k* ≤ *n*, we define

$$d\_0 = 1,\\ d\_k = \det(\langle \beta\_i, \beta\_j \rangle\_{k \times k}). \tag{7.64}$$

If {β∗ 1 , β∗ 2 ,...,β∗ *n* } is the orthogonal basis corresponding to {β1, β2,...,β*n*}, there is obviously

$$d\_k = \prod\_{i=1}^k |\beta\_i^\*|^2, 0 < k \le n. \tag{7.65}$$

Thus, *di* is a positive number, and *dn* = *d*(*L*)2. Let

$$D = \prod\_{k=1}^{n-1} d\_k,\tag{7.66}$$

We first prove that *dk* (0 < *k* ≤ *n*) and *D* have lower bounds.

#### **Lemma 7.34** *Let*

$$m(L) = \lambda(L)^2 = \min\{|x|^2 : x \in L, x \neq 0\}.$$

*Then*

$$d\_k \ge \left(\frac{3}{4}\right)^{\frac{k(k-1)}{2}} m(L)^k, \ 1 \le k \le n.$$

*Proof* The determinant of *k*-dimensional lattice *Lk* = *L*(β1, β2,...,β*k* ) ⊂ R*k* (1 ≤ *k* ≤ *n*) has

$$d^2(L\_k) = d\_k.$$

By the conclusion of Cassels (1971), there is a nonzero lattice point *x* in *Lk* , which satisfies *x* ∈ *Lk* , *x* = 0, and

$$|\mathbf{x}|^2 \le \left(\frac{4}{3}\right)^{\frac{k-1}{2}} d\_k^{\frac{1}{k}}.\tag{7.67}$$

Then

$$\begin{aligned} d\_k &\geq \left(\frac{3}{4}\right)^{\frac{k(k-1)}{2}} m(L\_k)^k\\ &\geq \left(\frac{3}{4}\right)^{\frac{k(k-1)}{2}} (m(L))^k. \end{aligned}$$

The Lemma holds.

Another important conclusion of this section is that for the integer lattice *L* estimation, the computational complexity of the Reduced basis of the integer lattice is obtained by using the LLL algorithm. We prove that the LLL algorithm on the integer lattice is polynomial.

**Theorem 7.4** *Let L* = *L*(*B*) ⊂ Z*n be an integer lattice, B* = [β1, β2,...,β*n*] *is the generating matrix, suppose N satisfies*

$$\max\_{1 \le i \le n} \left| \beta\_i \right|^2 \le N.$$

*Then the computational complexity of the Reduced basis of L obtained by B using the LLL algorithm is*

$$\text{Time}(\text{LLL algorithm}) = O(n^4 \log N).$$

*The binary digits of all integers in the LLL algorithm are O*(*n* log *N*)*, so the computational complexity of the LLL algorithm on the integer lattice is polynomial.*

*Proof* By (7.36), we have

$$|\beta\_i^\*| \le |\beta\_i|, \ 1 \le i \le n.$$

where {β∗ 1 , β∗ 2 ,...,β∗ *n* } is the orthogonal basis corresponding to {β1, β2,...,β*n*}, then by (7.65) and (7.66), we have

$$d\_k = \prod\_{i=1}^k |\beta\_i^\*|^2 \le \prod\_{i=1}^k |\beta\_i|^2 \le N^k, 1 \le k \le n.$$

And

$$1 \le D \le N^{\frac{n(n-1)}{2}}.\tag{7.68}$$

The inequality on the left of the above formula is because of *dk* ∈ Z, and *dk* ≥ 1, by (7.66), then *D* ≥ 1. Therefore, *O*(*n*) arithmetic operations are required in the first step of the LLL algorithm, *O*(*n*3) arithmetic operations are required in the second and third steps, and the number of bit operations per algorithm operation is ≤ Time (calculate *D*), thus

$$\text{Time}(\text{LLL algorithm}) \le O(n^3)\\ \text{Time}(\text{calculate } D) = O(n^4 \log N)...$$

Therefore, the first conclusion of Theorem 7.4 is proved. The second conclusion is more complex, we will omit it. Interested readers can refer to the original (1982) of A. K. Lenstra, H. W. Lenstra and L. Lovasz.

# **7.5 Approximation of SVP and CVP**

The most important application of lattice Reduced basis and LLL algorithm is to provide approximation algorithms for the shortest vector problem and the shortest adjacent vector problem, and obtain some approximate results. Firstly, we prove the following Lemma.

**Lemma 7.35** *Let*{β1, β2,...,β*n*} *be a Reduced basis of a lattice L,*{β∗ 1 , β∗ 2 ,...,β∗ *n* } *be the corresponding orthogonal basis, and d*(*L*) *be the determinant of L, then we have*

*(i)*

$$d(L) \le \prod\_{i=1}^{n} |\beta\_i| \le 2^{\frac{n(n-1)}{4}} d(L). \tag{7.69}$$

*(ii)*

$$|\beta\_1| \le 2^{\frac{n-1}{4}} d(L)^{\frac{1}{n}}.\tag{7.70}$$

*Proof* The inequality on the left of (i), called Hadamard inequality, has been given by Lemma 7.17. The inequality on the right of (i) gives an upper bound of ,*n i*=1 |β*i*|, by Lemma 7.33,

$$|\beta\_j^\*| \le 2^{\frac{i-j}{2}} |\beta\_i^\*|, 1 \le j < i \le n. \tag{7.71}$$

Thus

$$
\beta\_i = \beta\_i^\* + \sum\_{j=1}^{i-1} u\_{ij} \beta\_j^\*.
$$

We get

$$\begin{aligned} |\beta\_i|^2 &= |\beta\_i^\*|^2 + \sum\_{j=1}^{i-1} \mu\_{ij}^2 |\beta\_j^\*|^2 \\ &\le |\beta\_i^\*|^2 + \frac{1}{4} \sum\_{j=1}^{i-1} |\beta\_j^\*|^2 \\ &\le \left(1 + \frac{1}{4} \sum\_{j=1}^{i-1} 2^{i-j}\right) |\beta\_i^\*|^2 \end{aligned}$$

#### 7.5 Approximation of SVP and CVP 297

$$\begin{aligned} &= \left(1 + \frac{1}{4}(2^i - 2)\right) |\beta\_i^\*|^2 \\ &\le 2^{i-1} |\beta\_i^\*|^2. \end{aligned}$$

There is

$$\begin{aligned} \prod\_{i=1}^n |\beta\_i|^2 &\le \prod\_{i=1}^n 2^{i-1} |\beta\_i^\*|^2 \\ &= 2^{\sum\_{i=0}^{n-1} i} \prod\_{i=1}^n |\beta\_i^\*|^2 \\ &= 2^{\frac{n}{2}(n-1)} \prod\_{i=1}^n |\beta\_i^\*|^2 \\ &= 2^{\frac{n}{2}(n-1)} (d(L))^2. \end{aligned}$$

So

$$\prod\_{i=1}^n |\beta\_i| \le 2^{\frac{n}{4}(n-1)}d(L).$$

We have (7.69) holds. To prove (iii), by (7.72) and (7.71), then

$$|\beta\_j|^2 \le 2^{j-1} |\beta\_j^\*|^2 \le 2^{j-1} 2^{i-j} |\beta\_i^\*|^2 = 2^{i-1} |\beta\_i^\*|^2. \tag{7.73}$$

For all 1 ≤ *j* ≤ *i* ≤ *n*, especially,

$$|\beta\_1^\*| \le 2^{i-1} |\beta\_i^\*|^2, 1 \le i \le n.$$

Thus

$$\begin{aligned} \left| \beta\_1 \right|^{2n} &\leq 2^{\sum\_{i=0}^n (i-1)} \prod\_{i=1}^n \left| \beta\_i^\* \right|^{2^i} \\ &= 2^{\frac{n}{2}(n-1)} (d(L))^2. \end{aligned}$$

So

$$|\beta\_1| \le 2^{\frac{n-1}{4}} d(L)^{\frac{1}{n}}.$$

Lemma 7.35 holds!

The following theorem shows that if {β1, β2,...,β*n*} is a set of Reduced bases of a lattice *L*, then β1 is the approximation vector of the shortest vector *u*0 of lattice *L*, and the approximation coefficient *rn* = 2*n*−1.

**Theorem 7.5** *Let L* = *L*(*B*) ⊂ R*n be a lattice (full rank lattice), B* = [β1, β2, ...,β*n*] *is a set of Reduced bases of L,* λ1 = λ(*L*) *is the minimal distance of L, then*

298 7 Lattice-Based Cryptography

$$|\beta\_1| \le 2^{\frac{n-1}{2}} \lambda\_1 = 2^{\frac{n-1}{2}} \lambda(L). \tag{7.74}$$

*Proof* We only prove that for ∀ *x* ∈ *L*, *x* = 0, there is

$$\|\beta\_1\|^2 \le 2^{n-1} |\mathbf{x}|^2, \forall \mathbf{x} \in L, \mathbf{x} \ne \mathbf{0}.\tag{7.75}$$

When *x* ∈ *L*, *x* = 0 given, let

$$\lambda x = \sum\_{i=1}^{n} r\_i \beta\_i = \sum\_{i=1}^{n} r'\_i \beta\_i^\*, r\_i \in \mathbb{Z}, r'\_i \in \mathbb{R}, \ 1 \le i \le n.$$

Let *k* be the largest subscript ⇒ *rk* = 0, thus *rk* = *r k* . So

$$|\mathbf{x}|^2 \ge r\_k^2 |\beta\_k^\*|^2 \ge |\beta\_k^\*|^2 \ge 2^{1-k} |\beta\_1|^2. \tag{7.76}$$

Thus

$$|\beta\_1|^2 \le 2^{k-1} |\alpha|^2 \le 2^{n-1} |\alpha|^2, \ x \in L, \ x \ne 0.$$

That is (7.75) holds, thus Theorem 7.5 holds.

The following results show that not only the shortest vector, the whole Reduced basis vector is the approximation vector of the Successive Shortest vector of the lattice.

**Lemma 7.36** *Let L* ⊂ R*n be a lattice,* {β1, β2,...,β*n*} *is a Reduced base of L, let* {*x*1, *x*2,..., *xt*} ⊂ *L be t linearly independent lattice points, then*

$$\left| \left| \beta\_{j} \right|^{2} \leq 2^{n-1} \max \{ \left| \mathbf{x}\_{1} \right|^{2}, \left| \mathbf{x}\_{2} \right|^{2}, \dots, \left| \mathbf{x}\_{l} \right|^{2} \} . \tag{7.77}$$

*For all* 1 ≤ *j* ≤ *t holds.*

*Proof* Write

$$x\_j = \sum\_{i=1}^n r\_{ij}\beta\_i, r\_{ij} \in \mathbb{Z}, \ 1 \le i \le n, \ 1 \le j \le t.$$

For fixed *j*, let *i*(*j*) the largest positive integer *i* ⇒ *ri j* = 0, by (7.76), we have

$$|x\_j|^2 \ge |\mathcal{J}\_{i(j)}^\*|^2, \ 1 \le j \le t.$$

Change the order of *x j* to ensure *i*(1) ≤ *i*(2) ≤···≤ *i*(*t*), then *j* ≤ *i*(*j*), for ∀ 1 ≤ *j* ≤ *t* holds. Otherwise, the assumption that

$$\{\mathbf{x}\_1, \mathbf{x}\_2, \dots, \mathbf{x}\_n\} \subset L(\beta\_1, \beta\_2, \dots, \beta\_{j-1})$$

is linearly independent of *x*1, *x*2,..., *x j* is contradictory. Thus *j* ≤ *i*(*j*). By (7.73) of Lemma 7.35, then

$$\begin{aligned} \left| \beta\_j \right|^2 &\le 2^{i(j)-1} \left| \beta\_{i(j)}^\* \right|^2 \\ &\le 2^{n-1} \left| \beta\_{i(j)}^\* \right|^2 \\ &\le 2^{n-1} \left| x\_j \right|^2, \forall \ 1 \le j \le t. \end{aligned}$$

Thus (7.77) holds, the Lemma holds.

*Remark 7.4* We give a proof of *rk* = *r k* in Theorem 7.5, because *k* is the largest subscript ⇒ *rk* = 0, so

$$x = \sum\_{i=1}^{k} r\_i \beta\_i = \sum\_{i=1}^{k} r'\_i \beta\_i^\* \dots$$

By (7.52) and (7.53),

$$r\_k^{'} = \frac{\langle \mathbf{x}, \beta\_k^\* \rangle}{|\beta\_k^\*|^2}, r\_k = \frac{\langle \mathbf{x}, \beta\_k^\* \rangle}{\langle \beta\_k, \beta\_k^\* \rangle}.$$

Because β*k* , β∗ *k* =β∗ *k* , β∗ *k* , so

$$r\_k^\prime = \frac{\langle \alpha, \beta\_k^\* \rangle}{\langle \beta\_k, \beta\_k^\* \rangle} = r\_k.$$

In order to discuss the approximation of the Successive Shortest vector of a lattice, let's look at the definitions of the continuous minimum λ1, λ2,...,λ*n* and the Successive Shortest vector of a lattice, by Definition 7.6 and Corollary 7.6 in Sect. 7.2, the continuous minimum λ1, λ2,...,λ*n* of a full rank lattice is reachable, for all 1 ≤ *i* ≤ *n*, there is

$$|\alpha\_i| = \lambda\_i, \ \alpha\_i \in L, 1 \le i \le n.$$

For a Successive Shortest vector called α1, α2,...,α*n*, |α*i*| is the shortest under the condition that α*i* is linearly independent of {α1, α2,...,α*i*−1}.

**Theorem 7.6** *Let*{β1, β2,...,β*n*} *be a Reduced basis of lattice L, and* λ1, λ2,...,λ*n be the continuous minimum of L, then we have*

$$\left| |\beta\_i| \right|^2 \le 2^{n-1} \lambda\_i, \ 1 \le i \le n. \tag{7.78}$$

*Proof* We make an induction of *i*. Because {β1, β2,...,β*i*} is an Reduced basis of lattice *Li* in R*i* , the proposition is obviously true when *i* = 1 (see Theorem 7.5 ). If the proposition holds for *i* − 1, then by Lemma 7.36,

$$|\beta\_i^\*|^2 \le 2^{n-1} \max\{\lambda\_1, \lambda\_2, \dots, \lambda\_i\} = 2^{n-1}\lambda\_i.$$

Therefore, (7.78) holds for all *i*. The Theorem holds.

Next, we choose the Reduced basis to solve the shortest adjacent vector problem (CVP). For any given *t* ∈ R*n*, because there are only finite lattice points in one lattice *L* in the Ball(*t*,*r*) with *t* as the center and *r* as the radius, there is a lattice point *ut* closest to *t*, that is

$$|u\_t - t| = \min\_{\mathbf{x} \in L, \mathbf{x} \neq t} |\mathbf{x} - t|. \tag{7.79}$$

We use the Reduced basis to find a lattice point ω ∈ *L* ⇒

$$|\alpha - t| \le r\_1(n)|u\_t - t|,\tag{7.80}$$

ω is called an approximation of the nearest lattice point *ut* , and *r*1(*n*) is called an approximation coefficient. According to Babai (1986), to solve the approximation of the nearest lattice point *ut* , we adopt the following two technical means:

(A) rounding off: ∀ *x* ∈ R*n*, [β1, β2,...,β*n*] = *B* is a Reduced base of lattice *L*. The discard vector [*x*]*B* of *x* is defined as follows, let

$$\chi = \sum\_{i=1}^{n} \chi\_i \beta\_i, \ x\_i \in \mathbb{R},$$

Let δ*i* be the nearest integer to *xi* , then define

$$\mathbb{I}[\chi]\_B = \sum\_{i=1}^n \delta\_i \beta\_i \,, \tag{7.81}$$

[*x*]*B* is called the discard vector of *x* under base *B*, write *x* = [*x*]*B* + {*x*}*B*, then

$$\{x\}\_B \in \left\{\sum\_{i=1}^n a\_i \beta\_i \,|\, -\frac{1}{2} < a\_i \le \frac{1}{2}, \, 1 \le i \le u\right\}.$$

(B) Adjacent plane

Let*U* = "*n*−1 *i*=1 Rβ*i* = *L*(β1, β2,...,β*n*−1) ⊂ R*n* be an *n* − 1-dimensional subspace, *L* = "*n i*=1 Zβ*i* ⊂ *L* be a sublattice of *L*, and v ∈ *L*, call *U* + v is an affine plane of R*n*. When *x* ∈ R*n* given, if the distance between *x* and *U* + v is the smallest, *U* + v is called the nearest affine plane of *x*.

Let *x* be the orthogonal projection of *x* in the nearest affine plane *U* + v, let *y* ∈ *L* be the vector closest to *x* − v in *L* , and let w = *y* + v be the approximation of the vector closest to *x* in *L*.

Let *L*(β1, β2,...,β*n*) ⊂ R*n* be a lattice, {β∗ 1 , β∗ 2 ,...,β∗ *n* } is the corresponding orthogonal basis. ∀ *x* ∈ R*n*, write *x* = "*n i*=1 *xi*β∗ *i* , *xi* ∈ R*n*, δ*i* represents the nearest integer of *xi* , according to the nearest plane method, we take (see Lemma 7.43 below).

$$\begin{cases} \begin{aligned} U &= L(\beta\_1^\*, \beta\_2^\*, \dots, \beta\_{n-1}^\*) = L(\beta\_1, \beta\_2, \dots, \beta\_{n-1}) \\ r &= \delta\_n \beta\_n \in L \\ \mathbf{x}' &= \sum\_{i=1}^{n-1} x\_i \beta\_i^\* + \delta\_n \beta\_n^\* \\ \mathbf{y} &\text{ is a sublattice The grid point closest to } \mathbf{x} - v \text{ in } L' = \sum\_{i=1}^{n-1} \mathbb{Z} \beta\_i \\ \boldsymbol{\omega} &= \mathbf{y} + v \end{aligned} \tag{7.82}$$

We prove that

**Theorem 7.7** *Let L* = *L*(*B*) ⊂ R*n be a lattice, B* = [β1, β2,...,β*n*] *is a Reduced base of L, for* ∀ *x* ∈ R*n given, the adjacent plane method produces a lattice point* ω = *y* + v *adjacent to x in L (by (7.82)), satisfies*

$$|w - x| \le 2^{\frac{q}{2}} |u\_x - x|,\tag{7.83}$$

*where ux is given by Eq. (7.79) and further*

$$|x - \omega| \le 2^{\frac{\mu}{2} - 1} |\beta\_n^\*|. \tag{7.84}$$

*Proof* If *n* = 1, then *B* = θ ∈ R, θ = 0. Let *x* ∈ R, *x* = *x*1θ, *L* = *n*θ, then when *n* ∈ Z,

$$|\mathbf{x} - n\theta| = |\mathbf{x}\_1 \theta - n\theta| = |\mathbf{x}\_1 - n||\theta| \ge |\mathbf{x}\_1 - \delta||\theta|,$$

where δ is the nearest integer to *x*1, let ω = δθ, then

$$|\mathbf{x} - \boldsymbol{\omega}| = |\mathbf{x}\_1 - \boldsymbol{\delta}| |\boldsymbol{\theta}| \le |\mathbf{x} - \boldsymbol{n}\boldsymbol{\theta}|, \ \forall \, \boldsymbol{n} \in \mathbb{Z}.$$

So ω = δθ is the lattice point closest to *x* in *L*, so ω = *ux* ∈ *L*, that is

$$|x - a| = |u\_x - x|.$$

Thus (7.83) holds.

Let *n* ≥ 2, we observe (see (7.82)), v = δ*n*β*n*, *x* = "*n*−1 *i*=1 *xi*β∗ *i* + δ*n*β∗ *n* , then

$$|\mathbf{x} - \mathbf{x}^{\prime}| = |\mathbf{x}\_n - \delta\_n| |\beta\_n^\*| \le \frac{1}{2} |\beta\_n^\*|,\tag{7.85}$$

since the distance between affine planes {*u* + *z*|*z* ∈ *L*} is at least |β∗ *n* |, and |*x* − *x* | is the distance between *x* and the nearest affine plane, there is

$$|\mathbf{x} - \mathbf{x}'| \le |\boldsymbol{\mu}\_x - \mathbf{x}|.\tag{7.86}$$

Let ω = *y* + v = *y* + δ*n*β*n* ∈ *L*, we prove that

$$\|\mathbf{x} - \boldsymbol{\alpha}\|^2 = |\mathbf{x} - \mathbf{x}\prime|^2 + |\mathbf{x}\prime - \boldsymbol{\alpha}\prime|^2. \tag{7.87}$$

Because *x* − *x* = (*xn* − δ*n*)β∗ *n* , *x* − ω = *x* − v − *y* ∈ *u*, so (*x* − *x* )⊥(*x* − ω). Therefore, by the Pythagorean theorem, (7.87) holds. By induction, we have (see (7.79))

$$\left|\mathbf{x} - \boldsymbol{\omega}\right|^2 \le \frac{1}{4} (|\boldsymbol{\beta}\_1^\*|^2 + |\boldsymbol{\beta}\_2^\*|^2 + \dots + |\boldsymbol{\beta}\_n^\*|^2).$$

By (7.71),

$$|\beta\_i^\*|^2 \le 2^{n-i} |\beta\_n^\*|^2.$$

Thus

$$\begin{aligned} \left| \left| x - w \right|^2 \leq \frac{1}{4} |\beta\_n^\*|^2 (1 + 2 + 2^2 + \dots + 2^{n-1}) \\ = \frac{1}{4} (2^n - 1) |\beta\_n^\*|^2 \\ \leq 2^{n-2} |\beta\_n^\*|^2. \end{aligned}$$

There is

$$|\mathbf{x} - \boldsymbol{\omega}| \le 2^{\frac{n}{2} - 1} |\boldsymbol{\beta}\_n^\*|,\tag{7.88}$$

that is (7.84) holds. To prove (7.83), we have two situations:

Case 1: if *ux* ∈ *U* + *x*,

In this case, *ux* − v ∈ *U* ⇒ *ux* − v ∈ *L* is the lattice point closest to *x* − v in *L*, so there is

$$|\mathbf{x}' - \boldsymbol{\omega}| = |\mathbf{x}' - \boldsymbol{v} - \mathbf{y}| \le C\_{n-1}|\mathbf{x}' - \boldsymbol{u}\_x| \le C\_{n-1}|\mathbf{x} - \boldsymbol{u}\_x|,$$

where *Cn* = 2 *n* 2 . By (7.87), we have

$$|\mathbf{x} - \boldsymbol{\omega}|^2 \le (1 + (C\_{n-1})^2)^{\frac{1}{2}} |\mathbf{x} - \boldsymbol{\mu}| < C\_n |\mathbf{x} - \boldsymbol{\mu}|.$$

The proposition holds.

Case 2: If *ux* ∈/ *U* + *x*, then

$$|x - u\_x| \ge \frac{1}{2} |\mathcal{J}\_n^\*|.$$

By (7.88), we get

$$|\mathbf{x} - \boldsymbol{\alpha}| < 2^{\frac{\mu}{2}}|\mathbf{x} - \boldsymbol{\mu}\_x|.$$

Thus, Theorem 7.7 holds.

Comparing Theorems 7.6 and 7.7, when *x* = 0, the approximation coefficient of Theorem 7.6 is 2*n*−1 2 , for general *x* ∈ R*n*, there is an additional factor √2 in the approximation coefficient. Using the rounding off technique, we can give an approximation to adjacent vectors, another main result in this section is

**Theorem 7.8** *Let B* = [β1, β2,...,β*n*] *be a Reduced basis of L, x* ∈ R*n given arbitrarily, ux* ∈ *L is the lattice point closest to x, and* [*x*]*B is given by Eq. (7.82), then* ω = [*x*]*B* ∈ *L, and*

$$|\mathbf{x} - \mathbf{f}\mathbf{x}|\_{B}| \le \left(1 + 2n\left(\frac{9}{2}\right)^{\frac{n}{2}}\right)|\mathbf{x} - \mathbf{u}\_x|.\tag{7.89}$$

By Theorem 7.8, [*x*]*B* ∈ *L* is an approximation of the nearest lattice point *ux* , and the approximation coefficient is γ1(*n*) = 1 + 2*n* - 9 2 . *n* 2 , it is a little worse than the approximation coefficients generated by adjacent planes, but the approximation vector is relatively simple. In lattice cryptosystem, [*x*]*B* as input information has higher efficiency. To prove Theorem 7.8, we need the following Lemma.

**Lemma 7.37** *Let B* = [β1, β2,...,β*n*] *is a Reduced base of* R*n,* θ*k represents the angle between vector* β*k and subspace Uk , where*

$$U\_k = \sum\_{i \neq k} \mathbb{R} \beta\_i. \tag{7.90}$$

*Then for each k,* 1 ≤ *k* ≤ *n, we have*

$$
\sin \theta\_k \ge \left(\frac{\sqrt{2}}{3}\right)^n. \tag{7.91}
$$

*Proof* 1 ≤ *k* ≤ *n* given, ∀ *m* ∈ *Uk* , we prove

$$|\beta\_k| \le \left(\frac{9}{2}\right)^{\frac{n}{2}} |m - \beta\_k|, m \in U\_k. \tag{7.92}$$

Because

$$\sin \theta\_k = \min\_{m \in U\_k} \frac{|m - \beta\_k|}{|\beta\_k|},$$

so by (7.92), ⇒ (7.91), the Lemma holds. To prove (7.92), let {β∗ 1 , β∗ 2 ,...,β∗ *n* } be the orthogonal basis corresponding to the Reduced basis Reduced {β1, β2,...,β*n*}, then *m* ∈ *Uk* can express as

$$m = \sum\_{i \neq k} a\_i \beta\_i = \sum\_{j=1}^n b\_j \beta\_j^\*, a\_i, b\_j \in \mathbb{R}.$$

Write

$$m = (a\_1, \dots, a\_n) \begin{bmatrix} \beta\_1 \\ \beta\_2 \\ \vdots \\ \beta\_n \end{bmatrix} = (a\_1, \dots, a\_n) U \begin{bmatrix} \beta\_1^\* \\ \beta\_2^\* \\ \vdots \\ \beta\_n^\* \end{bmatrix}.$$

where *ak* = 0, *U* is the transition matrix of Gram–Schmidt orthogonalization (see (7.87)). Then for any 1 ≤ *j* ≤ *n*, 1 ≤ *k* ≤ *n*, there is

$$b\_j = \sum\_{i \neq k} a\_i \mu\_{ij}, \beta\_k = \sum\_{i=1}^n \mu\_{ki} \beta\_i^\*.$$

So

$$m - \beta\_k = \sum\_{j=1}^{n} \nu\_j \beta\_j^\*, \text{ where } \nu\_j = b\_j - \mu\_{kj}.$$

Let *ak* = −1, then

$$\gamma\_j = \sum\_{i=1}^n a\_i u\_{ij} = a\_j + \sum\_{i=j+1}^n a\_i u\_{ij}. \tag{7.93}$$

Therefore, Eq. (7.92) can be rewritten as

$$|\beta\_k|^2 = \sum\_{j=1}^k \mu\_{kj}^2 |\beta\_j^\*|^2 \le \left(\frac{9}{2}\right)^{\frac{9}{2}} \sum\_{j=1}^n \nu\_j^2 |\beta\_j^\*|^2. \tag{7.94}$$

Let us first prove the following assertion:

$$\sum\_{j=k}^{n} \nu\_j^2 \ge \left(\frac{2}{3}\right)^{2(n-k)}.\tag{7.95}$$

If the above formula does not hold, i.e.,

$$\sum\_{j=k}^{n} \nu\_j^2 < \left(\frac{2}{3}\right)^{2(n-k)}$$

Then for all *j*, *k* ≤ *j* ≤ *n*, there is

$$|\chi\_j^2 < \left(\frac{2}{3}\right)^{2(n-k)} \Rightarrow |\chi\_j| < \left(\frac{2}{3}\right)^{(n-k)}.\tag{7.96}$$

.

By (7.93),

$$\begin{cases} \begin{aligned} \gamma\_n &= a\_n \\ \gamma\_{n-1} &= a\_{n-1} + a\_n u\_{nn-1} \\ \gamma\_{n-2} &= a\_{n-2} + a\_{n-1} u\_{n-1n-2} + a\_n u\_{nn-2} \\ &\cdots \\ \gamma\_k &= a\_k + a\_{k+1} u\_{k+1k} + \cdots + a\_n u\_{nk} \end{aligned} \end{cases}$$

We can prove

$$|a\_j| < \left(\frac{3}{2}\right)^{n-j} \cdot \left(\frac{2}{3}\right)^{n-k}.\tag{7.97}$$

Because when *j* = *n*, *an* = γ*n*, (7.96) ensures that (7.97) holds. Reverse induction of *j*(*k* ≤ *j* ≤ *n*), by (7.93),