next up previous
Next: 3.5 DES Up: 3.4 Factoring and Discrete Previous: 3.4.9 What is the

3.4.10 Which is easier, factoring or discrete log?

The asymptotic running time of the best discrete log algorithm is approximately the same as for the best general purpose factoring algorithm. Therefore, it requires about as much effort to solve the discrete log problem modulo a 512-bit prime as to factor a 512-bit RSA modulus. There are experimental evidences that the discrete log problem is slightly harder than factoring: it is suggested 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.

Denis Arnaud