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 $\Theta(\sqrt{|G|})$ steps. Moreover, for the parallelized distinguished points algorithm on J processors we find that $\Theta(\sqrt{|G|}/J)$ steps suffices. These are the first proofs of the correct order bounds which do not assume that every step of the algorithm produces an i.i.d. sample from G.
Publié le : 2010-04-15
Classification:
Pollard’s Rho,
discrete logarithm,
Markov chain,
mixing time,
60J10,
68Q25,
94A60
@article{1268143431,
author = {Kim, Jeong Han and Montenegro, Ravi and Peres, Yuval and Tetali, Prasad},
title = {A Birthday Paradox for Markov chains with an optimal bound for collision in the Pollard Rho algorithm for discrete logarithm},
journal = {Ann. Appl. Probab.},
volume = {20},
number = {1},
year = {2010},
pages = { 495-521},
language = {en},
url = {http://dml.mathdoc.fr/item/1268143431}
}
Kim, Jeong Han; Montenegro, Ravi; Peres, Yuval; Tetali, Prasad. A Birthday Paradox for Markov chains with an optimal bound for collision in the Pollard Rho algorithm for discrete logarithm. Ann. Appl. Probab., Tome 20 (2010) no. 1, pp. 495-521. http://gdmltest.u-ga.fr/item/1268143431/