Cryptography Reference
In-Depth Information
Algorithm 6.6. Baby-step giant-step.
Input
: A finite cyclic group
G
, a generator
g
∈
G
, the order
n
of
G
and an element
a
∈
G
.
Output
:log
g
a
.
Walk the baby steps (precomputation)
:
t
:=
√
n
;
1;
for
i
from
0
to
t
−
1
do
A
[
b
]:=
i
;(
A
is a table indexed by elements of
G
with entries in
{
0
,
1
,...,
t
−
1
}
)
b
:=
bg
;
end do
;
Sort
the list of indices of
A
.
Walk the giant steps and find collision
:
h
b
:=
g
−
1
t
;
:=
(
)
b
a
;
for
j
from
0
to
t
:=
1
do
if
b
is an index of
A
(use binary search to find out) and
A
−
[
b
]=
i
then
return
i
+
tj
end if
;
b
bh
;
end do
.
:=
The first part of the algorithm is a precomputation in the sense that it does not
depend on the element
a
G
whose discrete logarithm we are trying to compute
and hence it is not necessary to repeat it each time the logarithm of a new element
of
G
is computed. After walking the baby steps, we have a table
A
where
A
∈
[
b
]=
i
just means that
g
i
1, and then the list of indices of
this table is sorted. In the second part, after each giant step we can use binary search
on the sorted list of indices of
A
to check whether the group element just generated
is an index of
A
and, if so, we have found the discrete logarithm. This way it is
not necessary in general to walk all the giant steps and some space is saved. The
following proposition establishes the correctness of the algorithm and its running
time:
=
b
∈
G
,for
i
=
0
,
1
,...
t
−
Proposition 6.5
The baby-step giant-step algorithm correctly find
s
the discrete log-
arithm of an element a
(
√
n
∈
G
=
g
and its running time is O
·
polylog
(
n
))
if
n
=|
G
|
.
=
√
n
log
g
a
, so that
g
x
t
2
and
Proof
Let
x
=
=
a
, and let
t
. Then 0
≤
x
<
n
≤
hence
x
is a two-digit number in base
t
, i.e.,
x
=
i
+
tj
where
i
,
j
are base-
t
digits
g
x
g
i
+
tj
g
i
g
t
j
, from which it follows
such that 0
≤
i
,
j
<
t
. Hence
a
=
=
=
(
)
g
−
1
t
that, letting
h
=
(
)
∈
G
as above and multiplying both terms of the equation by
h
j
ah
j
. The second term of this equality is one of the
elements of
G
computed in the giant steps so the algorithm finishes when this value
of
j
is reached in the final loop with the output
i
g
tj
)
−
1
, we have that
g
i
=
(
=
log
g
a
.
The total number of group operations performed is clearly
O
+
tj
=
(
√
n
but we al
so
have to take into account the time taken by sorting and searching. Sorting the
O
)
(
√
n
)
