Near Optimal Bounds for Collision in Pollard Rho for Discrete Log

Details Near Optimal Bounds for Collision in Pollard Rho for Discrete Log Near Optimal Bounds for Collision in Pollard Rho for Discrete Log

2006-11-19

arxiv.org/abs/math/0611586v3

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), pp. 215-223, 2007.

Mathematics

Number Theory

Scientific paper

We analyze a fairly standard idealization of Pollard's Rho algorithm for finding the discrete logarithm in a cyclic group G. It is found that, with high probability, a collision occurs in $O(\sqrt{|G|\log |G| \log \log |G|})$ steps, not far from the widely conjectured value of $\Theta(\sqrt{|G|})$. This improves upon a recent result of Miller--Venkatesan which showed an upper bound of $O(\sqrt{|G|}\log^3 |G|)$. Our proof is based on analyzing an appropriate nonreversible, non-lazy random walk on a discrete cycle of (odd) length |G|, and showing that the mixing time of the corresponding walk is $O(\log |G| \log \log |G|)$.

Affiliated with

Also associated with

No associations

Rating

Near Optimal Bounds for Collision in Pollard Rho for Discrete Log 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 Near Optimal Bounds for Collision in Pollard Rho for Discrete Log, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Near Optimal Bounds for Collision in Pollard Rho for Discrete Log will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-120700