An Algorithm to Solve the Discrete Logarithm Problem with the Number Field Sieve

Recently, Shirokauer’s algorithm to solve the discrete logarithm problem modulo a prime

p

has been modified by Matyukhin, yielding an algorithm with running time

$L_{p}[\frac{1}{3},1.09018...]$

, which is, at the present time, the best known estimate of the complexity of finding discrete logarithms over prime finite fields and which coincides with the best known theoretical running time for factoring integers, obtained by Coppersmith. In this paper, another algorithm to solve the discrete logarithm problem in

$\mathbb{F}^{*}_{p}$

for

p

prime is presented. The global running time is again

$L_{p}[\frac{1}{3},1.09018...]$

, but in contrast with Matyukhins method, this algorithm enables us to calculate individual logarithms in a separate stage in time

$L_{p}[\frac{1}{3},3^{1/3}]$

, once a

$L_{p}[\frac{1}{3},1.09018...]$

time costing pre-computation stage has been executed. We describe the algorithm as derived from [6] and estimate its running time to be

$L_{p}[\frac{1}{3},(\frac{64}{9})^{1/3}]$

, after which individual logarithms can be calculated in time

$L_{p}[\frac{1}{3},3^{1/3}]$

.