Spectral analysis of Pollard Rho collisions

Stephen D. Miller, Ramarathnam Venkatesan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationAlgorithmic Number Theory - 7th International Symposium, ANTS-VII, Proceedings
PublisherSpringer Verlag
Number of pages9
ISBN (Print)3540360751, 9783540360759
StatePublished - 2006
Event7th International Symposium on Algorithmic Number Theory, ANTS-VII - Berlin, Germany
Duration: Jul 23 2006Jul 28 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4076 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other7th International Symposium on Algorithmic Number Theory, ANTS-VII

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


  • Collision time
  • Discrete logarithm
  • Expander graph
  • Mixing time
  • Pollard Rho algorithm
  • Random walk
  • Spectral analysis

Fingerprint Dive into the research topics of 'Spectral analysis of Pollard Rho collisions'. Together they form a unique fingerprint.

Cite this