Cryptography Reference
In-Depth Information
13.1 Exhaustive search
The simplest algorithm for the DLP is to sequentially compute
g
a
for 0
≤
a<r
and
test equality of each value with
h
. This requires at most
r
−
2 group operations and
r
comparisons.
Exercise 13.1.1
Write pseudocode for the exhaustive search algorithm for the DLP and
verify the claims about the worst-case number of group operations and comparisons.
If the cost of testing equality of group elements is
O
(1) group operations then the
worst-case running time of the algorithm is
O
(
r
) group operations. It is natural to assume
that testing equality is always
O
(1) group operations, and this will always be true for the
algebraic groups considered in this topic. However, as Exercise
13.1.2
shows, such an
assumption is not entirely trivial.
Exercise 13.1.2
Suppose projective coordinates are used for elliptic curves
E
(
F
q
) to speed
up the group operations in the exhaustive search algorithm. Show that testing equality
between a point in projective coordinates and a point in affine or projective coordinates
requires at least one multiplication in
F
q
(and so this cost is not linear). Show that, never-
theless, the cost of testing equality is less than the cost of a group operation.
For the rest of this chapter we assume that groups are represented in a compact way
and that operations involving the representation of the group (e.g., testing equality) all cost
less than the cost of one group operation. This assumption is satisfied for all the algebraic
groups studied in this topic.
13.2 The Pohlig-Hellman method
g
a
so that
h
lies in the cyclic group generated by
g
. Suppose
Let
g
have order
N
and let
h
=
=
i
=
1
l
e
i
. The idea of the Pohlig-Hellman
1
method [
432
] is to compute
a
modulo
the prime powers
l
e
i
i
and then recover the solution using the Chinese remainder theorem.
The main ingredient is the following group homomorphism, which reduces the discrete
logarithm problem to subgroups of prime power order.
N
Lemma 13.2.1
Suppose g has order N and l
e
|
N. The function
g
N/l
e
l
e
(
g
)
=
of order l
e
. Hence,
is a group homomorphism from
g
to the unique cyclic subgroup of
g
=
g
a
then
if h
l
e
(
g
)
a
(mod
l
e
)
.
l
e
(
h
)
=
Exercise 13.2.2
Prove Lemma
13.2.1
.
1
The paper [
432
] is authored by Pohlig and Hellman and so the method is usually referred to by this name, although Silver,
Schroeppel, Block and Nechaev also discovered it.
