Tenth Algorithmic Number Theory Symposium ANTS-X University of California, San Diego July 9 – 13, 2012 Tenth Algorithmic Number Theory Symposium (ANTS-X) July 9 – 13, 2012

Two grumpy giants and a baby

Daniel J. Bernstein and Tanja Lange

Abstract: Pollard's rho algorithm, along with parallelized, vectorized, and negating variants, is the standard method to compute discrete logarithms in generic prime-order groups. This paper presents two reasons that Pollard's rho algorithm is farther from optimality than generally believed. First, "higher- degree local anti-collisions" make the rho walk less random than the predictions made by the conventional Brent–Pollard heuristic. Second, even a truly random walk is suboptimal, because it suffers from "global anti-collisions" that can at least partially be avoided. For example, after (1.5 + o(1)) sqrt(l) additions in a group of order l (without fast negation), the baby-step-giant-step method has probability 0.5625 + o(1) of finding a uniform random discrete logarithm; a truly random walk would have probability 0.6753... + o(1); and this paper's new two-grumpy-giants-and-a-baby method has probability 0.71875 + o(1).

Files available: paper (PDF)