We will perform the baby-step/giant-step algorithm to compute $\log_{a} b$ in $\mathbf{Z}_{p}^*$, where $a = 47$, $b = 191$, and $p = 829$ is a prime number.
a = 47
b = 191
p = 829
Let use first perform the giant steps. Since $p$ is a prime, the maximal order of an element of $\mathbf{Z}_{p}^*$ is $p-1$. Therefore, we will perform $m = \lceil \sqrt{p-1} \rceil$ giant steps. In step $i$, the value $a^{mi} \bmod{p}$ is computed by repeatedly multiplying the last value by $a^m \bmod{p}$, and is then used as a key in a dictionary for the value $i$.
order = p - 1
m = ceil(sqrt(order))
am = pow(a, m, p)
gs = {1: 0}
ap = 1
for i in range(1, m):
ap = ap * am % p
gs[ap] = i
print(i, ap)
gs
1 514 2 574 3 741 4 363 5 57 6 283 7 387 8 787 9 795 10 762 11 380 12 505 13 93 14 549 15 326 16 106 17 599 18 327 19 620 20 344 21 239 22 154 23 401 24 522 25 541 26 359 27 488 28 474
{1: 0, 514: 1, 574: 2, 741: 3, 363: 4, 57: 5, 283: 6, 387: 7, 787: 8, 795: 9, 762: 10, 380: 11, 505: 12, 93: 13, 549: 14, 326: 15, 106: 16, 599: 17, 327: 18, 620: 19, 344: 20, 239: 21, 154: 22, 401: 23, 522: 24, 541: 25, 359: 26, 488: 27, 474: 28}
We will now perform the baby steps. In step $j$, the value $b \cdot a^{-j} \bmod{p}$ is computed by repeatedly multiplying the last value by $a^{-1} \bmod{p}$, and is then stored in a list.
bp = b
ai = a^-1 % p
bs = []
for j in range(m):
bs.append(bp)
bp = bp * ai % p
print(j+1, bp)
bs
1 251 2 217 3 181 4 533 5 223 6 675 7 32 8 424 9 644 10 243 11 111 12 20 13 265 14 817 15 670 16 173 17 427 18 62 19 407 20 626 21 419 22 785 23 246 24 358 25 184 26 780 27 387 28 361 29 431
[191, 251, 217, 181, 533, 223, 675, 32, 424, 644, 243, 111, 20, 265, 817, 670, 173, 427, 62, 407, 626, 419, 785, 246, 358, 184, 780, 387, 361]
We now find the index $j$ of the first element of the above list to appear as a key in the previously computed dictionary. If this key points to value $i$, then we have $a^{mi} \equiv b \cdot a^{-j} \pmod{p}$, allowing us to express $b \equiv a^{j + mi} \pmod{p}$.
j = next(i for i, bp in enumerate(bs) if bp in gs)
x = j + m * gs[bs[j]]
x
230
j
27
Let us check that we get the correct answer.
pow(a, x, p)
191
We will now use the function babyStepGiantStep
to compute some more discrete logarithms and measure the evaluation times.
from algorithms.discreteLogarithm import babyStepGiantStep
babyStepGiantStep(104, 164, 197, order=7)
4
pow(104, 186, 197)
164
pow(104, 4, 197)
164
%time babyStepGiantStep(47, 191, 100000000003)
CPU times: user 884 ms, sys: 14.8 ms, total: 899 ms Wall time: 898 ms
6935101882
%time babyStepGiantStep(47, 191, 10000000000000000051) # expected time: roughly 2 hours