**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\ldots+o(1);
and this paper's new two-grumpy-giants-and-a-baby method has probability 0.71875+o(1).

**Category / Keywords: **public-key cryptography / Discrete logarithms, Pollard rho, baby-step giant-step, anticollisions

**Publication Info: **Expanded version of ANTS 2012 paper.

**Date: **received 2 Jun 2012, last revised 10 Jul 2012

**Contact author: **tanja at hyperelliptic org

**Available format(s): **PDF | BibTeX Citation

**Version: **20120710:183329 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]