Mathematics – Probability
Scientific paper
2007-12-03
Annals of Applied Probability 2010, Vol. 20, No. 2, 495-521
Mathematics
Probability
Published in at http://dx.doi.org/10.1214/09-AAP625 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Inst
Scientific paper
10.1214/09-AAP625
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$.
Kim Jeong Han
Montenegro Ravi
Peres Yuval
Tetali Prasad
No associations
LandOfFree
A Birthday Paradox for Markov chains with an optimal bound for collision in the Pollard Rho algorithm for discrete logarithm does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Birthday Paradox for Markov chains with an optimal bound for collision in the Pollard Rho algorithm for discrete logarithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Birthday Paradox for Markov chains with an optimal bound for collision in the Pollard Rho algorithm for discrete logarithm will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-50498