\chapter{Introduction}

In this dissertation, we consider problems concerning deep holes of generalized Reed-Solomon codes and discrete logarithms over finite fields.

The motivation for the studies stems from the increasing requirements for transmitting messages over realistic channels, which are often imperfect.
This can be illustrated by the following example.
Suppose Alice and Bob want to communicate over a channel. 
For the sake of simplicity, we assume that all the information has been transformed into digital signals. 
We start from considering the following abstract channel model as in Figure \ref{fig:OrgChn},
which includes a source (Alice), a destination (Bob), and a channel. 

\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] (c) [right of=a, node distance = 4cm] {$channel$};
	\node [int] (b) [right of=c, node distance = 4cm] {$Bob$};
	\path[->] (a) edge node {$signal$} (c);
	\path[->] (c) edge node {$signal$} (b);
\end{tikzpicture}
\caption{Original communication channel model} \label{fig:OrgChn}
\end{figure}
\vspace{5 mm}



There are two fundamental issues of consideration:
\begin{itemize}
\item Correctness:  In reality, there is noise in the channel, which may interrupt the transmitted signal.
If Alice sends the message in the original form, the message received
by Bob may not be the same as sent by Alice. 

\item Privacy: The openness of the channel implies that other people, say Eve, may get the message over the channel.
If Alice sends the message in the plain text form, then Eve can get the text and understand its meaning.
\end{itemize}

The main tools developed to solve these problems are error-correcting code theory and cryptography.

\section{Error-correcting codes and deep holes for linear codes}
In this section, the problem of transmitting information over noisy channels is considered as in Figure \ref{fig:Cwn}. In a seminal paper published in 1948 \cite{Shannon48}, 
Shannon established information theory to solve this problem. 

\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] (c) [right of=a, node distance = 4cm] {$channel$};
	\node [int] (n) [below of=c, node distance = 2cm] {$noise$};
	\node [int] (b) [right of=c, node distance = 4cm] {$Bob$};
	\path[->] (a) edge node {$signal$} (c);
	\path[->] (c) edge node {$signal$} (b);
	\path[->] (n) edge node {}         (c);
\end{tikzpicture}
\caption{Communication channel model with noise} \label{fig:Cwn}
\end{figure}
\vspace{5 mm}

Because of the existence of noise, it may happen that a signal $0$ is sent but
a signal $1$ is received.

\begin{example}
The memoryless binary symmetric channel is defined as follows. The alphabet is $\F_2=\{0,1\}$.
The symmetric channel means that it flips each input bit with crossover probability $0\leqslant p \leqslant 1$.
Thus the transmission of a single bit can be described pictorially as in Figure \ref{fig:Bsc}.

\vspace{5 mm}
\begin{figure}[h]
\centering
\begin{tikzpicture}
%\tikzstyle{every node} = [circle, fill = gray!30]
\node (a) [circle] at (0,0) {1};
\node (b) [circle] at (0,3) {0};
\node (c) [circle] at (3,0) {1};
\node (d) [circle] at (3,3) {0};
\draw[->] (a) -- (c) node[pos=.5,sloped,below] {$1-p$};
\draw[->] (a) -- (d) node[pos=.5,sloped,below] {$p$};
\draw[->] (b) -- (c) node[pos=.5,sloped,above] {$p$};
\draw[->] (b) -- (d) node[pos=.5,sloped,above] {$1-p$};
\end{tikzpicture}
\caption{Binary symmetric channel} \label{fig:Bsc}
\end{figure}
\vspace{5 mm}

The memoryless channel means that the probability of flipping each
bit is independent from other signals. In other words,
let $\mathbf{t}=t_1t_2\cdots t_n\in\F_2^n, \mathbf{r}=r_1r_2\cdots r_n\in \F_2^n$, we have
\[
P\{\mathbf{r}\quad received\mid \mathbf{t}\quad transmitted\}
=\prod_{i=1}^{n}P\{r_i\quad received \mid t_i\quad transmitted\},
\]
where $P\{E\}$ denotes the probability that the event $E$ happens.
\end{example}
 
In order to detect and correct possible errors of signals during the transmission,
the encoding and decoding procedures are introduced as in Figure \ref{fig:cwc}.

\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 = 2cm] {$encoder$};
	\node [int] (c) [right of=e, node distance = 4cm] {$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$};
	\path[->] (a) edge node {} (e);
	\path[->] (e) edge node {$codeword$} (c);
	\path[->] (c) edge node {$codeword$} (d);
	\path[->] (d) edge node {} (b);
	\path[->] (n) edge node {}         (c);
\end{tikzpicture}
\caption{Communication channel model with encoder and decoder} \label{fig:cwc}
\end{figure}
\vspace{5 mm}

 
The encoding procedure is a map that transforms signal alphabets into codewords,
and the decoding is the inverse procedure. 
One of the fundamental results of Shannon \cite{Shannon48} is the Noisy-Channel 
Coding theorem. Informally speaking, the theorem asserts that under certain conditions,
there exist codes that make the error probability at the receiver 
arbitrarily small. A large number of codes have been designed.
Hamming pioneered this field \cite{Hamming50}.
Reed and Solomon \cite{ReedSo60} introduced Reed-Solomon codes in 1960,
which is of importance both in theory and in practice.

For the sake of usefulness,
there should exist an efficient decoding algorithm. In practice, the
maximum-likelihood decoding is used, which aims to minimize the error probability.
In certain cases, such as the binary symmetric channel with crossover probability $p < 1/2$,
the maximum-likelihood decoding is equivalent to the nearest-codeword decoding.
In the nearest-codeword decoding, a received word is decoded as
the closest codeword under the measure of Hamming distance.
A deep hole of a code is one word which has the largest distance to the code.
In this dissertation, we classify deep holes in a special case for generalized 
Reed-Solomon codes.

\newpage
\section{Cryptography and discrete logarithms over finite fields}
Confidentiality is a significant concern in the practice of communication.
In a paper published in 1949 \cite{Shannon49}, 
Shannon considered the problem of secure communication. 
Figure \ref{fig:cwe} shows a simplified model.

\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] (c) [right of=a, node distance = 4cm] {$channel$};
	\node [int] (n) [below of=c, node distance = 2cm] {$Eve$};
	\node [int] (b) [right of=c, node distance = 4cm] {$Bob$};
	\path[->] (a) edge node {$message$} (c);
	\path[->] (c) edge node {$message$} (b);
	\path[->] (n) edge node {}         (c);
\end{tikzpicture}
\caption{Communication channel model with eavesdropper} \label{fig:cwe}
\end{figure}
\vspace{5 mm}

Since there exists a third party over the channel, the encryption and decryption procedures are introduced to keep the message secure as shown in Figure \ref{fig:cwed}.
The goal of an encryption procedure is to make the transformed message look random to the third party, 
while the receiver can recover the original message with the decryption procedure.


\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 = 2cm] {$encryption$};
	\node [int] (c) [right of=e, node distance = 4cm] {$channel$};
	\node [int] (d) [right of=c, node distance = 4cm] {$decryption$};
	\node [int] (n) [below of=c, node distance = 2cm] {$Eve $};
	\node [int] (b) [right of=d, node distance = 2cm] {$Bob$};
	\path[->] (a) edge node {} (e);
	\path[->] (e) edge node {$cipher text$} (c);
	\path[->] (c) edge node {$cipher text$} (d);
	\path[->] (d) edge node {} (b);
	\path[->] (n) edge node {}         (c);
\end{tikzpicture}
\caption{Communication channel model with encryption and decryption} \label{fig:cwed}
\end{figure}
\vspace{5 mm}

The encryption procedure and its inverse are important components of cryptography.
In the early era, the confidentiality was usually achieved with some physical aid. 
In the modern era, cryptography has put its feet on more solid foundations \cite{Goldreich01}, such as
information theory, computational complexity, and mathematics.

There are two main branches of ciphers: one is the symmetric-key (or private-key) cipher and the other is 
the asymmetric-key (or public-key) cipher. Symmetric-key ciphers are implemented as either stream ciphers or block ciphers.
The considerable advantage of the symmetric-key cipher is its speed.
One of the drawbacks of the symmetric-key cipher is that the two participants 
need to share a key before the communication, which is a problem if there are many users
since $N$ users need $\binom{N}{2}$ keys. 

In 1976, Diffie and Hellman \cite{DiffieHe76} pioneered the public-key cryptography.
In public-key cryptography, each participant has a pair of keys: one is the public key
and the other is the private key. 
The public-key ciphers are usually
built on some hard computational problems, among which the integer factorization 
and discrete logarithms problem over finite fields are two commonly used ones.
For example, Diffie and Hellman \cite{DiffieHe76} designed a key-exchange scheme based on
the discrete logarithms over finite fields.
Rivest, Shamir, and Adleman \cite{RSA78} developed a cryptosystem based on the
integer factorization. ElGamal \cite{ElGamal85} established a 
cryptosystem based on the discrete logarithm problem.  


For the sake of security, cryptanalysis efforts have been made to consider the hardness (or weakness) of
these problems underlying these cryptosystems. In particular, many algorithms have been designed to attack the discrete logarithm
problem over finite fields. Shor \cite{Shor97} designed a randomized algorithm to solve the discrete logarithm in polynomial time on 
a hypothetical quantum computer. Many classical algorithms to compute discrete logarithms have been developed during the last decades, 
such as index calculus methods, the number field sieve, and the function field sieve.
The state-of-the-art general purpose algorithm  runs in 
sub-exponential time on classical computer models such as Turing machines. Recently, a quasi-polynomial time algorithm \cite{BGJT13v1, BGJT13v2} was proposed for 
the discrete logarithm problem over finite fields of small characteristics on classical computer models.
In this dissertation, we shall study the original form of this algorithm \cite{BGJT13v1}. Some heuristics are shown to be problematic 
and a solution is proposed.




