View source for Pollard's kangaroo algorithm

{{Short description|Algorithm in computational number theory}}
{{Use dmy dates|date=August 2023|cs1-dates=y}}
{{Use list-defined references|date=August 2023}}
In [[computational number theory]] and [[computer algebra|computational algebra]], '''Pollard's kangaroo algorithm''' (also '''Pollard's lambda algorithm''', see [[#Naming|Naming]] below) is an [[algorithm]] for solving the [[discrete logarithm]] problem.  The algorithm was introduced in 1978 by the number theorist [[John M. Pollard (mathematician)|John M. Pollard]], in the same paper as his better-known [[Pollard's rho algorithm for logarithms|Pollard's rho algorithm]] for solving the same problem.<ref name="Pollard_1978"/><ref name="Oorschot-Wiener_1999"/> Although Pollard described the application of his algorithm to the discrete logarithm problem in the multiplicative group of units modulo a prime ''p'', it is in fact a generic discrete logarithm algorithm—it will work in any [[finite cyclic group]].

==Algorithm==
Suppose <math>G</math> is a finite cyclic group of order <math>n</math> which is generated by the element <math>\alpha</math>, and we seek to find the discrete logarithm <math>x</math> of the element <math>\beta</math> to the base <math>\alpha</math>. In other words, one seeks <math>x \in Z_n</math> such that <math>\alpha^x = \beta</math>. The lambda algorithm allows one to search for <math>x</math> in some interval <math>[a,\ldots,b]\subset Z_n</math>. One may search the entire range of possible logarithms by setting <math>a=0</math> and <math>b=n-1</math>. 

1. Choose a set <math>S</math> of positive integers of mean roughly <math>\sqrt{b-a}</math> and define a [[pseudorandom]] map <math>f: G \rightarrow S</math>. 

2. Choose an integer <math>N</math> and compute a sequence of group elements <math>\{x_0,x_1,\ldots,x_N\}</math> according to:
* <math>x_0 = \alpha^b\,</math>
* <math>x_{i+1} = x_i\alpha^{f(x_i)}\text{ for }i=0,1,\ldots,N-1</math>
3. Compute
:<math>d = \sum_{i=0}^{N-1}f(x_i).</math>
Observe that:
:<math>x_N = x_0\alpha^d = \alpha^{b+d}\, .</math>
4. Begin computing a second sequence of group elements <math>\{y_0,y_1,\ldots\}</math> according to:
* <math>y_0 = \beta\,</math>
* <math>y_{i+1} = y_i\alpha^{f(y_i)}\text{ for }i=0,1,\ldots,N-1</math>
and a corresponding sequence of integers <math>\{d_0,d_1,\ldots\}</math> according to:
:<math>d_n = \sum_{i=0}^{n-1}f(y_i)</math>.
Observe that:
:<math>y_i = y_0\alpha^{d_i} = \beta\alpha^{d_i}\mbox{ for }i=0,1,\ldots,N-1</math>
5. Stop computing terms of <math>\{y_i\}</math> and <math>\{d_i\}</math> when either of the following conditions are met:

:A) <math>y_j = x_N</math> for some <math>j</math>.  If the sequences <math>\{x_i\}</math> and <math>\{y_j\}</math> "collide" in this manner, then we have:
::<math>x_N = y_j \Rightarrow \alpha^{b+d} = \beta\alpha^{d_j} \Rightarrow \beta = \alpha^{b+d-d_j} \Rightarrow 
x \equiv b+d-d_j \pmod{n}</math>
:and so we are done.

:B) <math>d_i > b-a+d</math>. If this occurs, then the algorithm has failed to find <math>x</math>. Subsequent attempts can be made by changing the choice of <math>S</math> and/or <math>f</math>.

==Complexity==
Pollard gives the time complexity of the algorithm as <math>O(\sqrt{b-a})</math>, using a probabilistic argument based on the assumption that <math>f</math> acts pseudorandomly. Since <math>a, b</math> can be represented using <math>O(\log b)</math> bits, this is exponential in the problem size (though still a significant improvement over the trivial brute-force algorithm that takes time <math>O(b-a)</math>). For an example of a [[subexponential time]] discrete logarithm algorithm, see the [[index calculus algorithm]].

==Naming==
The algorithm is well known by two names.

The first is "Pollard's kangaroo algorithm".  This name is a reference to an analogy used in the paper presenting the algorithm, where the algorithm is explained in terms of using a ''tame'' [[kangaroo]] to trap a ''wild'' kangaroo.  Pollard has explained<ref name="Pollard_2000_1"/> that this analogy was inspired by a "fascinating" article published in the same issue of ''[[Scientific American]]'' as an exposition of the [[RSA (algorithm)|RSA]] [[public key cryptosystem]]. The article<ref name="Dawson_1977"/> described an experiment in which a kangaroo's "energetic cost of locomotion, measured in terms of oxygen consumption at various speeds, was determined by placing kangaroos on a [[treadmill]]".

The second is "Pollard's lambda algorithm".  Much like the name of another of Pollard's discrete logarithm algorithms, [[Pollard's rho algorithm for logarithms|Pollard's rho algorithm]], this name refers to the similarity between a visualisation of the algorithm and the [[Greek letter]] [[lambda]] (<math>\lambda</math>).  The shorter stroke of the letter lambda corresponds to the sequence <math>\{x_i\}</math>, since it starts from the position b to the right of x.  Accordingly, the longer stroke corresponds to the sequence <math>\{y_i\}</math>, which "collides with" the first sequence (just like the strokes of a lambda intersect) and then follows it subsequently.

Pollard has expressed a preference for the name "kangaroo algorithm",<ref name="Jmptidcott2"/> as this avoids confusion with some parallel versions of his rho algorithm, which have also been called "lambda algorithms".

==See also==
* [[Dynkin's card trick]]
* [[Kruskal count]]<ref name="Pollard_2000_2"/>
* [[Rainbow table]]

==References==
{{reflist|refs=
<ref name="Pollard_1978">{{cite journal |title=Monte Carlo Methods for Index Computation (mod ''p'') |author-first=John M. |author-last=Pollard |author-link=John M. Pollard (mathematician) |location=Mathematics Department, Plessey Telecommunications Research, Taplow Court, Maidenhead, Berkshire, UK |journal=[[Mathematics of Computation]] |issn=0025-5718 |volume=32 |number=143 |publisher=[[American Mathematical Society]] |date=July 1978 |orig-date=1977-05-01, 1977-11-18 |pages=918–924 |url=https://www.ams.org/journals/mcom/1978-32-143/S0025-5718-1978-0491431-9/S0025-5718-1978-0491431-9.pdf |access-date=2023-08-19 |url-status=live |archive-url=https://web.archive.org/web/20130503020626/http://www.ams.org/journals/mcom/1978-32-143/S0025-5718-1978-0491431-9/S0025-5718-1978-0491431-9.pdf |archive-date=2013-05-03}} (7 pages)</ref>
<ref name="Dawson_1977">{{cite magazine |title=Kangaroos |author-first=Terence J. |author-last=Dawson |magazine=[[Scientific American]] |issn=0036-8733 |publisher=[[Scientific American, Inc.]] |date=1977-08-01 |volume=237 |number=2 |jstor=24954004 |pages=78–89}}</ref>
<ref name="Jmptidcott2">{{cite web |title=Jmptidcott2 |author-first=John M. |author-last=Pollard |author-link=John M. Pollard (mathematician) |date= |url=http://sites.google.com/site/jmptidcott2/ |access-date=2023-08-19 |url-status=live |archive-url=https://web.archive.org/web/20230818233808/https://sites.google.com/site/jmptidcott2/ |archive-date=2023-08-18}}</ref>
<ref name="Pollard_2000_1">{{cite journal |title=Kangaroos, Monopoly and Discrete Logarithms |author-first=John M. |author-last=Pollard |author-link=John M. Pollard (mathematician) |location=Tidmarsh Cottage, Manor Farm Lane, Tidmarsh, Reading, UK |date=2000-08-10 |orig-date=1998-01-23, 1999-09-27 |journal=[[Journal of Cryptology]] |issn=0933-2790 |publisher=[[International Association for Cryptologic Research]] |volume=13 |number=4 |doi=10.1007/s001450010010 |pages=437–447 |url=https://link.springer.com/content/pdf/10.1007/s001450010010.pdf |access-date=2023-08-19 |url-status=live |archive-url=https://web.archive.org/web/20230818234706/https://link.springer.com/content/pdf/10.1007/s001450010010.pdf |archive-date=2023-08-18}} (11 pages)</ref>
<ref name="Pollard_2000_2">{{cite journal |title=Kruskal's Card Trick |author-first=John M. |author-last=Pollard |author-link=John M. Pollard (mathematician) |location=Tidmarsh Cottage, Manor Farm Lane, Tidmarsh, Reading, UK |journal=[[The Mathematical Gazette]] |issn=0025-5572 |volume=84 |number=500 |date=July 2000 |publisher=[[The Mathematical Association]] |jstor=3621657 |id=84.29 |pages=265–267 |doi=10.2307/3621657 |url=https://web.northeastern.edu/seigen/11Magic/KruskalsCount/Pollard.pdf |access-date=2023-08-19 |url-status=live |archive-url=https://web.archive.org/web/20230818222322/https://web.northeastern.edu/seigen/11Magic/KruskalsCount/Pollard.pdf |archive-date=2023-08-18}} (1+3 pages)</ref>
<ref name="Oorschot-Wiener_1999">{{cite journal |title=Parallel collision search with cryptanalytic applications |author-first1=Paul C. |author-last1=van Oorschot |author-link1=Paul C. van Oorschot |author-first2=Michael J. |author-last2=Wiener |journal=[[Journal of Cryptology]] |issn=0933-2790 |publisher=[[International Association for Cryptologic Research]] |volume=12 |number=1 |date=1999 |doi= 10.1007/PL00003816|pages=1–28 |url=https://repository.library.carleton.ca/downloads/2514nk502}}</ref>
}}

==Further reading==
* {{cite conference |title=How Long Does it Take to Catch a Wild Kangaroo? |author-first1=Ravi |author-last1=Montenegro |author-link1=:d:Q102271025 |author-first2=Prasad V. |author-last2=Tetali |author-link2=Prasad V. Tetali |date=2010-11-07 |orig-date=2009-05-31 |conference=Proceedings of the forty-first annual ACM symposium on Theory of computing (STOC 2009) |doi=10.1145/1536414.1536490 |s2cid=12797847 |arxiv=0812.0789 |pages=553–560 |url=https://faculty.uml.edu/rmontenegro/research/kangaroo-journal.pdf |access-date=2023-08-20 |url-status=live |archive-url=https://web.archive.org/web/20230820105311/https://faculty.uml.edu/rmontenegro/research/kangaroo-journal.pdf |archive-date=2023-08-20}}

{{Number-theoretic algorithms}}
[[Category:Number theoretic algorithms]]
[[Category:Computer algebra]]
[[Category:Logarithms]]