Tenth Algorithmic Number Theory Symposium ANTSX

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 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.5 + o(1)) sqrt(l) additions in a group of order l (without fast negation), the babystepgiantstep 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 twogrumpygiantsandababy method has probability 0.71875 + o(1).
Files available: paper (PDF)
XHTML 1.1 valid, CSS valid