Non-Degeneracy of Pollard Rho Collisions

DOI10.1093/imrn/rnn114zbMath1175.11073arXiv0808.0469OpenAlexW1979695301MaRDI QIDQ5503790

Stephen D. Miller, Ramarathnam Venkatesan

Publication date: 20 January 2009

Published in: International Mathematics Research Notices (Search for Journal in Brave)

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

zbMATH Keywords

complexityrandom walkcollisiondiscrete logarithmdegenerate pairPollard rho algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Data encryption (aspects in computer science) (68P25) Number-theoretic algorithms; complexity (11Y16) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Applications to coding theory and cryptography of arithmetic geometry (14G50) Randomized algorithms (68W20)

Related Items (2)

Rigorous analysis of a randomised number field sieve ⋮ A birthday paradox for Markov chains with an optimal bound for collision in the Pollard rho algorithm for discrete logarithm

This page was built for publication: Non-Degeneracy of Pollard Rho Collisions