How long does it take to catch a wild kangaroo?

Details How long does it take to catch a wild kangaroo? How long does it take to catch a wild kangaroo?

2008-12-03

arxiv.org/abs/0812.0789v2

Conference version: Proc. of the 41st ACM Symposium on Theory of Computing (STOC 2009), pp. 553-559, 2009

Mathematics

Probability

Journal version: 15 pages

Scientific paper

We develop probabilistic tools for upper and lower bounding the expected time until two independent random walks on $\ZZ$ intersect each other. This leads to the first sharp analysis of a non-trivial Birthday attack, proving that Pollard's Kangaroo method solves the discrete logarithm problem $g^x=h$ on a cyclic group in expected time $(2+o(1))\sqrt{b-a}$ for an average $x\in_{uar}[a,b]$. Our methods also resolve a conjecture of Pollard's, by showing that the same bound holds when step sizes are generalized from powers of 2 to powers of any fixed $n$.

Affiliated with

Also associated with

No associations

Rating

How long does it take to catch a wild kangaroo? 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 How long does it take to catch a wild kangaroo?, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and How long does it take to catch a wild kangaroo? will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-135068