DISCRETE LOGARITHMS IN GF(P) USING THE NUMBER-FIELD SIEVE

Recently, several algorithms using number field sieves have been given to factor a number n in heuristic expected time Ln [1/3;c], where L(n)[v; c] = exp{(c + o(1))(log n)v(log log n)1-v} for n --> infinity. This paper presents an algorithm to solve the discrete logarithm problem for GF(p) with heuristic expected running time L(p)[1/3; 3(2/3)]. For numbers of a special form, there is an asymptotic practical version of the algorithm.