Studies on Deep Holes and Discrete Logarithms
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.
In the recent breakthrough paper by Barbulescu,
Gaudry, Joux and Thome, 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,
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.
Collections
- OU - Dissertations [9317]