Non-degeneracy of Pollard rho collisions

Stephen D. Miller, Ramarathnam Venkatesan

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

The Pollard ρ algorithm is a widely used algorithm for solving discrete logarithms on general cyclic groups, including elliptic curves. Recently the first nontrivial runtime estimates were provided for it, culminating in a sharp O( √n) bound for the collision time on a cyclic group of order n [4, 5]. In this paper, we show that for n satisfying a mild arithmetic condition, the collisions guaranteed by these results are nondegenerate with high probability: that is, the Pollard ρ algorithm successfully finds the discrete logarithm.

Original languageEnglish (US)
Pages (from-to)1-10
Number of pages10
JournalInternational Mathematics Research Notices
Volume2009
Issue number1
DOIs
StatePublished - Dec 1 2009

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Non-degeneracy of Pollard rho collisions'. Together they form a unique fingerprint.

Cite this