### Question 53. Which is Easier: Factoring or
Discrete Logarithm?

The asymptotic running time of the best discrete logarithm algorithm
is approximately the same as that of the best general-purpose factoring
algorithm. Therefore, it requires about as much effort to solve the discrete
logarithm problem modulo a 512-bit prime as it does to factor a 512-bit
RSA modulus. One paper [LO91] cites experimental evidence that the discrete
logarithm problem is slightly harder than factoring; the authors suggest
that the effort necessary to factor a 110-digit integer is the same as
the effort to solve discrete logarithms modulo a 100-digit prime. This
difference is so slight that it should not be a significant consideration
when choosing a cryptosystem.

Historically, it has been the case that an algorithmic advance in either
problem, factoring or discrete logs, was then applied to the other. This
suggests that the degrees of difficulty of both problems are closely linked,
and that any breakthrough, either positive or negative, will affect both
problems equally.