Baby-step/giant-step algorithm

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.

In [1]:
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$.

In [2]:
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
Out[2]:
{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.

In [3]:
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
Out[3]:
[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}$.

In [4]:
j = next(i for i, bp in enumerate(bs) if bp in gs)
x = j + m * gs[bs[j]]
x
Out[4]:
230
In [5]:
j
Out[5]:
27

Let us check that we get the correct answer.

In [6]:
pow(a, x, p)
Out[6]:
191

Running time comparison

We will now use the function babyStepGiantStep to compute some more discrete logarithms and measure the evaluation times.

In [7]:
from algorithms.discreteLogarithm import babyStepGiantStep
In [8]:
babyStepGiantStep(104, 164, 197, order=7)
Out[8]:
4
In [9]:
%time babyStepGiantStep(47, 191, 100000000003)
CPU times: user 1.2 s, sys: 0 ns, total: 1.2 s
Wall time: 1.2 s
Out[9]:
6935101882
In [10]:
%time babyStepGiantStep(47, 191, 10000000000000000051) # expected time: roughly 2 hours
---------------------------------------------------------------------------
KeyboardInterrupt                         Traceback (most recent call last)
<timed eval> in <module>

~/fri/kirv/kriptografija-in-racunalniska-varnost/kirv/notebooks/algorithms/discreteLogarithm.py in babyStepGiantStep(a, b, n, order, trace)
     23     ap = 1
     24     for i in xxrange(1, m):
---> 25         ap = ap * am % n
     26         gs[ap] = i
     27         if trace:

~/sage/local/lib/python3.8/site-packages/sage/rings/finite_rings/integer_mod.pyx in sage.rings.finite_rings.integer_mod.IntegerMod_abstract.__mod__ (build/cythonized/sage/rings/finite_rings/integer_mod.c:7213)()
    491             return NotImplemented
    492         from .integer_mod_ring import IntegerModRing
--> 493         R = IntegerModRing(modulus)
    494         if (<Element>self)._parent._IntegerModRing_generic__order % R.order():
    495             raise ArithmeticError(f"reduction modulo {modulus!r} not defined")

~/sage/local/lib/python3.8/site-packages/sage/structure/factory.pyx in sage.structure.factory.UniqueFactory.__call__ (build/cythonized/sage/structure/factory.c:2258)()
    367         key, kwds = self.create_key_and_extra_args(*args, **kwds)
    368         version = self.get_version(sage_version)
--> 369         return self.get_object(version, key, kwds)
    370 
    371     cpdef get_object(self, version, key, extra_args):

~/sage/local/lib/python3.8/site-packages/sage/structure/factory.pyx in sage.structure.factory.UniqueFactory.get_object (build/cythonized/sage/structure/factory.c:2356)()
    369         return self.get_object(version, key, kwds)
    370 
--> 371     cpdef get_object(self, version, key, extra_args):
    372         """
    373         Returns the object corresponding to ``key``, creating it with

~/sage/local/lib/python3.8/site-packages/sage/rings/finite_rings/integer_mod_ring.py in get_object(self, version, key, extra_args)
    196     """
    197     def get_object(self, version, key, extra_args):
--> 198         out = super(IntegerModFactory,self).get_object(version, key, extra_args)
    199         category = extra_args.get('category', None)
    200         if category is not None:

src/cysignals/signals.pyx in cysignals.signals.python_check_interrupt()

KeyboardInterrupt: