RSA Laboratories

2.3.8 What are the best discrete logarithm methods in use today?

Currently, the best algorithms to solve the discrete logarithm problem (see Question 2.3.7) are broken into two classes: index-calculus methods and collision search methods. The two classes of algorithms differ in the ways they are applied. Index calculus methods generally require certain arithmetic properties to be present in order to be successful, whereas collision search algorithms can be applied much more generally. The absence of more properties in elliptic curve groups prevents the more powerful index-calculus techniques from being used to attack the elliptic curve analogues of the more traditional discrete logarithm based cryptosystems (see Section 3.5).

Index calculus methods are very similar to the fastest current methods for integer factoring and they run in what is termed sub-exponential time. They are not as fast as polynomial time algorithms, yet they are considerably faster than exponential time methods. There are two basic index calculus methods closely related to the quadratic sieve and number field sieve factoring algorithms (see Question 2.3.4).

As of this time, the largest discrete logarithm problem that has been solved was over GF(2503).

Collision search algorithms have purely exponential running time. The best general method is known as the Pollard rho method, so-called because the algorithm produces a trail of numbers that when graphically represented with a line connecting successive elements of the trail looks like the Greek letter rho. There is a tail and a loop; the objective is basically to find where the tail meets the loop. This method runs in time O(Ön) (more accurately, in Ö steps) where n is the size of the group. The largest such problem that has been publicly solved has n ~ 297 (see Question 3.5.5). This is the best known method of attack for the general elliptic curve discrete logarithm problem.

Top of the page