Pollard Kangaroo Algorithm

Purpose: Solve a discrete logarithm $g^x=h$ when $x$ is known to lie in a bounded interval $[a,b]$, in $O(\sqrt{b-a})$ time and $O(1)$ space. Also called the lambda method.

The Metaphor

Two kangaroos hop through the group, taking pseudo-random jump sizes determined only by their current position:

• the tame kangaroo starts at a known exponent $b$ (the top of the interval) and hops forward, laying a trap at its final position;
• the wild kangaroo starts at the unknown $h=g^x$ and hops with the same rule.

Because the jump function depends only on the group element, once the wild kangaroo lands on any point the tame one visited, their paths merge — the “λ” shape that names the method. Detecting the collision recovers $x$.

Algorithm

1. Choose a jump set $\{s_1,\dots ,s_k\}$ (powers of 2 work well) with mean $m\approx \sqrt{b-a}/2$, and a hash $f(y)\to$ jump index.
2. Tame walk: start at $y=g^b$, $d=0$. Repeat $N\approx \sqrt{b-a}$ times: $d+=s_{f(y)}$, $y\ast =g^{s_{f(y)}}$. Record the trap $(y_T,d_T)$.
3. Wild walk: start at $y=h$, $d=0$. Hop with the same rule. If $y=y_T$, then
   $x+d=b+d_T⟹x=b+d_T-d.$
4. If $d$ exceeds $b-a+d_T$ without a collision, restart with a different jump set.

Complexity

• Time: $O(\sqrt{b-a})$ group operations
• Space: $O(1)$ — this is the point. Baby-step giant-step is also $O(\sqrt{n})$ time but needs $O(\sqrt{n})$ memory.

Kangaroo vs Rho vs BSGS

Method	Time	Space	Best for
Baby-step giant-step	$O(\sqrt{n})$	$O(\sqrt{n})$	small $n$, when memory is free
Pollard’s rho for DLP	$O(\sqrt{n})$	$O(1)$	$x$ anywhere in the group
Kangaroo (lambda)	$O(\sqrt{b-a})$	$O(1)$	$x$ in a known interval

When the interval is much smaller than the group, kangaroo is the clear winner — it pays for the interval width, not the group size.

Why It Works

Both walks are deterministic functions of the current group element, so once two walks coincide at any point they coincide forever. The tame walk covers about $\sqrt{b-a}$ points ahead of $b$; the wild walk starts at most $b-a$ behind and takes steps of mean size $\sqrt{b-a}/2$, so it lands inside the tame walk’s footprint with constant probability by the birthday argument. Expected total hops is $\Theta (\sqrt{b-a})$.

Variants / Use Cases

• Parallel / distinguished points (van Oorschot-Wiener) — run many kangaroos, record only points whose hash has $k$ trailing zeros; gives near-linear speedup across machines and is how large ECDLP records are set
• Pollard’s rho — the same random-walk idea applied to factorisation
• Pohlig-Hellman — use first if the group order is smooth; kangaroo then handles each large prime factor
• Discrete Logarithm — the topic page
• Bitcoin puzzle challenges — the best known public use of large-scale kangaroo searches