RSA Laboratories

2.3.9 What are the prospects for a theoretical breakthrough in the discrete logarithm problem?

It is impossible to predict when a mathematical breakthrough might occur; this is why they are called breakthroughs. Factoring algorithms have been studied for hundreds of years, general discrete logarithm algorithms have been extensively studied since the early 1970s, and elliptic curve discrete logarithms have been studied since the mid-1980s. Each time a new algorithm has been announced it has come more or less as a surprise to the research community.

It should be noted that for integer factoring and general discrete logarithms, a "breakthrough" means finding a polynomial time algorithm. However, for elliptic curve discrete logarithms, a breakthrough may consist of just finding a sub-exponential time method.

We mention that a solution to the discrete logarithm problem would be applicable to the factoring problem (see Question 2.3.3).

Top of the page