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.