\chapter*{Abstract}

Error-correcting codes and cryptography are two important areas related to information communication.
Generalized Reed-Solomon codes and cryptosystems based on the discrete logarithm problem are important 
representatives of these two fields, respectively.

For a linear code, deep holes are defined to be vectors
that are  further away from codewords than all other vectors.
The problem of deciding whether a received word is a deep hole
for generalized Reed-Solomon codes is co-NP-complete \cite{CM07, GV05}.
%For the extended Reed-Solomon codes $RS_q(\F_q,k)$, a conjecture was made to classify deep holes in \cite{CM07}.

In the recent breakthrough paper by Barbulescu, 
Gaudry, Joux and Thom{\'e} \cite{BGJT13v1, BGJT13v2}, a quasi-polynomial time 
algorithm (QPA) was proposed for the discrete logarithm problem over finite fields
of small characteristics. The time complexity analysis of the algorithm is 
based on several heuristics presented in their  paper. 

In this dissertation, we shall study the deep hole problem of generalized Reed-Solomon codes
and the discrete logarithm problem over finite fields.
On the one hand, we shall classify deep holes for generalized Reed-Solomon codes $RS_q(D,k)$ in a special case.
On the other hand, we shall show that some of the heuristics in BGJT-algorithm are problematic in their original forms \cite{BGJT13v1}, 
in particular, when the field is not a Kummer extension. We propose a solution to the algorithm in non-Kummer cases,
without altering the quasi-polynomial time complexity.
