Spectral Analysis of Pollard Rho Collisions

Details Spectral Analysis of Pollard Rho Collisions Spectral Analysis of Pollard Rho Collisions

2006-03-31

arxiv.org/abs/math/0603727v2

Mathematics

Number Theory

To appear in Proceedings of ANTS VII

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Spectral Analysis of Pollard Rho Collisions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Spectral Analysis of Pollard Rho Collisions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spectral Analysis of Pollard Rho Collisions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-332535