Skip to content



A birthday paradox for Markov chains, with an optimal bound for collision in the Pollard Rho algorithm for discrete logarithm

Montenegro, R (Massachusetts Lowell)
Wednesday 26 March 2008, 14:35-15:05

Seminar Room 1, Newton Institute


We show a Birthday Paradox for self-intersections of Markov chains with uniform stationary distribution. As an application, we analyze Pollard's Rho algorithm for finding the discrete logarithm in a cyclic group G and find that, if the partition in the algorithm is given by a random oracle, then with high probability a collision occurs in order |G|^0.5 steps. This is the first proof of the correct order bound which does not assume that every step of the algorithm produces an i.i.d. sample from G.

Related Links


[pdf ]




The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧