A BIRTHDAY PARADOX FOR MARKOV CHAINS WITH AN OPTIMAL BOUND FOR COLLISION IN THE POLLARD RHO ALGORITHM FOR DISCRETE LOGARITHM
成果类型：
Article
署名作者：
Kim, Jeong Han; Montenegro, Ravi; Peres, Yuval; Tetali, Prasad
署名单位：
Yonsei University; National Institute for Mathematical Sciences (NIMS), Republic of Korea; Microsoft; University of Massachusetts System; University of Massachusetts Lowell; University System of Georgia; Georgia Institute of Technology
刊物名称：
ANNALS OF APPLIED PROBABILITY
ISSN/ISSBN：
1050-5164
DOI：
10.1214/09-AAP625
发表日期：
2010
页码：
495-521
关键词：
摘要：
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(root vertical bar G vertical bar) steps. Moreover, for the parallelized distinguished points algorithm on J processors we find that Theta(root vertical bar G vertical bar/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.
来源URL：