In
computational number theory
In mathematics and computer science, computational number theory, also known as algorithmic number theory, is the study of
computational methods for investigating and solving problems in number theory and arithmetic geometry, including algorithm ...
and
computational algebra, Pollard's kangaroo algorithm (also Pollard's lambda algorithm, see
Naming
Naming is assigning a name to something.
Naming may refer to:
* Naming (parliamentary procedure), a procedure in certain parliamentary bodies
* Naming ceremony, an event at which an infant is named
* Product naming, the discipline of deciding wh ...
below) is an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
for solving the
discrete logarithm
In mathematics, for given real numbers ''a'' and ''b'', the logarithm log''b'' ''a'' is a number ''x'' such that . Analogously, in any group ''G'', powers ''b'k'' can be defined for all integers ''k'', and the discrete logarithm log''b' ...
problem. The algorithm was introduced in 1978 by the number theorist
J. M. Pollard, in the same paper as his better-known
Pollard's rho algorithm
Pollard's rho algorithm is an algorithm for integer factorization. It was invented by John Pollard in 1975. It uses only a small amount of space, and its expected running time is proportional to the square root of the smallest prime factor of the ...
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.
Algorithm
Suppose
is a finite cyclic group of order
which is generated by the element
, and we seek to find the discrete logarithm
of the element
to the base
. In other words, one seeks
such that
. The lambda algorithm allows one to search for
in some interval
. One may search the entire range of possible logarithms by setting
and
.
1. Choose a set
of integers and define a
pseudorandom
A pseudorandom sequence of numbers is one that appears to be statistically random, despite having been produced by a completely deterministic and repeatable process.
Background
The generation of random numbers has many uses, such as for rand ...
map
.
2. Choose an integer
and compute a sequence of group elements
according to:
*
*
3. Compute
:
Observe that:
:
4. Begin computing a second sequence of group elements
according to:
*
*
and a corresponding sequence of integers
according to:
:
.
Observe that:
:
5. Stop computing terms of
and
when either of the following conditions are met:
:A)
for some
. If the sequences
and
"collide" in this manner, then we have:
::
:and so we are done.
:B)
. If this occurs, then the algorithm has failed to find
. Subsequent attempts can be made by changing the choice of
and/or
.
Complexity
Pollard gives the time complexity of the algorithm as
, based on a probabilistic argument which follows from the assumption that
acts pseudorandomly. When the size of the set
to be searched is measured in
bit
The bit is the most basic unit of information in computing and digital communications. The name is a portmanteau of binary digit. The bit represents a logical state with one of two possible values. These values are most commonly represente ...
s, as is normal in
complexity theory, the set has size
, and so the algorithm's complexity is
, which is exponential in the problem size. For this reason, Pollard's lambda algorithm is considered an
exponential time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
algorithm. For an example of a
subexponential time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
discrete logarithm algorithm, see the
index calculus algorithm In computational number theory, the index calculus algorithm is a probabilistic algorithm for computing discrete logarithms.
Dedicated to the discrete logarithm in (\mathbb/q\mathbb)^* where q is a prime, index calculus leads to a family of algorit ...
.
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
Kangaroos are four marsupials from the family Macropodidae (macropods, meaning "large foot"). In common use the term is used to describe the largest species from this family, the red kangaroo, as well as the antilopine kangaroo, eastern gre ...
to trap a ''wild'' kangaroo. Pollard has explained that this analogy was inspired by a "fascinating" article published in the same issue of ''
Scientific American
''Scientific American'', informally abbreviated ''SciAm'' or sometimes ''SA'', is an American popular science magazine. Many famous scientists, including Albert Einstein and Nikola Tesla, have contributed articles to it. In print since 1845, it i ...
'' as an exposition of the
RSA public key cryptosystem
Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...
. The article 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
A treadmill is a device generally used for walking, running, or climbing while staying in the same place. Treadmills were introduced before the development of powered machines to harness the power of animals or humans to do work, often a type o ...
".
The second is "Pollard's lambda algorithm". Much like the name of another of Pollard's discrete logarithm algorithms,
Pollard's rho algorithm
Pollard's rho algorithm is an algorithm for integer factorization. It was invented by John Pollard in 1975. It uses only a small amount of space, and its expected running time is proportional to the square root of the smallest prime factor of the ...
, this name refers to the similarity between a visualisation of the algorithm and the
Greek letter
The Greek alphabet has been used to write the Greek language since the late 9th or early 8th century BCE. It is derived from the earlier Phoenician alphabet, and was the earliest known alphabetic script to have distinct letters for vowels as w ...
lambda
Lambda (}, ''lám(b)da'') is the 11th letter of the Greek alphabet, representing the voiced alveolar lateral approximant . In the system of Greek numerals, lambda has a value of 30. Lambda is derived from the Phoenician Lamed . Lambda gave rise ...
(
). The shorter stroke of the letter lambda corresponds to the sequence
, since it starts from the position b to the right of x. Accordingly, the longer stroke corresponds to the sequence
, 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",
as this avoids confusion with some parallel versions of his rho algorithm, which have also been called "lambda algorithms".
See also
*
Rainbow table
References
{{Number-theoretic algorithms
Number theoretic algorithms
Computer algebra
Logarithms