On Computing Logarithms Over Finite Fields

The problem of computing logarithms over finite fields has proved to be of interest in different fields [4]. Subexponential time algorithms for computing logarithms over the special cases GF(p), GF(p2) and GF(pm) for a fixed p and m → ∞ have been obtained. In this paper, we present some results for obtaining a subexponential time algorithms for the remaining cases GF(pm) for p → ∞ and fixed m ≠ 1, 2. The algorithm depends on mapping the field GF(pm) into a suitable cyclotomic extension of the integers (or rationals). Once an isomorphism between GF(pm) and a subset of the cyclotomic field Q(θ_q) is obtained, the algorithms becomes similar to the previous algorithms for m = 1.2.A rigorous proof for subexponential time is not yet available, but using some heuristic arguments we can show how it could be proved. If a proof would be obtained, it would use results on the distribution of certain classes of integers and results on the distribution of some ideal classes in cyclotomic fields.