Paper 2015/685 Original: eprint.iacr.org/2015/685 ↗

On the discrete logarithm problem in finite fields of fixed characteristic

Abstract

For $q$ a prime power, the discrete logarithm problem (DLP) in $\mathbb{F}_{q}^{\times}$ consists in finding, for any $g \in \mathbb{F}_{q}^{\times}$ and $h \in \langle g \rangle$, an integer $x$ such that $g^x = h$. For each prime $p$ we exhibit infinitely many extension fields $\mathbb{F}_{p^n}$ for which the DLP in $\mathbb{F}_{p^n}^{\times}$ can be solved in expected quasi-polynomial time.