Vol. 1, No. 1, 2013

Download this article
Download this article For screen
For printing
Recent Volumes
The Open Book Series
About the Series
Ethics Statement
Other MSP Publications
Two grumpy giants and a baby

Daniel J. Bernstein and Tanja Lange

Vol. 1 (2013), No. 1, 87–111

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 anticollisions” 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 anticollisions” that can at least partially be avoided. For example, after (1.5 + o(1)) additions in a group of order (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).

Pollard rho, baby-step giant-step, discrete logarithms, complexity
Mathematical Subject Classification 2010
Primary: 11Y16
Published: 14 November 2013
Daniel J. Bernstein
Department of Computer Science
University of Illinois at Chicago
Chicago, IL 60607-7053
United States
Tanja Lange
Department of Mathematics and Computer Science
Technische Universiteit Eindhoven
P.O. Box 513
5600 MB Eindhoven
The Netherlands