Pollard's kangaroo algorithm: Difference between revisions

Revision as of 09:01, 21 October 2010

Latest revision as of 09:28, 22 April 2025

(85 intermediate revisions by 54 users not shown)

Line 1:

{{Short description|Algorithm in computational number theory}}

In [[computational number theory]] and [[computational algebra]], '''Pollard's kangaroo algorithm''' (aka '''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 accomplished number theorist [[John Pollard (mathematician)|J. M. Pollard]], in the same paper <ref>J. Pollard, ''Monte Carlo methods for index computation mod p'', Mathematics of Computation, Volume 32, 1978</ref> as his better-known [[Pollard's rho algorithm for logarithms|rho algorithm]] for solving the same problem. 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.

{{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''' (akaalso '''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 accomplished number theorist [[John M. Pollard (mathematician)|J.John M. Pollard]], in the same paper <ref>J. Pollard, ''Monte Carlo methods for index computation mod p'', Mathematics of Computation, Volume 32, 1978</ref> 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]].

==The algorithmAlgorithm==

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, weone seekseeks <math>x \in Z_n</math> such that <math>\alpha^x = \beta</math>. The lambda algorithm allows usone to search for <math>x</math> in some subsetinterval <math>\{[a,\ldots,b\}]\subset Z_n</math>. WeOne may search the entire range of possible logarithms by setting <math>a=0</math> and <math>b=n-1</math>, although in this case Pollard's rho algorithm is more efficient. We proceed as follows:

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

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, we seek <math>x \in Z_n</math> such that <math>\alpha^x = \beta</math>. The lambda algorithm allows us to search for <math>x</math> in some subset <math>\{a,\ldots,b\}\subset Z_n</math>. We may search the entire range of possible logarithms by setting <math>a=0</math> and <math>b=n-1</math>, although in this case Pollard's rho algorithm is more efficient. We proceed as follows:

1. Choose a set <math>S</math> of integers 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)}\mboxtext{ 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)}\mboxtext{ 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>.

Line 24 ⟶ 26:

: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} \pmod{n} \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]].

Pollard gives the time complexity of the algorithm as <math>{\scriptstyle O(\sqrt{b-a})}</math>, based on a probabilistic argument which follows from the assumption that ''f'' acts pseudorandomly. Note that when the size of the set {''a'',&nbsp;…,&nbsp;''b''} to be searched is measured in [[Binary digit|bits]], as is normal in [[Computational complexity theory|complexity theory]], the set has size log(''b''&thinsp;&minus;&thinsp;''a''), and so the algorithm's complexity is <math>{\scriptstyle O(\sqrt{b-a}) = O(e^{\frac{1}{2}\log(b-a)})}</math>, which is exponential in the problem size{{Citation needed|date=September 2009}}. For this reason, Pollard's lambda algorithm is considered an [[exponential time]] algorithm. 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>J. M. Pollard, ''Kangaroos, Monopoly and Discrete Logarithms'', Journal of Cryptology, Volume 13, pp 437-447, 2000<name="Pollard_2000_1"/ref> 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>T. J. Dawson, ''Kangaroos'', Scientific American, August 1977, pp. 78-89<name="Dawson_1977"/ref> 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>http: name="Jmptidcott2"//sites.google.com/site/jmptidcott2/</ref>, 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=

<references/>

<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]]

[[nl:Pollards lambda-algoritme]]