Near Optimal Bounds for Collision in Pollard Rho for Discrete Log
Jeong Han Kim, Ravi Montenegro, Prasad Tetali · Annual Symposium on Foundations of Computer Science · 2007
We analyze-a fairly standard idealization of Pollard's rho algorithm for finding the discrete logarithm in acyclic group G. It is found that, with high probability, a collision occurs in O(radic( |G|log|G|log log|G|)) steps, not far from the widely conjectured value of Theta(radic|G|). Tins improves upon a recent result of Miller-Venkalesan which showed an upper bound of O(radic|G|log3|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|).