Cryptography Reference
In-Depth Information
D.3 Baby-Step Giant-Step Algorithm
Baby-Step Giant-Step Algorithm for Computing Discrete Logs
Given a generator
α
of a cyclic group
G
of order
n
, and
β
∈
G
, the goal is
to compute the discrete logarithm,
x
≡
log
α
β
(mod
n
)
.
√
n
(1) Compute
s
=
.
1, compute (
j,α
j
β
). Then sort the list
by second component in ascending order.
(2)
Baby-Step
:For
j
=0
,
1
,...,s
−
(3)
Giant-Step
:For
i
=1
,
2
,...,s
compute (
α
is
,i
) and sort by first compo-
nent in ascending order.
(4)
Search and Compare
: Search the lists in steps (2) and (3) to see if there
is an
α
j
β
from step (2) and an
α
is
from step (3) such that
α
j
β
=
α
is
.If
so, then compute
x
≡
is
−
j
(mod
n
)
,
which is
log
α
β
(mod
n
)
.
Example D.2
Let
α
=5
,
β
=71
, and
n
= 167
. We want to determine
x
≡
log
5
(71) (mod 167)
.
√
n
First, we calculate
s
=
=12
. The
baby-step
is the computation of
(
j,
5
j
·
71 (mod 167))
for
j
=0
,
1
,...,
11 :
(0
,
71)
,
(1
,
21)
,
(2
,
105)
,
(3
,
24)
,
(4
,
120)
,
(5
,
99)
,
(6
,
161)
,
(7
,
137)
,
(8
,
17)
,
(9
,
85)
,
(10
,
91)
,
(11
,
121)
. Then we sort according to the second element:
j
8
1
3
0
9
10
5
j
·
71
17
21
24
71
85
91
j
5
2
4
11
7
6
5
j
·
71
99
105
120
121
137
161
The
giant-step
is the computation of
(5
12
i
(mod 167)
,i
)
for
i
=1
,
2
,...,
12
:
(152
,
1)
,
(58
,
2)
,
(132
,
3)
,
(24
,
4)
,
(141
,
5)
,
(56
,
6)
,
(162
,
7)
,
(75
,
8)
,
(44
,
9)
,
(8
,
10)
,
(47
,
11)
,
(130
,
12)
. Then we order according to the first component:
15
12
i
8
24
44
47
56
58
i
10
4
9
11
6
2
Search WWH ::
Custom Search