Pollard's Kangaroo Method

Pollard's Kangaroo (Lambda) Method is used to solve the Discrete Logarithm problem: given the generator g of a cyclic group G and an element h∈ G solve for exponent x such that gx=h. In cryptography x is a secret message and h is the encrypted message.

The basic principle is the same as for the Kruskal Count card trick. Suppose it is known that x∈ [a,b] for some interval. Pick a value y∈ [a,b] for the tame kangaroo to start from. Set Y0=gy, look up a jump size δ0 determined by Y0 (given by a hash function), and set Y1=Y0*gδo=gy+δo. Repeat this procedure from Y1. After some moderate number of steps a "trap" is placed, at state T=gt=gy+∑ δi. Next, consider the "wild kangaroo" starting from X0=h=gx, look up a jump size Δ0 and set X1=X0*gΔo=gx+Δo. Repeat until Xk=T, in which case gx+∑ Δi = T = gt, and so x ≡ t - ∑ Δi   mod ord(g).

The following gives an interactive illustration of the method.

Solve gx = h mod n when x∈[0,c]:      n:      g:      c:
 Slow Fast

 Trap Dist. Points Tame Trail

Description of Methods:
• Trap: Pollard's original method. Tame kangaroo starts at gc, takes some number of jumps, places a trap. Wild kangaroo then starts jumping.
• Dist. Points: Distinguished points method. Wild and tame kangaroos take one step each. Repeat until one kangaroo hits a spot visited by the other.
• Tame Trail: Clearer demo of Dist Points when |G| >> c. Tame kangaroo jumps until reaches "end" of group. Then wild kangaroo starts jumping.
We use the common choice of Δ = 2k where k∈uar [0,d] such that Δ ≈ 0.5√c.

Created by Ravi Montenegro.