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.

| Question 54 |