The Baby-Step-Giant-Step algorithm.
The Baby-Step-Giant-Step algorithm is an algorithm introduced by Dan Shanks in 1969, which can
be applied to solve the discrete logarithm problem in a cyclic group.
Let G be a cyclic group with n elements, and let a 2 G be a generator of the group. It means that
G = {a, a2 , . . . , an = e}. In particular, every x 2 G can be written as x = as , for some s 2 Z.
The exponent s, which by Lagrange’s theorem it is only well defined modulo n, is by definition the
discrete logarithm of x in base a
s := loga (x) mod n.
The Baby-Step-Giant-Step algorithm is a deterministic algorithm for computing the discrete log-
arithm in an arbitrary finite cyclic group. It exploits the fact that every element x 2 G can be
written as
x = aj+mi , (1)
p
for integers m, i, j satisfying m ⇠ n, and 0 i, j m. Equation (1) can be rewritten as
ai = xa mj . Then the logarithm loga (x) is obtained by comparing two lists: the baby steps ai and
the giant steps xa mj , for 0 i, j m. When a coincidence is found between the two lists, namely
one has ai0 = xa mj0 for some i0 and j0 , then
log(x)a = i0 + mj0 .
p
By BSGS, one obtains the desired logarithm by computing at most 2m ⇠ 2 p powers modulo
p and comparing the two lists. By the naif method one could possibly have to compute up to p
powers modulo p, before obtaining the desired logarithm.
Example. Fix p = 433 and let a = 7 be a primitive root in Z⇤p . We want to calculate the discrete
p
logarithm of x = 166 in base a. In this case, m = 21 ⇠ 433.
We first produce the list of the Baby-Steps:
ai mod p, for 0 i m 1
a0 = 1
a1 = 7
a2 = 49
a3 = 343
a4 = 236
a5 = 353
a6 = 306
a7 = 410
a8 = 272
a9 = 172
a10 = 338
a11 = 201
a12 = 108
a13 = 323
a14 = 96
a15 = 239
a16 = 374
a17 = 20
a18 = 140
a19 = 114
a20 = 365
m 21
a =a = 292
10
Next we produce the list of the Giant-Steps:
mj
xa mod p, for 0 j m 1
and each time we check whether the value the new Giant-Step already appears in the list of the
Baby-Steps. When that is the case, we are done.
x · a0 = 166
x · a 21 = 409
x · a 42 = 353 !!!
We have found a coincidence between the two lists: a5 = x · a 42
. This means that
x = a5+42 = a47 and log7 (166) = 47.
Indeed one can check that 747 = 166 mod 433.
The Pohlig-Hellman algorithm.
Q
Let G be a cyclic group of order N and suppose that N = i qiei is the product of small distinct
primes qi , for i = 1, . . . , s. Then G ⇠
= G1 ⇥ . . . ⇥ Gs , with
#Gi = qiei and Gi ⇠
= Zqiei .
By the Chinese Remainder Theorem the discrete logarithm problem in G can be reduced to the
discrete problem in the smaller groups Gi . Hence the essential case is G = Zqe , for q odd prime
and e 1.
Let P be a generator of G and let Q be a given element. Then Q = kP , for some integer
k mod q e . We want to determine k, which by definition is the discrete logarithm of Q in base P .
Recall that the subgroups of G are linearly ordered
0 = qe G ⇢ qe 1
G ⇢ . . . ⇢ qG ⇢ G,
where q m G is the q e m -torsion subgroup, for m = 0, 1, . . . , e.
The Pohlig-Hellman algorithm provides a method to solve the DLP in G. Write k in base q,
as k = k0 + k1 q + . . . + ks q s , for kj 2 {0, . . . , q e 1}. Then
Q = kP = k0 P + k1 qP + . . . + ks q s P, (⇤)
where the summand km q m P is an element in the q e m -torsion subgroup of G, for m = 0, 1, . . . , e.
In order to determine the coefficients km , we precompute the elements of the q-torsion
T = {0, q e 1
P, . . . , (q 1)q e 1
P }.
By multiplying both terms of the equation (⇤) by q e 1
we get
qe 1
Q = k0 q e 1
P,
which is an element in the q-torsion T . By comparing it with the elements of T , we determine k0 .
In general, once we have determined k0 , . . . , kj 1 , we obtain kj as follows: we multiply both terms
of the equation
Q k0 P . . . kj 1 q j 1 P = kj q j P + . . . + ks q s P
by q e j 1 . The only surviving element on the right hand side is kj q e 1
P . By comparing it with
the elements of T , we determine kj .
11
