# Two grumpy giants and a baby

D.J. Bernstein, T. Lange

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

## 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\ldots+o(1); and this paper's new two-grumpy-giants-and-a-baby method has probability 0.71875+o(1). Keywords: Pollard rho, baby-step giant-step, discrete logarithms, complexity
Original language English ANTS X (Proceedings of the Tenth Algorithmic Number Theory Symposium, San Diego, California, July 9-13, 2012) E.W. Howe, K.S. Kedlaya Berkeley Mathematical Sciences Publishers 87-111 978-1-935107-00-2 https://doi.org/10.2140/obs.2013.1.87 Published - 2013 10th Algorithmic Number Theory Symposium (ANTS 2012) - University of California, San Diego, United StatesDuration: 9 Jul 2012 → 13 Jul 2012Conference number: 10

### Publication series

Name The Open Book Series 1 2329-9061

### Conference

Conference 10th Algorithmic Number Theory Symposium (ANTS 2012) ANTS X United States San Diego 9/07/12 → 13/07/12