We will perform the Pohlig-Hellman algorithm to compute $\log_{a} b$ in $\mathbf{Z}_{p}^*$, where $a = 11$, $b = 2020$, and $p = 15121$ is a prime number.
from algorithms.factorization import totalFactorization
from algorithms.discreteLogarithm import babyStepGiantStep
from algorithms.modular import crt
a = 11
b = 2020
p = 15121
We notice that $p-1$ can be efficiently factorized. This allows the Pohlig-Hellman algorithm to break the problem into multiple smaller problems which can be solved, say, using the giant-step/baby-step algorithm.
n = p - 1
f = totalFactorization(n)
f
{3: 3, 2: 4, 5: 1, 7: 1}
We now perform the main loop of the algorithm. The idea is to compute discrete logarithms with base $(p-1)/q$ for each prime power factor $q^e$ of $p-1$ which give a $q$-ary representation of the sought result modulo $q^e$.
ai = a^-1 % p
v = {}
for q, e in f.items():
print("prime power factor: %d^%d" % (q, e))
nq = n // q
ap = pow(a, nq, p)
print("a^(%d/%d) = %d" % (n, q, ap))
bp, qp = b, 1
c, k, x = 1, 0, 0
for i in range(e):
c = c * pow(ai, k, p) % p
bp = pow(b*c, nq, p)
print("c_%d = c_%d * a^-k_%d = %d" % (i, i-1, i-1, c))
print("b_%d = (b_%d*c_%d)^(%d/%d^%d) = %d" %
(i, i-1, i, n, q, i+1, bp))
print("z = log_%d(%d) mod %d, order = %d" % (ap, bp, p, q))
k = (babyStepGiantStep(ap, bp, p, order = q) % q) * qp
x += k
print("k_%d = z*q^%d = %d" % (i, i, k))
qp *= q
nq //= q
v[qp] = x
v
prime power factor: 3^3 a^(15120/3) = 7292 c_0 = c_-1 * a^-k_-1 = 1 b_0 = (b_-1*c_0)^(15120/3^1) = 7828 z = log_7292(7828) mod 15121, order = 3 k_0 = z*q^0 = 2 c_1 = c_0 * a^-k_0 = 11372 b_1 = (b_0*c_1)^(15120/3^2) = 1 z = log_7292(1) mod 15121, order = 3 k_1 = z*q^1 = 0 c_2 = c_1 * a^-k_1 = 11372 b_2 = (b_1*c_2)^(15120/3^3) = 1 z = log_7292(1) mod 15121, order = 3 k_2 = z*q^2 = 0 prime power factor: 2^4 a^(15120/2) = 15120 c_0 = c_-1 * a^-k_-1 = 1 b_0 = (b_-1*c_0)^(15120/2^1) = 15120 z = log_15120(15120) mod 15121, order = 2 k_0 = z*q^0 = 1 c_1 = c_0 * a^-k_0 = 4124 b_1 = (b_0*c_1)^(15120/2^2) = 1 z = log_15120(1) mod 15121, order = 2 k_1 = z*q^1 = 0 c_2 = c_1 * a^-k_1 = 4124 b_2 = (b_1*c_2)^(15120/2^3) = 15120 z = log_15120(15120) mod 15121, order = 2 k_2 = z*q^2 = 4 c_3 = c_2 * a^-k_2 = 8938 b_3 = (b_2*c_3)^(15120/2^4) = 15120 z = log_15120(15120) mod 15121, order = 2 k_3 = z*q^3 = 8 prime power factor: 5^1 a^(15120/5) = 11389 c_0 = c_-1 * a^-k_-1 = 1 b_0 = (b_-1*c_0)^(15120/5^1) = 1383 z = log_11389(1383) mod 15121, order = 5 k_0 = z*q^0 = 2 prime power factor: 7^1 a^(15120/7) = 10187 c_0 = c_-1 * a^-k_-1 = 1 b_0 = (b_-1*c_0)^(15120/7^1) = 7205 z = log_10187(7205) mod 15121, order = 7 k_0 = z*q^0 = 6
{27: 2, 16: 13, 5: 2, 7: 6}
This gives a system of congruences with pairwise coprime moduli, which can then be solved using the Chinese remainder theorem.
x = crt(v)
x
12557
Let us check that we get the correct answer.
pow(a, x, p)
2020
We will now use the function pohligHellman to compute some more discrete logarithms and measure the evaluation times.
from algorithms.discreteLogarithm import pohligHellman
%time pohligHellman(47, 191, 100000000003)
CPU times: user 30.6 ms, sys: 0 ns, total: 30.6 ms Wall time: 28.8 ms
6935101882
%time pohligHellman(47, 191, 10000000000000000051)
CPU times: user 29 ms, sys: 0 ns, total: 29 ms Wall time: 28.5 ms
6780065714244411514
%time pohligHellman(47, 191, 1000000000000000000117)
CPU times: user 33.9 ms, sys: 0 ns, total: 33.9 ms Wall time: 32.6 ms
354067223054486232245
%time pohligHellman(47, 191, 10000000000000000000000343, trace = 2)