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:||    |
Created by Ravi Montenegro.