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 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|log <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> |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|).