Two Grumpy Giants and a Baby

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.

Provided by: International Association for Cryptologic Research Topic: Data Centers Date Added: Jul 2012 Format: PDF

Find By Topic