Spectral Analysis of Pollard Rho Collisions

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We show that the classical Pollard rho algorithm for discrete logarithms produces a collision in expected time O(sqrt(n)(log n)^3). This is the first nontrivial rigorous estimate for the collision probability for the unaltered Pollard rho graph, and is close to the conjectured optimal bound of O(sqrt(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 rho 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.
To appear in Proceedings of ANTS VII

Keywords

Number Theory, Cryptography and Security, Discrete Mathematics, Combinatorics

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/110380

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0603727
 http://arxiv.org/abs/math/0603727

Collections

arXiv