Near Optimal Bounds for Collision in Pollard Rho for Discrete Log

Abstract

We analyze a fairly standard idealization of Pollard's Rho algorithm for finding the discrete logarithm in a cyclic group G. It is found that, with high probability, a collision occurs in $O(\sqrt{|G|\log |G|\log \log |G|})$ steps, not far from the widely conjectured value of $\Theta (\sqrt{|G|})$. This improves upon a recent result of Miller--Venkatesan which showed an upper bound of $O(\sqrt{|G|}{\log }^3|G|)$. Our proof is based on analyzing an appropriate nonreversible, non-lazy random walk on a discrete cycle of (odd) length |G|, and showing that the mixing time of the corresponding walk is $O(\log |G|\log \log |G|)$.

References in corpus (2)

• Markov Chain Intersections and the Loop-Erased Walk
• Spectral Analysis of Pollard Rho Collisions

Cited by in corpus (1)

• A Birthday Paradox for Markov chains with an optimal bound for collision in the Pollard Rho algorithm for discrete logarithm