Two Grumpy Giants and a Baby

Free registration required

Executive Summary

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.

  • Format: PDF
  • Size: 427.6 KB