A birthday paradox for Markov chains, with an optimal bound for collision in the Pollard Rho algorithm for discrete logarithm
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.
- http://www.ravimontenegro.com/research/prho.pdf - Preprint of the paper
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.