Pollard's lambda algorithm


Pollard's lambda algorithm

In mathematics, specifically computational number theory and computational algebra, Pollard's lambda algorithm (aka Pollard's kangaroo algorithm, see Naming below) is an algorithm for solving the discrete logarithm. The algorithm was introduced in 1978 by the accomplished number theorist J. M. Pollard, in the same paper [J. Pollard, "Monte Carlo methods for index computation mod p", Mathematics of Computation, Volume 32, 1978] as his better-known 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.

The algorithm

Suppose G is a finite cyclic group of order n which is generated by the element alpha, and we seek to find the discrete logarithm x of the element eta to the base alpha. In other words, we seek x in Z_n such that alpha^x = eta. The lambda algorithm allows us to search for x in some subset {a,ldots,b} of Z_n. We may search the entire range of possible logarithms by setting a=0 and b=p-1, although in this case Pollard's rho algorithm is more efficient. We proceed as follows:

1. Choose a set S of integers and define a pseudorandom map f: G ightarrow S.

2. Choose an integer N and compute a sequence of group elements {x_0,x_1,ldots,x_N} according to:
* x_0 = alpha^b
* x_{i+1} = x_ialpha^{f(x_i)} for i=0,1,ldots,N-13. Compute:d = sum_{i=0}^{N-1}f(x_i).Observe that::x_N = x_0alpha^d = alpha^{b+d}.4. Begin computing a second sequence of group elements {y_0,y_1,ldots} according to:
* y_0 = eta
* y_{i+1} = y_ialpha^{f(y_i)} for i=0,1,ldots,N-1and a corresponding sequence of integers {d_0,d_1,ldots} according to::d_n = sum_{i=0}^{n-1}f(y_i).Observe that::y_i = y_0alpha^{d_i} = etaalpha^{d_i} for i=0,1,ldots,N-15. Stop computing terms of {y_i} and {d_i} when either of the following conditions are met:

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

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

Complexity

Pollard gives the time complexity of the algorithm as {scriptstyle O(sqrt{b-a})}, based on a probabilistic argument which follows from the assumption that "f" acts pseudorandomly. Note that when the size of the set {"a", …, "b"} to be searched is measured in bits, as is normal in complexity theory, the set has size log("b" − "a"), and so the algorithm's complexity is {scriptstyle O(sqrt{b-a}) = O(e^{frac{1}{2}log(b-a)})}, which is exponential in the problem size. 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 lambda algorithm". Much like the name of another of Pollard's discrete logarithm algorithms, Pollard's rho algorithm, this name refers to the similarity between a visualisation of the algorithm and the Greek letter lambda (lambda). The longer stroke of the letter lambda corresponds to the sequence {x_i}. The shorter stroke corresponds to the sequence {y_i}, which "collides with" the first sequence (just like the strokes of a lambda intersect) and then follows it subsequently.

The second 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 [J. M. Pollard, "Kangaroos, Monopoly and Discrete Logarithms", Journal of Cryptology, Volume 13, pp 437-447, 2000] that this analogy was inspired by a "fascinating " article published in the same issue of Scientific American as an exposition of the RSA public key cryptosystem. The article [T. J. Dawson, "Kangaroos", Scientific American, August 1977, pp. 78-89] 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".

Pollard has expressed a preference for the name "kangaroo algorithm"Fact|date=August 2007, as this avoids confusion with some parallel versions of his rho algorithm, which have also been called "lambda algorithms".

ee also

* Rainbow table

References


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Pollard — may refer to:*Pollard (surname) *Pollard, Alabama, a town in the United States *Jonathan Pollard, a spy *Pollard, a tree or animal which has been polled (had its branches, horns or antlers removed): **Pollard, a tree affected by pollarding, a… …   Wikipedia

  • Discrete logarithm — In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga(b) is a solution of the equation ax = b over the… …   Wikipedia

  • List of mathematics articles (P) — NOTOC P P = NP problem P adic analysis P adic number P adic order P compact group P group P² irreducible P Laplacian P matrix P rep P value P vector P y method Pacific Journal of Mathematics Package merge algorithm Packed storage matrix Packing… …   Wikipedia

  • Rainbow table — A rainbow table is a lookup table offering a time memory tradeoff used in recovering the plaintext password from a password hash generated by a hash function, often a cryptographic hash function. A common application is to make attacks against… …   Wikipedia

  • Cycle detection — This article is about iterated functions. For another use, see Cycle detection (graph theory). In computer science, cycle detection is the algorithmic problem of finding a cycle in a sequence of iterated function values. For any function ƒ that… …   Wikipedia

  • Ρ-алгоритм Полларда — Эта статья  о факторизации чисел. О методе дискретного логарифмирования см. Ρ метод Полларда дискретного логарифмирования. Числовая последовательность зацикливается, начиная с неко …   Википедия

  • RSA — In cryptography, RSA is an algorithm for public key cryptography. It is the first algorithm known to be suitable for signing as well as encryption, and one of the first great advances in public key cryptography. RSA is widely used in electronic… …   Wikipedia

  • List of Brown University people — The following is a partial list of notable Brown University people, known as Brunonians. It includes alumni, professors, and others associated with Brown University. Notable alumni Note: Class of is used to denote the graduation class of… …   Wikipedia