The Number Field Sieve for Discrete Logarithms

Abstract

We present two general number field sieve algorithms solving the discrete logarithm problem in finite fields. The first algorithm presented deals with discrete logarithms in prime fields, while the second considers prime power fields. We prove, using the standard heuristic, that these algorithms will run in sub-exponential time.

We also give an overview of different index calculus algorithms solving the discrete logarithm problem efficiently for different possible relations between the characteristic and the extension degree.

To be able to give a good introduction to the algorithms, we present theory necessary to understand the underlying algebraic structures used in the algorithms. This theory is largely algebraic number theory.