Data Centers

Two Grumpy Giants and a Baby

Date Added: Jul 2012
Format: PDF

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; "Higher-Degree Local Anti-Collisions" make the rho walk less random than the predictions made by the conventional Brent-Pollard heuristic and even a truly random walk is suboptimal, because it suffers from "Global Anti-Collisions" that can at least partially be avoided.