Cryptography Reference
In-Depth Information
Exercise 13.2.6
Recall the Tonelli-Shanks algorithm for computing square roots modulo
p
from Section
2.9
. A key step of the algorithm is to find a solution
j
to the equation
b
y
2
j
(mod
p
) where
y
has order 2
e
. Write down the Pohlig-Hellman method to solve
this problem. Show that the complexity is
O
(log(
p
)
2
M
(log(
p
))) bit operations.
=
=
i
=
1
x
i
where 2
B
. Prove that
i
=
1
x
i
≤
Exercise 13.2.7
Let
B
∈ N
>
3
.Let
N
≤
x
i
≤
B
log(
N
)
/
log(
B
).
Hence,
performs
O
(log(
N
)
2
show
that
the
Pohlig-Hellman
method
+
B
log(
N
)
/
log(
B
)) group operations.
Remark 13.2.8
As we will see, replacing exhaustive
s
earch by the baby-step-giant-step
algorithm improves the complexity to
O
(log(
N
)
2
+
√
B
log(
N
)
/
log(
B
)) group operations
(at the cost of more storage).
Algorithm
12
can be improved, when there is a prime power
l
e
dividing
N
with
e
large, by
structuring it differently. Secti
o
n 11.2.3 of Shoup [
497
] gives a method to compute the DLP
in a group of order
l
e
in
O
(
e
√
l
e
log(
e
)log(
l
)) group operations (this is using baby-step-
giant-step rather than exhaustive search). Algorithm 1 and Corollary 1 of Sutherland [
537
]
give an algorithm that requires
O
(
e
√
l
+
+
e
log(
l
) log(
e
)
/
log(log(
e
)))
(13.1)
group operations. Sutherland also considers non-cyclic groups.
If
N
is
B
-smooth then summing the improved complexity statements over the prime
powers dividing
N
gives
O
(log(
N
)
√
B/
log(
B
)
+
log(
N
) log(log(
N
)))
(13.2)
group operations for the DLP (it is not possible to have a denominator of log(log(log(
N
)))
since not all the primes dividing
N
necessarily appear with high multiplicity).
13.3 Baby-step-giant-step (BSGS) method
This algorithm, usually credited to Shanks,
3
exploits an idea called the time/mem
o
ry
=
√
r
tradeoff. Suppose
g
has prime order
r
and that
h
=
g
a
for some 0
≤
a<r
.Let
m
.
Then there are integers
a
0
,a
1
such that
a
=
a
0
+
ma
1
and 0
≤
a
0
,a
1
<m
.Itfollowsthat
g
a
0
h
(
g
−
m
)
a
1
=
and this observation leads to Algorithm
13
. The algorithm requires storing a large list of
values and it is important, in the second stage of the algorithm, to be able to efficiently
determine whether or not an element lies in the list. There are a number of standard solutions
to this problem including using binary trees, hash tables or sorting the list after line 7 of
the algorithm (see, for example, parts II and III of [
136
] or Section 6.3 of [
283
]).
3
Nechaev [
405
] states it was known to Gel'fond in 1962.
