#### Vol. 1, No. 1, 2013

 Recent Volumes 4: ANTS XIV 3: Hillman: Poincaré Duality 2: ANTS XIII 1: ANTS X
 The Open Book Series All Volumes About the Series Ethics Statement Purchase Printed Copies Author Index MSP Books and Monographs Other MSP Publications
Two grumpy giants and a baby

### Daniel J. Bernstein and Tanja Lange

Vol. 1 (2013), No. 1, 87–111
##### 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 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 $\left(\mathfrak{1}.\mathfrak{5}+o\left(\mathfrak{1}\right)\right)\sqrt{\ell }$ additions in a group of order $\ell$ (without fast negation), the baby-step-giant-step method has probability $\mathfrak{0}.\mathfrak{5}\mathfrak{6}\mathfrak{2}\mathfrak{5}+o\left(\mathfrak{1}\right)$ of finding a uniform random discrete logarithm; a truly random walk would have probability $\mathfrak{0}.\mathfrak{6}\mathfrak{7}\mathfrak{5}\mathfrak{3}\dots +o\left(\mathfrak{1}\right)$; and this paper’s new two-grumpy-giants-and-a-baby method has probability $\mathfrak{0}.\mathfrak{7}\mathfrak{1}\mathfrak{8}\mathfrak{7}\mathfrak{5}+o\left(\mathfrak{1}\right)$.

##### Keywords
Pollard rho, baby-step giant-step, discrete logarithms, complexity
Primary: 11Y16
##### Milestones
Published: 14 November 2013
##### Authors
 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