Discrete Logarithms in GF(p)
Several related algorithms are presented for computing logarithms in fields GF(p), p a prime. Heuristic arguments predict a running time of exp((1+0(1)) sqrt (log p log log p) for the initial precomputation phase that is needed for each p, and much shorter running times for computing individual logarithms once the precomputation is done. The running time of the precomputation is roughly the same as that of the fastest known algorithms for factoring integers of size about p.