Download Now Free registration required
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