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

DOI10.1214/09-AAP625zbMath1195.60096arXiv0712.0220OpenAlexW2051025109WikidataQ123010543 ScholiaQ123010543MaRDI QIDQ968774

Jeong Han Kim, Yuval Peres, Prasad Tetali, Ravi Montenegro

Publication date: 6 May 2010

Published in: The Annals of Applied Probability, Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0712.0220

zbMATH Keywords

Markov chainself intersectioncollision timemixing timediscrete logarithmPollard rhoPollard's RhoBirthday Paradox

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Number-theoretic algorithms; complexity (11Y16) Factorization (11Y05)

Related Items (8)

A fourth‐moment phenomenon for asymptotic normality of monochromatic subgraphs ⋮ Normal approximation and fourth moment theorems for monochromatic triangles ⋮ Accelerating Pollard's rho algorithm on finite fields ⋮ Recent progress on the elliptic curve discrete logarithm problem ⋮ Rigorous analysis of a randomised number field sieve ⋮ The Second-Moment Phenomenon for Monochromatic Subgraphs ⋮ On a lower bound for the Chung-Diaconis-Graham random process ⋮ Solving discrete logarithm problems faster with the aid of pre-computation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The range of stable random walks
• Random walks arising in random number generation
• Parallel collision search with cryptanalytic applications
• Markov chain intersections and the loop-erased walk
• On the Chung-Diaconis-Graham random process
• A monte carlo method for factorization
• An improved algorithm for computing logarithms over<tex>GF(p)</tex>and its cryptographic significance (Corresp.)
• Monte Carlo Methods for Index Computation (mod p)
• Non-Degeneracy of Pollard Rho Collisions
• Algorithmic Number Theory

This page was built for publication: A birthday paradox for Markov chains with an optimal bound for collision in the Pollard rho algorithm for discrete logarithm