Cryptography Reference
In-Depth Information
Baby-step Giant-step Algorithm
The next algorithm is an improvement of exhaus-
tive search in that it doesn't cycle through all exponents. It is based on the fact that if
m
is
the smallest integer no less than
√
n
, where
n
is the modulus, and
a
x
b
(mod
n
)
we can write
x
=
im
+
j
where 0
≤
i
and
j
<
m
. This yields
a
x
=
a
im
a
j
,
implying that
a
j
(mod
n
),
where (
a
m
)
is an inverse of
a
m
modulo
n
(if this inverse exists). The baby-step giant-step
algorithm exploits this: The algorithm finds a discrete log (if one exists) of
a
x
b
((
a
m
)
)
i
b
(mod
n
)
1.
Let
b
be an integer between 1 and
n
1.
2.
Let
m
be the smallest integer no less than
√
n
.
Make a table whose entries are (
j
,
g
j
) for
j
= 0, 1, 2, . . .,
m
1. The entries for
g
j
should
be the least nonnegative residues modulo
n
.
Compute (
g
m
)
, an inverse of
g
m
modulo
n
. (Of course, this assumes
g
m
is invertible
modulo
n
; if not, this method will fail. Of course, if the modulus is prime, this will not
be a problem.)
3.
5.
Set
y
=
b
.
6.
For
i
from 0 to
m
1 do:
• Search the second components in the table for a
g
j
such that
g
j
=
y
for some index
j
.
• If such an entry is found, compute and return
x
=
im
+
j
.
• If no such entry is found, set
y
equal to the lnr of
y
(
g
m
)
.
This algorithm will usually be superior in running time to exhaustive search because it
only checks a maximum of
m
=
√
n
exponents (whereas exhaustive search may cycle through
n
exponents). However, the table required can be quite large, obviously, if
n
is very large.
Also, the method we use to search the table is important. A sequential search is out of the
question, and a binary search on a sorted table will also be time-consuming; a much prefer-
able alternative is to use a hash table.
E
XAMPLE
.
We'll use baby-step giant-step to solve the congruence
43
x
140 (mod 307).
(Note 43 is a generator modulo the prime 307.) First, since
√
307
17.5214, we'll set
m
=
18. Hence, Table 13.3 will have 18 entries:
Search WWH ::
Custom Search