@inproceedings{bed2ed6a69f3436a9fc0fb45f2215e10,

title = "Spectral analysis of Pollard Rho collisions",

abstract = "We show that the classical Pollard p algorithm for discrete logarithms produces a collision in expected time O(√n(log n)3). This is the first nontrivial rigorous estimate for the collision probability for the unaltered Pollard p graph, and is close to the conjectured optimal bound of O(√n)- The result is derived by showing that the mixing time for the random walk on this graph is O((log n)3); without the squaring step in the Pollard p algorithm, the mixing time would be exponential in log n. The technique involves a spectral analysis of directed graphs, which captures the effect of the squaring step.",

keywords = "Collision time, Discrete logarithm, Expander graph, Mixing time, Pollard Rho algorithm, Random walk, Spectral analysis",

author = "Miller, {Stephen D.} and Ramarathnam Venkatesan",

year = "2006",

doi = "10.1007/11792086_40",

language = "English (US)",

isbn = "3540360751",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "573--581",

booktitle = "Algorithmic Number Theory - 7th International Symposium, ANTS-VII, Proceedings",

address = "Germany",

note = "7th International Symposium on Algorithmic Number Theory, ANTS-VII ; Conference date: 23-07-2006 Through 28-07-2006",

}