\chapter{Background}

\section{Basic field theory}
\begin{definition}
A field $\F$ is a commutative ring with identity in which each nonzero element has an inverse.
In other words, the set of units $\F^* = \F \setminus \{0\}$ is an abelian group under multiplication.
\end{definition}

\begin{example}
We can check that the following are fields:
\begin{enumerate}
\item Fields with infinite elements: $\Q, \R, \C$, i.e., the fields of rational numbers, real numbers and complex numbers.
\item Fields with finite elements: $\Z/2\Z, \Z/11\Z$. In general, $\F_p =\Z/p\Z$ is a field, where $p$ is a prime number.
\end{enumerate}
\end{example}

\begin{definition}
A field with finite elements is called a finite field or a Galois field.
\end{definition}

\begin{definition}
Let $\F$ be a given field. The characteristic of $\F$, denoted by $ch(\F)$, is defined as the smallest 
positive integer $n$ such that $n*1_{\F}=0$ if such an integer exists and is defined as $0$ otherwise.
\end{definition}

\begin{proposition}
Let $\F$ be a given field. Then $ch(\F)$ is either $0$ or a prime $p$.
\end{proposition}

\begin{example}
We have the following cases:
\begin{enumerate}
\item $ch(\Q) = 0$, where $\Q$ is the rational number field.
\item Let $p$ be a prime number. Then $ch(\F_p)=p$.
\item Let $p$ be a prime number, $\F_p[x]$ be the integral domain of polynomials in the variable $x$ with coefficients
in $\F_p$ and $\F_p(x)$ be the fraction field of $\F_p[x]$. We have $ch(\F_p(x)) = p$. 
\end{enumerate}
\end{example}

\begin{definition}
Let $\F$ be a given field. The intersection of all subfields of $\F$, denoted by $\mathbf{K}\subset \F$, is 
called the prime subfield of $\F$.
\end{definition}

\begin{proposition}
We have the following conclusions:
\begin{enumerate}
\item If $ch(\F)=0$, then the prime subfield $\mathbf{K}$ of $\F$ is isomorphic to $\Q$. 
\item If $\F$ is a finite field, i.e., $|\F|< \infty$, then the prime subfield $\mathbf{K}$ of $\F$ is isomorphic to $\F_p$, where $p=ch(\F)$.
Furthermore, if the field extension degree $[\F:\mathbf{K}]=k$, then $|\F|=p^k$.
\end{enumerate}
\end{proposition}

\begin{proposition}
We have the following conclusions:
\begin{enumerate}
\item If $\F_q$ is a finite field with order $q\in \Z$, then $q = p^k$, where $p = ch(\F_q)$.
\item Conversely, for each $q=p^k$ where $p$ is a prime and $k$ is a positive integer, there exists a unique finite field of order $q$ up to isomorphism.
The field is the splitting field of $f(X)=X^q-X$ over $\F_p$. All the elements of $\F_q$ are roots of $f(X)$. 
Furthermore, $\F_q^*$ is cyclic.
\end{enumerate}
\end{proposition}


\section{Error-correcting codes}
Basically, error-correcting codes add some 
useful redundant information to detect and correct errors. 
More information on error-correcting codes can be found in books such as \cite{MacwilliamsSl77}.

\subsection{Linear codes}

In this section, we shall give a concise description of the linear codes \cite{MacwilliamsSl77}.
We assume the alphabet of the codes is a finite field $\F_q$.
We shall first consider the sending side.

\vspace{5 mm}
\begin{figure}[h]
\tikzstyle{int}=[draw, minimum size=2em]
\tikzstyle{init} = [pin edge={to-,thin,black}]
\centering
\begin{tikzpicture} [node distance = 2.5cm, auto, >=latex']
	\node [int] (a) {$Alice$};
	\node [int] (e) [right of=a, node distance = 5cm] {$encoder$};
	\node [int] (c) [right of=e, node distance = 6cm] {$channel$};
	%\node [int] (d) [right of=c, node distance = 4cm] {$decoder$};
	\node [int] (n) [below of=c, node distance = 2cm] {$noise$};
	%\node [int] (b) [right of=d, node distance = 2cm] {$Bob$};
	%edge node[align=center] {$line1$\\$line2$} (two);
	\path[->] (a) edge node[align=center] {$signals$ \\ $\mathbf{v}=v_1v_2\cdots v_k$} (e);
	\path[->] (e) edge node[align=center] {$codeword$ \\ $\mathbf{x}=x_1x_2\cdots x_n$} (c);
	%\path[->] (c) edge node {$signal$} (d);
	%\path[->] (d) edge node {} (b);
	\path[->] (n) edge node {} (c);
\end{tikzpicture}
\caption{Encoding procedure} \label{fig:encoding}
\end{figure}
\vspace{5 mm} 

As indicated in Figure \ref{fig:encoding}, the sent message is divided by blocks.
Each message block is of length $k$, which is encoded as a codeword of length $n\geqslant k$.

\begin{example}
In this example, the codeword consists of two parts: the first part is the same as the message block,
i.e., $x_i=v_i$ for $1\leqslant i \leqslant k$; the second part contains the useful redundant
symbols, which are called \textit{check} symbols. Given the \textit{parity check matrix} $H$
of the form 
\begin{equation} \label{parityform}
H = [A|I_{n-k}],
\end{equation}
where $A$ is an $(n-k)*n$ matrix and $I_{n-k}$ is an $(n-k)*(n-k)$ unit matrix,
the check symbols are determined so that 
\[
H\begin{pmatrix}x_1\\x_2\\ \vdots \\x_n\end{pmatrix}=0,
\]
where the computation is performed in the given field $\F_q$.
\end{example}

\begin{remark}
In general, a parity check matrix may not have the form given in (\ref{parityform}).
\end{remark}

\begin{example}
Suppose $k=1,n=3$ and the linear code is defined over $\F_2$. Let the parity check matrix be
\[
H =
\begin{bmatrix}
1 & 1 & 0 \\
1 & 0 & 1
\end{bmatrix}.
\]
Since $k=1$, each block consists of one symbol. Also each codeword $x_1x_2x_3$ satisfies the conditions:
\[
x_1+x_2 = 0, \quad x_1+x_3 =0.
\]
Thus, we have the following encoding table:
\hspace{5mm}
\begin{center}
\begin{tabular} {|c|c|}
\hline
message & codeword \\ \hline
0       & 000 \\ \hline
1 		& 111 \\ 
\hline
\end{tabular}
\end{center}
\hspace{5mm}

This is known as a repetition code.
\end{example}

\begin{example}
Suppose $k=2,n=4$ and the linear code is defined over $\F_2$. Let the parity check matrix be
\[
H =
\begin{bmatrix}
0 & 1 & 1 & 0 \\
1 & 0 & 0 & 1
\end{bmatrix}.
\]
Each message block includes two symbols in this case. Each codeword $x_1x_2x_3x_4$ satisfies:
\[
x_2+x_3=0, \quad x_1+x_4=0.
\]
Thus, we have the following encoding table:
\hspace{5mm}
\begin{center}
\begin{tabular} {|c|c|}
\hline
message & codeword \\ \hline
00      & 0000 \\ \hline
01 		& 0110 \\ \hline
10      & 1001 \\ \hline
11      & 1111  \\
\hline
\end{tabular}
\end{center}
\hspace{5mm}
\end{example}

The general definition of linear codes is given below.
\begin{definition}
A \textit{linear code} of length $n$ and rank $k$, denoted by $[n,k]_q$, is a linear subspace with dimension k of the vector space
$\F_q^n$ where $\F_q$ is the finite field with $q$ elements.
The code has rate (or efficiency) $R=k/n$.
\end{definition}

\begin{remark}
Let $[n,k]_q$ be a given linear code. The elements in the code are called \textit{codewords}.
Elements in $\F_q^n$ are called codes or vectors.
\end{remark}

\begin{remark}
Since we can regard a $[n,k]_q$ linear code as a vector space over $\F_q$ of dimension $k$,
there exists a linearly independent basis $\mathbf{b}_1,\ldots,\mathbf{b}_k$ such that
each codeword $\mathbf{u}$ can be written as
\[
\mathbf{u} = \sum_{i=1}^{k}(c_i\mathbf{b}_i),\quad c_i\in \F_q, 1\leqslant i \leqslant k.
\]
The matrix $G$ whose rows are $\mathbf{b}_1,\ldots,\mathbf{b}_k$ is called a generator matrix.
In the sequel, we assume that the rows of a generator matrix form a basis for the code.
\end{remark}

\begin{definition}
A linear code $[n,k]_q$ is called \textit{maximum distance separable} (in short, MDS) 
if it attains the Singleton bound, i.e., $d=n-k+1$.  
\end{definition}

Now we turn our attention to the receiver's side shown in Figure \ref{fig:decoding}.

\vspace{5 mm}
\begin{figure}[h]
\tikzstyle{int}=[draw, minimum size=2em]
\tikzstyle{init} = [pin edge={to-,thin,black}]
\centering
\begin{tikzpicture} [node distance = 2.5cm, auto, >=latex']
	\node [int] (c) {$Channel$};
	\node [int] (d) [right of=a, node distance = 4cm] {$decoder$};
	\node [int] (r) [right of=e, node distance = 4cm] {$Bob$};
	%\node [int] (d) [right of=c, node distance = 4cm] {$decoder$};
	\node [int] (e) [below of=c, node distance = 2cm] {$error\quad \mathbf{e}$};
	%\node [int] (b) [right of=d, node distance = 2cm] {$Bob$};
	%edge node[align=center] {$line1$\\$line2$} (two);
	\path[->] (c) edge node[align=center] {$received$ \\ $\mathbf{r}=\mathbf{x}+\mathbf{e}$} (d);
	\path[->] (d) edge node[align=center] {$decode$ \\ $\mathbf{v}'$} (r);
	%\path[->] (c) edge node {$signal$} (d);
	%\path[->] (d) edge node {} (b);
	\path[->] (e) edge node {} (c);
\end{tikzpicture}
\caption{Decoding procedure} \label{fig:decoding}
\end{figure}
\vspace{5 mm} 

At the receiver's end, the received message is a mixture of the transmitted message and the 
error vector $\mathbf{e}$ introduced during the transmission. Given $\mathbf{r}=\mathbf{x}+\mathbf{e}$,
the decoder needs to decode $\mathbf{r}$ as $\mathbf{v}'$ such that it minimizes the error.
This is called the maximum likelihood decoding.

\begin{definition}
The \textit{Hamming distance} between two words $\mathbf{u},\mathbf{v}\in\F_q^n$, denoted by $d(\mathbf{u},\mathbf{v})$,
is the number of their distinct coordinates. 
\end{definition}

\begin{example}
Over $\F_2^3$, we have $d(101,001)=1$, $d(010,100)=2$, $d(000,111)=3$.
\end{example}

\begin{definition}
The \textit{error distance} of a received word $\mathbf{u}\in\F_q^n$ to the code $[n,k]_q$ is defined as
its minimum Hamming distance to codewords. 
\end{definition}

\begin{definition}
The \textit{minimum distance} of a code, which is denoted by $d$, 
is the smallest distance between any two distinct codewords of the code. 
The \textit{covering radius} of a code is the maximum distance from any vector in $\F_q^n$ to the nearest codeword.
\end{definition}

\begin{definition}
A \textit{deep hole} of a code $[n,k]_q$ is a vector in $\F_q^n$ achieving the covering radius.
\end{definition}

\begin{example} In Euclidean space $\R^2$, the analogous deep holes are shown in Figure \ref{fig:deepholeR2}.

\begin{figure}[h]
\centering
\begin{tikzpicture}[scale=1.5,>=stealth]
  \foreach \x in {1,2,3,4,5}
  \foreach \y in {1,2,3}
  {
    \draw (\x,\y) circle(0.5);
    \draw[fill=black] (\x,\y) circle(0.05);
  }  
  % \onslide<2>{\draw[dashed] (3.1,2.1) circle(0.5);
  % \draw[fill=gray] (3.1,2.1) circle(0.05);}

  % \onslide<3-5>{  \draw[fill=gray] (3.48,2.32) circle(0.05);}
  % \onslide<3>{\draw[dashed] (3.48,2.32) circle(0.5);}

  % \onslide<4>{\draw[dashed] (3.48,2.32) circle(0.7);}
  % \onslide<5>{\draw[->>] (3.48,2.32) -- (3,2);  }
  \foreach \x in {1,2,3,4}
  \foreach \y in {1,2}
  {
    \draw (\x,\y) + (0.5,0.5) circle(0.05);
  }   
\end{tikzpicture}
\caption{Deep holes in $\R^2$} \label{fig:deepholeR2}
\end{figure}
\end{example}

\subsection{Generalized Reed-Solomon codes}
Generalized Reed-Solomon codes are of special interest and importance both in theory and practice of error-correcting codes.
\begin{definition}
Let $\F_q$ be a finite field with q elements and characteristic $p$.
Let $D=\{\alpha_1,\ldots,\alpha_n\}\subseteq \F_q$ be the evaluation set and $v_i\in\F_q^*, 1\leqslant i \leqslant n,$ be the column multipliers. The
set of codewords of the generalized Reed-Solomon code $RS_q(D,k)$ of
length $n$ and dimension $k$ over $\F_q$ is defined as
$$RS_q(D,k)=\{(v_1f(\alpha_1),\ldots,v_nf(\alpha_n))\in \F_q^n \mid f(x)\in \F_q[x],
deg(f)\leqslant k-1\}.$$
\end{definition}
The generalized Reed-Solomon codes are MDS codes and the minimum distance $d=n-k+1$
and the covering radius $\rho=n-k$.
We shall write generalized Reed-Solomon codes as GRS codes for short.
If $D=\F_q^*$, it is called \textit{primitive}. If $D=\F_q$,
it is called a \textit{singly-extended} GRS code. A GRS code is called \textit{normalized} if its column multipliers are all equal to 1.
In this dissertation, we shall work on the normalized GRS without loss of generality. 

The encoding algorithm of the GRS code can be
described by the linear map: $\varphi: \F_q^k\rightarrow \F_q^n$, in which a message $(a_1,\ldots,a_k)$ is mapped to a codeword $(f(\alpha_1),\ldots,f(\alpha_n))$,
where $f(x)=a_kx^{k-1}+a_{k-1}x^{k-2}+\cdots+a_1\in \F_q[x].$

Efforts have been made to obtain an efficient decoding algorithm for
GRS codes. Given a received word $\mathbf{u}\in \F_q^n$, if the
error distance is smaller than $n-\sqrt{nk}$, then the list decoding
algorithm of Sudan \cite{Sudan97} and Guruswami-Sudan \cite{GS99}
solves the decoding in polynomial time. However, in general, the
maximum likelihood decoding of GRS codes is NP-hard
\cite{GV05}.


\section{Some results related to additive combinatorics}
In this section, we introduce some additive combinatorics results that we shall use later.
The first theorem is about the estimation of the size of restricted sum sets, which was first proved by Dias da Silva and Hamidoune \cite{SH94}. Then Alon et al. \cite{ANR96}
gave a simple proof using the polynomial method.
\begin{theorem}\cite{ANR96,SH94}\label{SH}
Let $\F$ be a field with characteristic $p$ and $n$ be a positive integer. Then for any finite subset $S\subset \F$ we have
$$ |n ^\wedge  S |\geqslant \min\{p, n|S|-n^2+1\},$$
where $n ^\wedge S$ denotes the set of all sums of $n$ distinct elements of $S$.
\end{theorem}


Brakemeier \cite{B78} and Gallardo et al. \cite{GGP99} established the following theorem:
\begin{theorem}\cite{B78,GGP99}\label{2sum}
Let $n$ be a positive integer and $S\subset \Z/n\Z$. If $|S|>\frac{n}{2}+1$, then
\[
2^\wedge S = \Z/n\Z,
\]
where $2^ \wedge S$ denotes the set of all sums of $2$ distinct elements of $S$.
\end{theorem}

\begin{example}
Let $n=7$.
\begin{enumerate}
\item If $S_1=\{1,2,3\}$, then $2^\wedge S_1 = \{3,4,5\} \neq \Z/7\Z$.
\item If $S_2=\{0,2,3,6\}$, then $2^\wedge S_2 = \{1,2,3,5,6\}\ \neq \Z/7\Z$.
\item If $S_3=\{0,1,2,3,4\}$, then $2^\wedge S_3=\{0,1,2,3,4,5,6\} = \Z/7\Z$. 
\item If $S_4 =\{0,1,3,5,6\}$, then $2^\wedge S_4 = \{0,1,2,3,4,5,6\} = \Z/7\Z$.
\end{enumerate}

\end{example}

Theorem \ref{2sum} implies the following corollary:
\begin{corollary}\label{2product}
Let $\F_p$ be a prime finite field, $S\subset \F_p^*$. If $|S|>\frac{p+1}{2}$, then each element of $\F_p^*$ is the product of two distinct
elements of $S$.
\end{corollary}
%For the proof of Corollary \ref{2product}, please refer Appendix B.
\begin{proof}
Let $g$ be a generator of $\F_p^*$. Let $S'=\{e|g^e\in S\}\subset \Z/(p-1)\Z$.
For any given element $\alpha=g^a\in\F_p^*$, we need to show that there exist two distinct
elements $b\neq c$ such that $g^a=g^bg^c$, where $b,c\in S'$.
This is equivalent to $a = b + c$, which follows from Theorem \ref{2sum}.
\end{proof}

\iffalse
\section{Some results related to finite geometry}
In this section, we introduce some finite geometry results that we will use later.

The deep hole problem for Reed-Solomon codes is also closely related to
the famous MDS conjecture in coding theory. On the one hand, GRS codes are MDS codes.
On the other hand, it is known that all long enough MDS codes are essentially GRS codes.
Following the notation of \cite{RL89}, let $N_{min}(k,q)$ be the minimal integer, if any, such that every $[n,k]$ MDS code over $GF(q)$ with
$n>N_{min}(k,q)$ is GRS and be $q+2$ if no such integer exists. For the case of $k=3$, Segre \cite{Segre55} obtained the following result:
\begin{theorem} \cite{Segre55} \label{B.Segre}
If $q$ is odd, every $[n,3]$ MDS code over $GF(q)$ with $q-\dfrac{\sqrt{q}-7}{4} < n \leqslant q+1$ is GRS.
\end{theorem}

When $q=p$ is a prime, Voloch \cite{Voloch90} obtained the following result:
\begin{theorem}\cite{Voloch90}\label{Voloch}
If $p$ is an odd prime number, every $[n,3]$ MDS code over $GF(p)$ with $p-\dfrac{p}{45}+2< n \leqslant p+1$ is GRS.
\end{theorem}

Further, there is a relation for $N_{min}(k+1,q)$ and $N_{min}(k,q)$ \cite{RL89} as follows:
\begin{lemma}\cite{RL89}\label{RL}
For $3\leqslant k \leqslant q-2$, we have
$$N_{min}(k+1,q)\leqslant N_{min}(k,q)+1.$$
\end{lemma}

S. Ball \cite{Ball12} showed the following result:
\begin{theorem}\cite{Ball12}\label{Simeon}
Let $S$ be a set of vectors of the vector space $\F_q^k$, with the
property that every subset of $S$ of size $k$ is a basis. If
$|S|=q+1$ and $k\leqslant p$ or $3\leqslant q-p+1\leqslant
k\leqslant q-2$, where
 $p$ is the characteristic of $\F_q$, then $S$ is equivalent to the following set:
$$\{(1,\alpha,\alpha^2,\ldots,\alpha^{k-1})\mid \alpha\in \F_q\}\cup\{(0,\ldots,0,1)\}.$$
\end{theorem}
\fi

\section{Cryptography}
Cryptography stems from the necessity of confidentiality, authentication and integrity
of information communication. There are three most important primitives, namely
symmetric ciphers, asymmetric ciphers, and hash functions.
\subsection{Asymmetric cryptography}
In a seminal paper \cite{DiffieHe76}, Diffie and Hellman proposed a new kind of
cryptography which is called asymmetric or public-key cryptography. 
In such systems, there exits a private key and a public key, hence the name.

The security of such systems relies on the concept of one-way functions, 
which is easy to compute in one way but hard to compute inversely.
The existence of such functions implies that $P\neq NP$.
Although nobody can prove the existence of such functions currently, people believe 
that there are some qualified candidates. 
The discrete logarithm problem over finite fields is one of the most important 
candidates, besides the integer factorization problem and others.
The hardness of discrete logarithm problem underpins 
the security of the widely adopted 
Diffie-Hellman key exchange protocol \cite{DiffieHe76} and 
ElGamal's cryptosystem \cite{ElGamal85}.



\subsection{The discrete logarithm problem over finite fields}

%It is widely believed that the discrete logarithm problem is hard. 
%Many protocols essentially rely on the hardness of the
%discrete logarithm problem, such as 

\begin{definition}
Let $\F_q$ be a finite field of characteristic $p$. Given $\alpha,\beta\in \F_q^*$, 
the discrete logarithm problem is to find an integer $x$ such that $\alpha^{x}=\beta$.
\end{definition}

\begin{remark}
In this dissertation, we only consider the case when $\alpha$ is a primitive element of $\F_q$.
\end{remark}

The  state-of-the-art general-purpose methods for 
solving the discrete logarithm problem over finite fields 
are the number field sieve algorithm and 
the function field sieve algorithm, which originated from 
the index-calculus method. All these algorithms run
in sub-exponential time. Let 
\[L_{N}(\alpha)=\exp(O((\log N)^\alpha (\log\log N)^{1-\alpha})).\]
%where $0 < \alpha < 1$. 
For a finite field $\F_q$,
successful efforts have been made to reduce the heuristic 
complexity of these algorithms 
from $L_{q} (1/2)$ to $L_{q} (1/3)$.
See \cite{Adleman79, Adleman94, Coppersmith84, Gordon93, JouxLe06, JLSV06, Merkle79, Pollard78}.


A sequence of breakthrough results \cite{GGMZ13, Joux13a, Joux13b} obtained
recently on the discrete logarithm problem over finite fields culminated 
in a discovery of a quasi-polynomial time algorithm 
for small characteristic fields \cite{BGJT13v1,BGJT13v2}.
For a finite field $ \F_{q^{2 k}} $ with $ k < q $,
their algorithm runs in heuristic time  $ q^{O(\log k)} $. 
This result, if correct, essentially removes the discrete logarithm
over small characteristic  fields from hard problems in cryptography.

\section{Smoothness of integers and polynomials}
Most efficient algorithms on the discrete logarithm problem over finite fields 
rely on smoothness of integers or  polynomials.
The basic idea is to reduce the discrete logarithm of a bigger norm element
to discrete logarithms of elements of smaller norm.
%Thus the analysis of the
%probability for integers and polynomials plays an important role.

\begin{definition}
An integer $n=\prod_{i=1}^{k}p_i^{e_i}$ is $ B $-smooth
if $p_i<B$ for a chosen upper bound $B$ for all $1\leqslant i \leqslant k$.
A polynomial of degree $n$ over a finite field $\F_q$ is $ m $-smooth if all its irreducible factors have  degrees 
$\leqslant m  $. Denote the probability that a random polynomial of degree $n$ ($\geqslant m$) 
over  $\F_q$ is $m$-smooth by $p(n,m)$.
\end{definition}

\begin{remark}
In \cite{Adleman79}, the author attributed the term smoothness to R. Rivest.
\end{remark}

Odlyzko \cite{Odlyzko84} showed that 
\[
p(n,m) = exp((1+o(1))\frac{n}{m}\log_{e}\frac{m}{n}),
\]
in the case when $ch(\F_q)=2,n\rightarrow \infty$ and $n^{\frac{1}{100}}\leqslant m \leqslant n^{\frac{99}{100}}$.
Lovorn \cite{Lovorn92} generalized the conclusion to any prime power $q$. Car \cite{Car87} obtained an asymptotic
result in terms of Dickman function when $m$ is large compared with $n$. Panario et al. \cite{PGF98} showed that
the Dickman function approaches the number of smooth polynomials when $m \geqslant (1+\epsilon)(\log n)^{1/k}$ for
a positive integer $k$.


\section{Lattice theory}
In this section, we shall give a brief introduction to the lattice theory.
More information about lattice theory can be found in books such as \cite{MG02} and \cite{Hua82}.

\subsection{Basic concepts}
\begin{definition}
 A lattice in $\R^m$ is the set
\[
\mathcal{L}=\{\sum_{i=1}^{n}x_i \mathbf{b}_i|x_i\in\Z\},
\]
where $n \leqslant m$ and $\mathbf{b}_1,\mathbf{b}_2,\ldots,\mathbf{b}_n$ are linearly
independent vectors over $\R$ and $\mathbf{b}_i \in \R^n$ for $1\leqslant i \leqslant n$.
\end{definition}

\begin{remark}
Given a lattice $\L$ defined as above, we call $m,n$ the dimension and rank of the lattice $\L$, respectively.
If $m = n$, we call it a full rank lattice.
And we call the set of vectors $\mathbf{b}_1,\mathbf{b}_2,\cdots,\mathbf{b}_n$  a lattice basis
and write 
\[
B=[\mathbf{b}_1,\mathbf{b}_2,\ldots,\mathbf{b}_n],
\]
where $\mathbf{b}_i$ is written as a column vector for $1\leqslant i \leqslant n$.
Equivalently, we say the basis generates the lattice.
\end{remark}

Geometrically, the lattice consists of the intersection points of an infinite, regular $n$-dimensional grid.

\begin{example}
Let $m=n=2$, i.e., we consider a full rank lattice in $\R^2$.
Let the lattice basis be
\[
\mathbf{b}_1 = \begin{bmatrix}1\\0\end{bmatrix}, \qquad
\mathbf{b}_2 = \begin{bmatrix}0\\1\end{bmatrix}.
\]
The lattice is generated by $B=[\mathbf{b}_1,\mathbf{b}_2]\in\R^{2\times 2}$.
Pictorially, it is shown in Figure \ref{fig:latticeb1b2}.

%\vspace{5 mm}
\begin{figure}[h]
\centering
\begin{tikzpicture} 
%x and y axis 
\draw[->] (-3,0) -- (3,0);
\draw[->] (0,-3) -- (0,3);
% basis vectors (1,0),(0,1)
\draw[->,thick] (0,0) -- (1,0) node [above,scale=0.5] {$\mathbf{b}_1$=(1,0)};
\draw[->,thick] (0,0) -- (0,1) node [above,scale=0.5] {$\mathbf{b}_2$=(0,1)};
%\clip (-5,-5) rectangle (5cm,5cm); % Clips the picture...
\clip (-3,-3) rectangle (3cm,3cm); % Clips the picture...
% combinaions of the basis
\foreach \m in {-5,...,5}
  {\draw[style=dashed,domain=-10:10] plot (\x,\m);}
%  {\draw[style=dashed,red!50,domain=-10:10] plot (\x,\m);}
\foreach \n in {-5,...,5}
  {\draw[style=dashed,domain=-10:10] plot (\n,\x);}
\end{tikzpicture}
\caption{Lattice generated by $\mathbf{b}_1,\mathbf{b}_2$} \label{fig:latticeb1b2}
\end{figure}
%\vspace{5 mm}
\end{example} 

\begin{example}
Let $m=n=2$, i.e., we consider a full rank lattice in $\R^2$.
Let the lattice basis be
\[
\mathbf{b}_1' = \begin{bmatrix}1\\0\end{bmatrix}, \qquad
\mathbf{b}_2' = \begin{bmatrix}1\\1\end{bmatrix}.
\]
The lattice is generated by $B'=[\mathbf{b}_1',\mathbf{b}_2']\in\R^{2\times 2}$.
Pictorially, it is shown in Figure \ref{fig:latticeb1'b2'}.


%\vspace{5 mm}
\begin{figure}[h]
\centering
\begin{tikzpicture} 
%x and y axis 
\draw[->] (-3,0) -- (3,0);
\draw[->] (0,-3) -- (0,3);
% basis vectors (1,0),(0,1)
\draw[->,thick] (0,0) -- (1,0) node [above,scale=0.5] {$\mathbf{b}_1'$=(1,0)};
\draw[->,thick] (0,0) -- (1,1) node [above,scale=0.5] {$\mathbf{b}_2'$=(1,1)};
\clip (-3,-3) rectangle (3cm,3cm); % Clips the picture...
% combinaions of the basis
\foreach \m in {-10,...,10}
  {\draw[style=dashed,domain=-10:10] plot (\x+\m,\x);}
\foreach \n in {-5,...,5}
  {\draw[style=dashed,domain=-10:10] plot (\n,\x+\n);}
\end{tikzpicture}
\caption{Lattice generated by $\mathbf{b}_1',\mathbf{b}_2'$} \label{fig:latticeb1'b2'}
\end{figure}
%\vspace{5 mm}
\end{example}


\begin{remark}
Graphically, the intersection sets are the same as the last example.
One can check that the lattice generated by $B$ is the same as the one generated by $B'$.
In this case, we call $B$ and $B'$ equivalent, in other words, equivalent bases generate
the same lattice. 
\end{remark}

\iffalse
Given two bases matrix $B,B'\in \R^{m\times n}$. 
There are two ways to decide whether they generate the same lattice.
\begin{itemize}
\item Geometric characterization: Let $B'=[\mathbf{b}_1',\mathbf{b}_2',\ldots,\mathbf{b}_n']$.
Consider the half open parallelepiped 
\[
P(B') = \{B'\mathbf{x}:0\leqslant x_i < 1\}.
\]
Then, $B$ and $B'$ generate the same lattice if and only if $P(B')$ does not contain other 
lattice points except the original.
\item Algebraic characterization: $B$ and $B'$ generate the same lattice if and only if there exists a 
uni-modular matrix $U\in \Z^{n\times n}$, whose determinant is 1 by definition, such that
\[
B = U*B'.
\] 
\end{itemize}
\fi

\begin{definition}
The determinant of a lattice $\L(B)$ is the $n$-dimensional volume of the fundamental 
parallelepiped $P(B)$, which is spanned by the basis vectors. 
In other words,
\[
P(B) = \{B\mathbf{x}:0\leqslant x_i \leq 1\}.
\]
We denote the determinant 
of $\L$ by $\det(\L)$.
\end{definition}

\iffalse
\begin{example}
Consider the lattice in $\R^3$ generated by the basis
\[
\mathbf{b}_3 = \begin{bmatrix}1\\0\\1\end{bmatrix}, \qquad
\mathbf{b}_4 = \begin{bmatrix}1\\1\\0\end{bmatrix}.
\]
Clearly, this lattice is not of full rank.
\end{example}
\fi

\subsection{Computational problems}
Minkowski's convex body theorem \cite[page 12]{MG02} asserts
that given any convex set in $\R^n$, which is symmetric with respect
to the origin and with volume greater than $2^n\det(\mathcal{L})$,
there exists a non-zero lattice point in the set. As a corollary,
Minkowski's first theorem implies that the length of the shortest
vector in $\mathcal{L}$ satisfies
$$\lambda_1<\sqrt{n}\det(\mathcal{L})^{1/n}.$$

While no known efficient algorithm can find the shortest vector, or
even a vector within the Minkowski's bound, there are  polynomial-time
algorithms to approximate the shortest vector in a lattice.
% such as LLL reduction and BKZ reduction algorithm.
The Lenstra-Lenstra-Lovasz (LLL) algorithm can find in polynomial-time
a vector whose length is at most $(2/\sqrt{3})^n$ times the
length of  the shortest vector of a lattice \cite[page 33]{MG02}. 
The Block-Korkine-Zolotarev (BKZ) algorithm \cite{MG02} can
achieve a better approximation factor.

\subsection{Lattices and groups}
Let $\L(B)$ be a rank $n$ lattice and let $\L(B')$ be a full rank sublattice of $\L(B)$. 
Since each column vector of $B'$ is a linear combination of column vectors of $B$, there exists a nonsingular
integer matrix $T\in \Z^{n \times n}$ such that 
\[
B' = B*T.
\]

Recall that how we define the congruent classes of integers as an additive group. Let $m\in \Z$, then 
$G=\langle m \rangle$ is a subgroup of $\Z$. Two integers $a,b$ are equivalent if $a-b\in G$. 
If they are equivalent, we denote this by 
\[
a \equiv b \pmod m.
\]

Following a similar procedure, we define an equivalent relation on $\L(B)$ as follows: given two lattice points $\mathbf{u},\mathbf{v}\in \L(B)$,
$\mathbf{u}$ is equivalent to $\mathbf{v}$ if and only if $\mathbf{u}-\mathbf{v}\in \L(B')$. If they are equivalent,
then we denote this by 
\[
\mathbf{u}\equiv \mathbf{v} \pmod {\L(B')}.
\]

Furthermore, we can define an operation on the equivalent classes as follows:
\[
[\mathbf{u}]+[\mathbf{v}]=[\mathbf{u}+\mathbf{v}].
\]  
One can check that the quotient $G=\L(B)/\L(B')$ is an additive group with respect to the defined operation. And the map
\[ 
\phi: \L(B) \rightarrow  G = \L(B)/\L(B')
\]
given by 
\[
\mathbf{u} \mapsto [\mathbf{u}],
\]
is a group homomorphism, where $ker(\phi) = \L(B')$.

\begin{remark}
There are different representations for the elements of $G$. Two well known ways are Hermite Normal Form (HNF)
and Smith Norm Form (SNF).
\end{remark}

\begin{definition}
A square nonsingular integer matrix $T\in \Z^{n\times n}$ is in HNF if it satisfies the following conditions:
\begin{itemize}
\item $T$ is upper triangular, i.e., $t_{i,j} = 0$ if $i > j$,
\item All diagonal elements of $T$ are strictly positive, i.e., $t_{i,i} > 0 $ for $1\leqslant i \leqslant n$,
\item All non diagonal elements are reduced modulo the corresponding diagonal element on the same row, i.e., $0\leqslant t_{i,j} < t_{i,i}$ 
if $i < j$.
\end{itemize}
\end{definition}

\begin{definition}
A matrix $T\in \Z^{n\times n}$ is in SNF if it satisfies the following conditions:
\begin{itemize}
\item $T$ is diagonal, i.e., $t_{i,j} = 0$ if $i\neq j$,
\item All diagonal elements are non negative, i.e., $t_{i,i} \geqslant 0$ for $1\leqslant i \leqslant n$,
\item $t_{i,i}|t_{i+1,i+1}$ for $1\leqslant i < n$.
\end{itemize}
\end{definition}

\iffalse
\begin{example}
Let 
\[
B = [\mathbf{b}_1,\mathbf{b}_2]=
\begin{bmatrix}
1 & 0 \\
0 & 1 
\end{bmatrix},
\quad
B' = [\mathbf{b}_1',\mathbf{b}_2']=
\begin{bmatrix}
3 & 3 \\
0 & 2 
\end{bmatrix}.
\]
Clearly, $\L(B')$ is a sublattice of $\L(B)$. Also we can take $T=B'$ such that
\[
B' = B*T.
\]
%The group $G=\L(B)/\L(B')$ has order $6$, which is shown in Figure \ref{fig:sublattice}.

Firstly, we compute the HNF of $T$ and get
\begin{equation} \label{hnfequ}
\begin{bmatrix}
3 & 0 \\
0 & 2 
\end{bmatrix}
=
\begin{bmatrix}
3 & 3 \\
0 & 2 
\end{bmatrix}
\begin{bmatrix}
1 & -1 \\
0 & 0 
\end{bmatrix}.
\end{equation}
%Equation \ref{hnfequ} implies that 

Next, we compute the SNF of $T$ and get
\begin{equation} \label{snfequ}
\begin{bmatrix}
1 & 0 \\
0 & 6 
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 \\
-2 & -3 
\end{bmatrix}
\begin{bmatrix}
3 & 3 \\
0 & 2 
\end{bmatrix}
\begin{bmatrix}
2 & 5 \\
-1 & -3 
\end{bmatrix}.
\end{equation}

\iffalse
\vspace{5 mm}
\begin{figure}[h]
\centering
\begin{tikzpicture} 
%x and y axis 
\draw[->] (0,0) -- (7,0);
\draw[->] (0,0) -- (0,3);
% basis vectors (1,0),(0,1)
\draw[->,thick] (0,0) -- (3,0) node [above,scale=0.5] {$P,\mathbf{b}_1'$=(3,0)};
\draw[->,thick] (0,0) -- (3,2) node [above,scale=0.5] {$Q,\mathbf{b}_2'$=(3,2)};
\draw[->,dashed] (3,0) -- (6,2);
\draw[->,dashed] (3,2) -- (6,2);
\fill (0,0) circle (1 pt) node[below] {$A$};
\fill (1,0) circle (1 pt) node[below] {$B$};
\fill (2,0) circle (1 pt) node[below] {$C$};
\fill (2,1) circle (1 pt) node[below] {$D$};
\fill (3,1) circle (1 pt) node[below] {$E$};
\fill (4,1) circle (1 pt) node[below] {$F$};
\end{tikzpicture}
\caption{Group generated by lattice quotient} \label{fig:sublattice}
\end{figure}
\fi

\end{example}
\fi
