Pollard's kangaroo algorithm: Difference between revisions

Revision as of 23:44, 18 August 2023

Latest revision as of 09:28, 22 April 2025

(16 intermediate revisions by 5 users not shown)

Line 1:

{{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==

Line 44 ⟶ 45:

==See also==

* [[Dynkin's card trick]]

* [[Kruskal count]]<ref name="Pollard_2000_2"/>

* [[Rainbow table]]

Line 49 ⟶ 51:

==References==

{{reflist|refs=

<ref name="Pollard_1978">{{cite journal |title=Monte Carlo Methods for Index computationComputation (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]] |volume=32 |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=T.Terence J. |author-last=Dawson |magazine=[[Scientific American]] |issn=0036-8733 |publisher=[[Scientific American, Inc.]] |date=August 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}}