Near Optimal Bounds for Collision in Pollard Rho for Discrete Log

DOI10.1109/FOCS.2007.38MaRDI QIDQ6478273zbMATH OpenFDO

Authors Jeong Han Kim, Ravi Montenegro, Prasad Tetali

Publication date 19 November 2006

Full work available at URL https://doi.org/10.1109/FOCS.2007.38

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Randomized algorithms (68W20)

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|loglog|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|lo{g}^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|loglog|G|)$.

This page was built for publication: Near Optimal Bounds for Collision in Pollard Rho for Discrete Log

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6478273)