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

- Published in 2008
- Added on

In the collections

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$.

## Links

## Other information

- key
- Howlongdoesittaketocatchawildkangaroo
- type
- article
- date_added
- 2018-05-12
- date_published
- 2008-11-28

### BibTeX entry

@article{Howlongdoesittaketocatchawildkangaroo, key = {Howlongdoesittaketocatchawildkangaroo}, type = {article}, title = {How long does it take to catch a wild kangaroo?}, author = {Ravi Montenegro and Prasad Tetali}, abstract = {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{\$}.}, comment = {}, date_added = {2018-05-12}, date_published = {2008-11-28}, urls = {http://arxiv.org/abs/0812.0789v2,http://arxiv.org/pdf/0812.0789v2}, collections = {Animals,Easily explained,Probability and statistics}, url = {http://arxiv.org/abs/0812.0789v2 http://arxiv.org/pdf/0812.0789v2}, year = 2008, urldate = {2018-05-12}, archivePrefix = {arXiv}, eprint = {0812.0789}, primaryClass = {math.PR} }