[YAYERKA]

Thanks for posting; found many sections interesting especially 3.2;

>3.2. Does NSA have an $n^{1/3}$-algorithm for finding elliptic curve discrete logs? ...

In 2013 Bernstein and Lange described such an algorithm albeit with intractable pre-computation costs. [https://www.iacr.org/conferences/asiacrypt2013/slides/44.pdf]

In the paper Koblitz and Menezes say "it is conceivable that the NSA has found (or believes that there might exist) a similar algorithm that requires far less precomputation."

This made we wonder; are there any historic example(s) of an algorithm we have improved over time which lead to the side stepping of a previously unavoidable and large pre-computation?

[pbsd]

It is not a common occurrence, but it does happen occasionally.

Once upon a time the best known way to compute discrete logarithms was Shanks's Baby-Step Giant-Step. This method begins by constructing a table of size sqrt(p), and then finds a logarithm in time sqrt(p) as well. But in 1978, Pollard came up with the rho algorithm, which did not require any storage beyond 2 group elements, and had the same asymptotic runtime! This method relies on collision-finding, and is still the best algorithm today---in a modified fashion to make it parallelizable---to attack elliptic curves.

Another example happened in integer factorization, but is more nuanced. In the early 1980s, the best known integer factorization algorithm to break semi-primes (i.e., RSA keys) was the quadratic sieve. Now, the quadratic sieve runs in time exp( sqrt( log n log log n ) ), but also requires storage proportional to the size of its factor base---exp( 1/2 sqrt( log n log log n ) ). Then in 1985 Lenstra came up with the elliptic curve method, which once again requires little storage and has the same asymptotic runtime as the quadratic sieve. In practice, however, the quadratic sieve will be faster for RSA numbers. And in 1990, the number field sieve improved the running time to something curve-based methods could not match.

[YAYERKA]

Thanks for your response; 1971 Shanks' BSGS improvement to 1974 Pollard Rho for DLP is indeed a nice example.

[YAYERKA]

My mistake; 1978 Pollard's Rho algorithm for DLP. Was looking at Pollard's Rho for integer factorization at the time. On that note; what a monster this Pollard character. Wonder what he is up to these days.

[pbsd]

Retired: https://sites.google.com/site/jmptidcott2

[YAYERKA]

Following the "List of my papers" section from the "Number Theory" page https://sites.google.com/site/jmptidcott2/nthy

>Some authors even applied the name "kangaroo" to any random walk in a cyclic group. This is zoologically absurd (a kangaroo cannot jump in one bound to another continent) - and mathematically confusing.

Spurred by this thread and especially after studying BSGS and the Pollard Rho for DLP set of algorithms more in depth over the last few days; I found his clarification and justification regarding the "taxonomy" of these methods entertaining and enlightening. Thanks again.