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.



| Question 54 |
| Back to FAQ INDEX |
|RSA Labs' FAQ Home | RSA Home | What's New? |
| RSA & Partner Products | FTP Server | About ... |
| Contact Sales | Contact Technical Support |



Contact RSA Laboratories:
100 Marine Parkway, Suite 500
Redwood City, CA
94065-1031

phone: 415-595-8782
fax: 415-595-1873
Website: http://www.rsa.com/rsalabs/



Website feedback or comments can be sent to : WEBMAVEN@RSA.COM

Copyright ©1996, RSA Laboratories, Inc. All Rights Reserved.
Last Updated: Friday, May 24, 1996