Granger, RobertKleinjung, ThorstenZumbragel, Jens2016-09-052016-09-052016-09-05201810.1090/tran/7027https://infoscience.epfl.ch/handle/20.500.14299/129085WOS:000425780200005For~$q$ a prime power, the discrete logarithm problem (DLP) in~$\F_{q}$ 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$. We present an algorithm for computing discrete logarithms with which we prove that for each prime~$p$ there exist infinitely many explicit extension fields~$\mathbb{F}_{p^n}$ in which the DLP can be solved in expected quasi-polynomial time. Furthermore, subject to a conjecture on the existence of irreducible polynomials of a certain form, the algorithm solves the DLP in all extensions~$\mathbb{F}_{p^n}$ in expected quasi-polynomial time.text::journal::journal article::research article