Cryptography Reference
In-Depth Information
6.5.4 The Pohlig-Hellman Algorithm and Its Maple
Implementation
We have already mentioned that to make the DL problem difficult, the cyclic group
in which the problem occurs is often chosen to be of prime order, as was the case
in the record computation mentioned in Sect.
6.5.2
. The reason for this is just the
Chinese remainder theorem which, as we have already seen, reduces the problem
of finding the solution of an equation modulo
n
, where
n
=
i
=
1
n
i
with the
n
i
pairwise relatively prime, to the problem of solving the equation modulo
n
i
for each
i
=
1
,...,
k
. This idea was applied by Pohlig and Hellman to the DL problem as
follows:
Proposition 6.6
Let G be a group and g
∈
G an element of order n, where n
=
i
=
1
n
i
and
gcd
g
n
/
n
i
, and a
i
a
n
/
n
i
,
(
n
i
,
n
j
)
=
1
for i
=
j . Let a
∈
g
,g
i
=
=
for each i
=
1
,
2
,...,
k. Then, if x
i
=
log
g
i
a
i
,
log
g
a is the solution in
Z
n
of the
system of congruences:
⎫
⎬
x
≡
x
1
(
mod
n
1
)
x
≡
x
2
(
mod
n
2
)
(6.2)
.
⎭
x
≡
x
k
(
mod
n
k
)
Proof
Each
g
i
has order
n
i
by Proposition 2.5. Let
x
i
=
log
g
i
a
i
∈ Z
n
i
and
x
=
∈ Z
n
. Then
g
x
i
a
n
/
n
i
g
x
n
/
n
i
g
n
/
n
i
x
g
i
log
g
a
=
a
i
=
=
(
)
=
(
)
=
. Since the order
i
of
g
i
is uniquely defined as an element of
Z
n
i
this implies that
x
≡
x
i
(
mod
n
i
)
,for
each
i
k
.Butthe
n
i
are pairwise relatively prime by hypothesis and so the
Chinese remainder theorem tells us that
x
is the unique solution in
=
1
,...,
Z
n
of this system
of congruences.
We see that computation of discrete logarithms in
G
is reduced to the computation
of discrete logarithms in the subgroups
G
i
which have order
n
i
,plussome
additional computations which can be carried out in time
O
=
g
i
. These are
the computations of each of the powers
g
i
and
a
i
and the application of the CRT.
We can use either
the
BSGS or the rho method to compute the discrete logarithm
in
G
i
in time
O
(
polylog
(
n
))
(
√
n
i
·
polylog
(
n
i
))
and hence we can solve the DLP in
G
in time
O
i
=
1
√
n
i
·
. Since the number
k
of factors is
k
polylog
(
n
)
=
O
(
ln
n
)
,wesee
that
O
i
=
1
√
n
i
O
max
i
(
√
n
i
)
·
ln
n
and hence we obtain a running time
=
max
i
(
√
n
i
)
·
for the entire algorithm of
O
. Thus we see that the time to
compute discrete logarithms in
G
is essentially determined by the size of the largest
factor of the group order
n
.
If the prime factorization of
n
is
n
(
polylog
(
n
))
=
i
=
1
p
e
i
p
e
i
.Inthis
case, there is a further step that reduces the computation of a discrete logarithm in
the group
G
i
of order
p
e
i
then we can take
n
i
=
i
to the computation of
e
i
discrete logarithms in groups of
i
