Spectral analysis of Pollard Rho collisions

Stephen D. Miller, Ramarathnam Venkatesan

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

10 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationAlgorithmic Number Theory - 7th International Symposium, ANTS-VII, Proceedings
PublisherSpringer Verlag
Pages573-581
Number of pages9
ISBN (Print)3540360751, 9783540360759
DOIs
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

Other

Other7th International Symposium on Algorithmic Number Theory, ANTS-VII
CountryGermany
CityBerlin
Period7/23/067/28/06

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • 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

    Miller, S. D., & Venkatesan, R. (2006). Spectral analysis of Pollard Rho collisions. In Algorithmic Number Theory - 7th International Symposium, ANTS-VII, Proceedings (pp. 573-581). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4076 LNCS). Springer Verlag. https://doi.org/10.1007/11792086_40