Pollard's kangaroo algorithm in Python
Solves g^x = h for x in an interval of width w. A tame kangaroo from the middle and a wild one from h make small known jumps until they meet, in about 2 w^(1/2) steps and O(1) memory, heuristically.
- File
pollard_kangaroo.py, 79 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/pollard-kangaroo/. The authors are listed in prov/VXD7T2.jsonl.
import random
from math import isqrt
def _bsgs(g: int, h: int, n: int, p: int) -> int | None:
"""Least x in [0, n) with g^x = h (mod p), or None; O(n^(1/2)) steps."""
m = isqrt(max(n - 1, 0)) + 1
table: dict[int, int] = {}
e = 1 % p
for j in range(m):
if e not in table:
table[e] = j
e = e * g % p
u = pow(g, -m, p)
gamma = h
for i in range(m):
if gamma in table:
x = i * m + table[gamma]
return x if x < n else None
gamma = gamma * u % p
return None
def pollard_kangaroo(g: int, h: int, a: int, b: int, p: int, seed: int = 0, attempts: int = 3) -> int | None:
"""Pollard's kangaroo method with distinguished points, modulo p.
Return some x in [a, b] with g^x = h (mod p), or None if there is none.
The group is the cyclic subgroup <g> of (Z/pZ)^*.
Precondition: p >= 2, gcd(g, p) = 1 and 0 <= a <= b. Raises ValueError
otherwise.
Cost: heuristically about 2 w^(1/2) + 2/theta multiplications modulo p
per attempt, with w = b - a, jumps 2^j of mean about w^(1/2)/2 and a
table of O(theta w^(1/2)) distinguished points. A kangaroo run cannot
prove that no solution exists, so after `attempts` failed runs the
answer is certified by baby-step giant-step on the interval, at a cost
of O(w^(1/2)) steps and memory.
"""
if p < 2 or a < 0 or b < a:
raise ValueError("need p >= 2 and 0 <= a <= b")
g %= p
h %= p
w = b - a # @line L1
target = h * pow(g, -a, p) % p
half = isqrt(w)
k = 1 # @line L2
while (2**k - 1) < k * max(1, half // 2):
k += 1
jumps = [pow(g, 2**j, p) for j in range(k)]
spacing = max(1, half // 8)
budget = 4 * half + 4 * spacing + 16
rng = random.Random(seed)
key = 1
for _ in range(attempts): # @line L3
tame, d_tame = pow(g, w // 2, p), w // 2 # @line L4
wild, d_wild = target, 0
traps: dict[int, tuple[int, int]] = {} # @line L5
for _ in range(budget): # @line L6
for kind in (0, 1): # @line L7
y, d = (tame, d_tame) if kind == 0 else (wild, d_wild)
v = y * key % p
if (v // k) % spacing == 0: # @line L8
other = traps.get(y)
if other is not None and other[0] != kind: # @line L9
t_dist, w_dist = (d, other[1]) if kind == 0 else (other[1], d)
z = t_dist - w_dist # @line L10
if 0 <= z <= w and pow(g, z, p) == target: # @line L11
return a + z
traps[y] = (kind, d) # @line L12
j = v % k # @line L13
if kind == 0:
tame, d_tame = tame * jumps[j] % p, d_tame + 2**j
else:
wild, d_wild = wild * jumps[j] % p, d_wild + 2**j
key = rng.randrange(1, p) if p > 2 else 1 # @line L14
x = _bsgs(g, target, w + 1, p) # @line L15
return None if x is None else a + x
test_pollard_kangaroo.py 165 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/pollard-kangaroo/. The authors are listed in prov/VXD7T2.jsonl.
import random
import pytest
import pollard_kangaroo as module
from pollard_kangaroo import pollard_kangaroo
def is_prime(n: int) -> bool:
if n < 2:
return False
d = 2
while d * d <= n:
if n % d == 0:
return False
d += 1
return True
def power_table(g: int, p: int) -> dict[int, int]:
"""Least exponent of every power of g modulo p, by walking the cycle."""
seen: dict[int, int] = {}
e, x = 1 % p, 0
while e not in seen:
seen[e] = x
e, x = e * g % p, x + 1
return seen
def random_prime(rng: random.Random, lo: int, hi: int) -> int:
while True:
p = rng.randrange(lo, hi)
if is_prime(p):
return p
def solvable(table: dict[int, int], h: int, a: int, b: int) -> bool:
"""Is there y in [a, b] with g^y = h? Uses the period n = len(table)."""
if h not in table:
return False
n, x0 = len(table), table[h]
first = a + (x0 - a) % n
return first <= b
def check(g: int, h: int, a: int, b: int, p: int, table: dict[int, int], seed: int = 0) -> None:
x = pollard_kangaroo(g, h, a, b, p, seed)
if solvable(table, h % p, a, b):
assert x is not None and a <= x <= b and pow(g, x, p) == h % p
else:
assert x is None
def test_galbraith_example_14_5_2() -> None:
# g = 3 of order 131 mod 263, h = 181, 0 <= x < 53: the answer is 12.
assert pollard_kangaroo(3, 181, 0, 52, 263) == 12
def test_shifted_interval_example() -> None:
# 5^21 = 14 mod 23 and 21 lies in [18, 22]; nothing in [0, 10].
assert pollard_kangaroo(5, 14, 18, 22, 23) == 21
assert pollard_kangaroo(5, 14, 0, 10, 23) is None
assert pollard_kangaroo(2, 5, 0, 100, 23) is None
def test_trivial_targets() -> None:
rng = random.Random(3)
for _ in range(50):
p = random_prime(rng, 3, 100000)
g = rng.randrange(2, p)
b = rng.randrange(0, 2000)
table = power_table(g, p)
check(g, 1, 0, b, p, table)
check(g, g, 0, b, p, table)
check(g, 1, 1, b + 1, p, table)
def test_tiny_groups_exhaustive() -> None:
for p in [2, 3, 5, 7, 11, 13, 17, 19, 23]:
for g in range(1, p):
table = power_table(g, p)
for h in range(1, p):
for a in range(0, 6):
for b in range(a, a + 12, 3):
check(g, h, a, b, p, table)
def test_random_intervals() -> None:
rng = random.Random(2024)
for _ in range(250):
p = random_prime(rng, 50, 100000)
g = rng.randrange(2, p)
table = power_table(g, p)
n = len(table)
a = rng.randrange(0, 2 * n)
w = rng.choice([0, 1, 2, rng.randrange(n), rng.randrange(3 * n + 1)])
b = a + w
roll = rng.random()
if roll < 0.5:
h = pow(g, rng.randrange(a, b + 1), p)
elif roll < 0.8:
h = pow(g, rng.randrange(n), p)
else:
h = rng.randrange(1, p)
check(g, h, a, b, p, table, rng.randrange(1000))
def test_prime_order_subgroups() -> None:
rng = random.Random(11)
done = 0
while done < 30:
q = random_prime(rng, 50, 3000)
k = rng.randrange(2, 30)
p = k * q + 1
if not is_prime(p):
continue
g = 1
while g == 1:
g = pow(rng.randrange(2, p), k, p)
table = power_table(g, p)
assert len(table) == q
for _ in range(4):
a = rng.randrange(q)
b = a + rng.randrange(q // 2 + 1)
check(g, pow(g, rng.randrange(a, b + 1), p), a, b, p, table)
check(g, pow(g, rng.randrange(q), p), a, b, p, table)
non_member = next(y for y in range(2, p) if pow(y, q, p) != 1)
assert pollard_kangaroo(g, non_member, 0, q, p) is None
done += 1
def test_kangaroos_usually_succeed_without_fallback(monkeypatch: pytest.MonkeyPatch) -> None:
# Large intervals inside a large prime order subgroup: the walk alone
# should solve almost every instance, so the certificate is rarely used.
calls = []
original = module._bsgs
def spy(g: int, h: int, n: int, p: int) -> int | None:
calls.append(n)
return original(g, h, n, p)
monkeypatch.setattr(module, "_bsgs", spy)
rng = random.Random(5)
p = 99991
g = next(c for c in range(2, p) if all(pow(c, (p - 1) // f, p) != 1 for f in (2, 3, 5, 11, 101)))
n = p - 1
trials = 60
for _ in range(trials):
a = rng.randrange(n // 2)
b = a + rng.randrange(1000, n // 2)
x = rng.randrange(a, b + 1)
assert pollard_kangaroo(g, pow(g, x, p), a, b, p, rng.randrange(100)) is not None
assert len(calls) <= trials // 10
def test_bad_input() -> None:
with pytest.raises(ValueError):
pollard_kangaroo(2, 3, 5, 4, 7)
with pytest.raises(ValueError):
pollard_kangaroo(2, 3, -1, 4, 7)
with pytest.raises(ValueError):
pollard_kangaroo(2, 3, 0, 4, 1)
What the next level needs
- the tests did not run in this build