Pollard's kangaroo algorithm

In computational number theory and computational algebra, Pollard's kangaroo algorithm (also Pollard's lambda algorithm, see Naming below) is an algorithm for solving the discrete logarithm problem. The algorithm was introduced in 1978 by the number theorist John M. Pollard, in the same paper as his better-known Pollard's 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.

Algorithm

Suppose

G

{\displaystyle G}

is a finite cyclic group of order

n

{\displaystyle n}

which is generated by the element

α

{\displaystyle \alpha }

, and we seek to find the discrete logarithm

x

{\displaystyle x}

of the element

β

{\displaystyle \beta }

to the base

α

{\displaystyle \alpha }

. In other words, one seeks

x

∈

Z

n

{\displaystyle x\in \mathbb {Z} _{n}}

such that

α

x

=

β

{\displaystyle \alpha ^{x}=\beta }

. The lambda algorithm allows one to search for

x

{\displaystyle x}

in some interval

[

a

,

…

,

b

]

⊂

Z

n

{\displaystyle [a,\ldots ,b]\subset \mathbb {Z} _{n}}

. One may search the entire range of possible logarithms by setting

a

=

0

{\displaystyle a=0}

and

b

=

n

−

1

{\displaystyle b=n-1}

.

1. Choose a set

S

{\displaystyle S}

of positive integers of mean roughly

b

−

a

{\displaystyle {\sqrt {b-a}}}

and define a pseudorandom map

f

:

G

→

S

{\displaystyle f:G\rightarrow S}

.

2.