Two grumpy giants and a baby
Daniel J. Bernstein, Tanja Lange · The Open Book Series · 2013
Pollard's rho algorithm, along with parallelized, vectorized, and negating variants, is the standard method to compute discrete logarithms in generic primeorder 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:5C o.1// p `additions in a group of order `(without fast negation), the baby-step-giant-step method has probability 0:5625 C o.1/ of finding a uniform random discrete logarithm; a truly random walk would have probability 0:6753 : : : C o.1/; and this paper's new two-grumpygiants-and-a-baby method has probability 0:71875 C o.1/.