Abstract
For q a prime power, the discrete logarithm problem (DLP) in Fq consists in finding, for any g ∈ F × q and h ∈ hgi, 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 Fpn 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 Fpn in expected quasi-polynomial time.