Pollard's rho algorithm for discrete logarithms in Python
Walks x = g^a h^b pseudorandomly until Floyd's method finds x_i = x_2i, then solves a linear congruence for log_g h. Heuristic O(n^(1/2)) group operations with O(1) memory.
- File
pollard_rho_discrete_logarithm.py, 59 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-rho-discrete-logarithm/. The authors are listed in prov/8WE1PE.jsonl.
import random
from math import gcd, isqrt
def _step(x: int, a: int, b: int, g: int, h: int, n: int, p: int, key: int) -> tuple[int, int, int]:
"""One step of Pollard's walk; the invariant x = g^a h^b is kept."""
s = x * key % p % 3
if s == 1: # @line L17
return x * h % p, a, (b + 1) % n
if s == 0: # @line L18
return x * x % p, 2 * a % n, 2 * b % n
return x * g % p, (a + 1) % n, b # @line L19
def pollard_rho_log(g: int, h: int, n: int, p: int, seed: int = 0) -> int | None:
"""Pollard's rho method for discrete logarithms modulo a prime p.
Return the x in [0, n) with g^x = h (mod p), or None if h is not a power
of g. The group is the cyclic subgroup <g> of (Z/pZ)^*.
Precondition: p is prime, gcd(g, p) = 1 and n = ord(g) exactly.
Raises ValueError if p < 2 or n < 1.
Cost: heuristically about 3 * 1.03 * (pi n / 2)^(1/2) multiplications
modulo p per attempt (Floyd's cycle finding), O(1) stored residues; the
first attempt is Pollard's walk from x0 = 1 and later attempts use a
random start and a random partition. The number of attempts is small in
expectation but not bounded in the worst case.
"""
if p < 2 or n < 1:
raise ValueError("need p >= 2 and n >= 1")
g %= p
h %= p
if pow(h, n, p) != 1: # @line L1
return None
if h == 1: # @line L2
return 0
rng = random.Random(seed)
a0, b0, key = 0, 0, 1 # @line L3
while True: # @line L4
x = pow(g, a0, p) * pow(h, b0, p) % p # @line L5
a, b = a0, b0
big_x, big_a, big_b = x, a, b # @line L6
while True: # @line L7
x, a, b = _step(x, a, b, g, h, n, p, key) # @line L8
big_x, big_a, big_b = _step(big_x, big_a, big_b, g, h, n, p, key) # @line L9
big_x, big_a, big_b = _step(big_x, big_a, big_b, g, h, n, p, key)
if x == big_x: # @line L10
break
s = (b - big_b) % n # @line L11
d = gcd(s, n)
if s != 0 and d <= isqrt(n) + 1: # @line L12
m = n // d
y = (big_a - a) // d * pow(s // d, -1, m) % m # @line L13
for k in range(d): # @line L14
if pow(g, y + k * m, p) == h: # @line L15
return y + k * m
a0, b0, key = rng.randrange(n), rng.randrange(n), rng.randrange(1, p) # @line L16
test_pollard_rho_discrete_logarithm.py 150 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/pollard-rho-discrete-logarithm/. The authors are listed in prov/8WE1PE.jsonl.
import random
import pytest
from pollard_rho_discrete_logarithm import pollard_rho_log
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 check(g: int, h: int, p: int, seed: int = 0) -> None:
table = power_table(g, p)
n = len(table)
x = pollard_rho_log(g, h, n, p, seed)
if h % p in table:
assert x == table[h % p]
else:
assert x is None
def test_hac_example_3_61() -> None:
# Subgroup of order 191 in (Z/383Z)^*, collision x_14 = x_28 = 144.
assert pollard_rho_log(2, 228, 191, 383) == 110
def test_worked_example_no_solution() -> None:
# 5 is a generator mod 23, so 2 (order 11) does not reach it.
assert pollard_rho_log(2, 5, 11, 23) is None
assert pollard_rho_log(5, 14, 22, 23) == 21
def test_trivial_targets() -> None:
rng = random.Random(1)
for _ in range(60):
p = random_prime(rng, 3, 100000)
g = rng.randrange(2, p)
n = len(power_table(g, p))
assert pollard_rho_log(g, 1, n, p) == 0
assert pollard_rho_log(g, g, n, p) == (1 if n > 1 else 0)
def test_tiny_groups_exhaustive() -> None:
for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]:
for g in range(1, p):
for h in range(1, p):
check(g, h, p)
def test_random_small_groups() -> None:
rng = random.Random(2024)
for _ in range(300):
p = random_prime(rng, 3, 3000)
g = rng.randrange(1, p)
h = rng.randrange(1, p) if rng.random() < 0.5 else pow(g, rng.randrange(p), p)
check(g, h, p, rng.randrange(1000))
def test_random_large_groups() -> None:
rng = random.Random(77)
for _ in range(60):
p = random_prime(rng, 10000, 100000)
g = rng.randrange(2, p)
table = power_table(g, p)
n = len(table)
for _ in range(3):
x = rng.randrange(n)
h = pow(g, x, p)
assert pollard_rho_log(g, h, n, p, rng.randrange(1000)) == table[h]
outside = rng.randrange(1, p)
expected = table.get(outside)
assert pollard_rho_log(g, outside, n, p) == expected
def test_prime_order_subgroups() -> None:
rng = random.Random(5)
found = 0
while found < 40:
q = random_prime(rng, 3, 300)
k = rng.randrange(2, 300)
p = k * q + 1
if not is_prime(p):
continue
g = 1
while g == 1:
g = pow(rng.randrange(2, p), k, p)
assert len(power_table(g, p)) == q
for _ in range(5):
x = rng.randrange(q)
assert pollard_rho_log(g, pow(g, x, p), q, p, rng.randrange(100)) == x
non_member = next(y for y in range(2, p) if pow(y, q, p) != 1)
assert pollard_rho_log(g, non_member, q, p) is None
found += 1
def test_composite_order_subgroups() -> None:
rng = random.Random(9)
for _ in range(80):
p = random_prime(rng, 100, 50000)
r = p - 1
divisors = [d for d in range(4, r + 1) if r % d == 0 and not is_prime(d)]
if not divisors:
continue
n = rng.choice(divisors)
g = 1
while len(power_table(g, p)) != n:
g = pow(rng.randrange(2, p), r // n, p)
for _ in range(4):
x = rng.randrange(n)
assert pollard_rho_log(g, pow(g, x, p), n, p, rng.randrange(100)) == x
check(g, rng.randrange(1, p), p)
def test_seed_independence_of_answer() -> None:
for seed in range(20):
assert pollard_rho_log(2, 228, 191, 383, seed) == 110
def test_bad_input() -> None:
with pytest.raises(ValueError):
pollard_rho_log(2, 3, 0, 5)
with pytest.raises(ValueError):
pollard_rho_log(2, 3, 1, 1)
What the next level needs
- the tests did not run in this build
Read the full page about Pollard's rho algorithm for discrete logarithms