Wednesday, April 25th, 2007
2:30pm - 3:30pm, in Science 2-065

Ravi Montenegro

UMass Lowell

A Near Optimal Bound for Pollard's Rho to Solve Discrete Log

Abstract: We analyze the classical Pollard's Rho algorithm for finding the discrete logarithm in a cyclic group $G$. We prove that, with high probability, a collision occurs and the discrete logarithm found in $O(\sqrt{G\log |G|\,\log \log |G|})$ steps, not far from the widely conjectured value of $\Theta(\sqrt{|G|})$. This is done by analyzing an appropriate nonreversible, nonlazy random walk on a discrete cycle of (odd) length $|G|$, and showing that the mixing time of the walk is $O(\log |G| \log \log |G|)$. Joint work with Jeong-Han Kim (Microsoft Research) and Prasad Tetali (Georgia Tech).