# Introduction

Definition 1.1(Lattice). A lattice $\mathcal L$ is a discrete subgroup of $H$ generated by all the integer combinations of the vectors of some basis $B$ :
$$\mathcal L = \sum^m_{i=1}\mathbb Zb_i = \lbrace \sum^m_{i=1}z_ib_i, where \ z_i \in \mathbb Z,b_i \in B \rbrace .$$
Theorem 1.1 (Minowski’s Theorem). Any convex, centrally symmetric body $S$ of volume $vol(S) > 2^ndet(\mathcal L)$ contains a non-zero lattice point. $det(\mathcal L)$ is the determinant of a lattice $\mathcal L$ .

Definition 1.2 (Fundamental Region). A set $\mathcal F \subseteq \mathbb R^n$ of a lattice $\mathcal F$ if its translation $x+\mathcal F = {x+y:y \in \mathcal F}$,taken over all $x \in \mathcal L$, form a partition of $\mathbb R^n$.

Corollary 1.1.1 For any n-dimensional lattice $\mathcal L$, we have the length of shortest vector $\lambda(\mathcal L) > \sqrt n \cdot det(\mathcal L)^{1 \over n}$

# Basis Reduction

​ Basis reduction is a process of reducing the basis $B$ of a lattice $\mathcal L$ to a shorter basis $B’$ while keeping $\mathcal L$ the same.

​ There are some ways to change the basis but keep the same lattice :

      1. Swap two vectors in the basis.
2. For a vector $b_i \in B$, use $-b_i$ instead.
3. For a vector $b_i \in B$, add a linear combination of other basis vectors to it.


Basis reduction can help solving SVP, because if we can not reduce a basis anymore, the shortest basis vector should be the shortest vector of the lattice.

Now we start by solving the SVP in 2-dimensional case.

Definition 2.1 (Two dimensional reduced basis). A basis $(b_1,b_2)$ is said to be reduced if it satisfies following condition:
$$|| b_1 || \leq || b_2 || \\ u = {b_1 \cdot b_2 \over ||b_1||^2} \leq {1\over 2}$$
with the $u$ is called the orthogonal projection coefficient.

Theorem 2.1. Given a two dimensional lattice $\mathcal L$ with basis rank 2, if $\lambda$ is the length of the shortest vector in $\mathcal L$, then
$$\lambda \leq \sqrt { {2 \over \sqrt3}det(\mathcal L)}.$$
Theorem 2.2 if a basis ${b_1,b_2}$ is reduced, then $b_1$ is the shortest vector.

​ About the Definition 2.1 and Theorem 2.1 , 2.2 , I think when we can say we find the shortest vector $b_1$, the basis $(b_1,b_2)$ is said “already be reduced”. And it means that this basis satisfies the condition in the Definition 2.1.
​ So, if $u > {1\over 2}$, the basis can be reduced continued.

The description of Gauss’s algorithm solved SVP in 2-dimensional.

1. Start with basis ${b_1,b_2}$, if $||b_1|| > ||b_2||$. swap $b_1$ and $b_2$.
2. Compute $u = {b_1 \cdot b_2 \over ||b_1||^2}.$If $u>{1\over 2}$. let $m$ be the biggest integer that is smaller than $u$, and let $b_2 = b_2 - mb_1.$
3. If $||b_1|| > ||b_2||$, then swap $b_1$ and $b_2$, and repeat step 2. Otherwise, output $b_1$

According the algorithm above, I write the following script with the Sagemath.

The basis we found in Gauss algorithm is not exactly orthogonal, but it is the nearest basis we can get.

# Gram-Schmidt Orthogonalization

To generalize the algorithm to n-dimensions, we need to find a way to construct n-dimensional orthogonal basis based on the given basis, which leads us to Gram-Schmidt Orthogonalization.

Theorem 3.1 (Gram-Schmidt Orthogonalization method). Given a basis $\{b_1,b_2,\cdots,b_m\}$ of a subspace $H_m$ of $\mathbb R^n$, we define
$$b_1^* = b_1 \\ b_2^*=b_2 - u_{1,2}b_1, \ \ \ \ \ \ u_{1,2} = {b_2 \cdot b_1^* \over b_1^* \cdot b_1^*} \\ \vdots \\ b_m^* = b_m - \sum_{i<m}u_{i,m}b_i \ \ \ \ \ \ u_{i,m} = {b_m \cdot b_i^* \over b_i^* \cdot b_i^*} \\$$
Then, $\{b_1^*,b_2^*,\cdots,b_m^*\}$ is an orthogonal basis of $H_m$.

Based on this Theorem, if we set $u_{m,m} = 1$, then we have
$$b_m = \sum ^m_{i=1}u_{i,m}b_i$$
Therefore, we can write the above formula in matrix form, $B = B^*U$.

where basis vectors are columns in $B$ and $B^*$. Thus, we have
$$U = \begin{pmatrix} u_{1,1}&u_{1,2}&\cdots&u_{1,n} \\ 0&u_{2,2}&\cdots&u_{2,n} \\ \vdots&\vdots&\ddots&\vdots \\ 0&0&0&u_{n,n} \\ \end{pmatrix} = \begin{pmatrix} 1&u_{1,2}&\cdots&u_{1,n} \\ 0&1&\cdots&u_{2,n} \\ \vdots&\vdots&\ddots&\vdots \\ 0&0&0&1 \\ \end{pmatrix}$$
Obviously, we can know that $det(U) = 1$

For better understanding the matrix , let’s write the matrix at length.

but before write down the matrix, I want to translate the formula in the Theorem 3.1.

$$(b_1,b_2,\cdots,b_n) \begin{pmatrix} 1&u_{1,2}&\cdots&u_{1,n} \\ 0&1&\cdots&u_{2,n} \\ \vdots&\vdots&\ddots&\vdots \\ 0&0&0&1 \\ \end{pmatrix} = (b_1^*,b_2^*,\cdots,b_n^*)$$
I can’t understand! why $B = B^*U$ ?????

# LLL Basis Reduction

Definition 4.1 (LLL reduced basis). Let$\{b_1,b_2,\cdots,b_n\}$ be a basis for a n-dimensional Lattice $\mathcal L$ , and $\{b_1^{∗},b_2^{∗},\cdots,b_n^{∗}\}$ be the orthogonal basis generated in Theorem 3.1, and we have $u_{i,k}={b_k \cdot b_i^{∗} \over b_i^{∗} \cdot b_i^{∗}}$. We say $\{b_1,b_2,\cdots,b_n\}$ is a LLL reduced basis if it satisfies two conditions:

(1) $\forall i \ne k, u_{i,k} \le {1\over 2},$
(2) For each $i, ||b_{i+1}^{∗} + u_{i,i+1}b_i^{∗}||^2 \ge {3\over 4}||b_i^{∗}||^2$

Remark. The constant $3\over 4$ is chosen for the simplicity of the paper. Any constant between $1\over 4$ and 1 can guarantee that the algorithm terminates in polynomial time.

Remark. The condition 2 emphasizes the ordering of the basis, like what we did in two dimensional case.

Given a basis $\{b_1,b_2,\cdots,b_n\}$ in n-dimension, to get a LLL reduced basis, the LLL algorithm works as below.

• Step 1: Computed the most orthogonal basis based on Gram-Schmidt orthogonalization.

• Step 2: Check the second condition.

Because I don’t know how to choose the constant, I run the LLL Algorithm four times with different constants for one output.

Claim 4.1. If $\{b_1,b_2,\cdots,b_n\}$ is a n-dimensional LLL reduced basis of Lattice $\mathcal L$, then $||b_1|| \le 2^{n-1 \over 2 }\lambda(\mathcal L)$ is the length of the shortest vector of $\mathcal L$.

In this paper, the author proof the LLL algorithm terminates in polynomial time of $n$ in the next part. If you want to know how to proof that, you can read the original paper.

# Conclusion

I think this paper make me understand the LLL Algorithm easily, but I want to know more detail about the LLL Algorithm. If I have time, I would like to see the original paper about LLL! -> https://link.springer.com/content/pdf/10.1007/BF01457454.pdf