ON THE DISCRETE LOGARITHM PROBLEM IN FINITE FIELDS OF FIXED CHARACTERISTIC

For q a prime power, the discrete logarithm problem (DLP) in F-q consists of finding, for any g is an element of F-x(q) and h is an element of < g >, 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 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 F-p(n) in expected quasi-polynomial time.