Cryptography Reference
In-Depth Information
•
Algorithms that do not attempt to exploit special characteristics of the group
in which the DLP must be solved.
Algorithms of the first category are often called
special-purpose algorithms
,
whereas algorithms of the second category are called
generic algorithms
. Let's start
with the second category of algorithms.
7.4.1
Generic Algorithms
Let
G
be a cyclic group and
g
be a generator in this group. The difficulty of
computing discrete logarithms to the base
g
in
G
then depends on whether we know
the order of the group (i.e.,
|
G
|
). If we don't know
|
G
|
, then the
Baby-step giant-
step algorithm
is the best we can do. It has a running time of
O
(
|
G
|
log
|
G
|
) and
memory requirements of
O
(
, then we can do better.
In this case, we can use
Pollard's
ρ
-algorithm
, which is slightly more efficient than
the Baby-step giant-step algorithm. In fact, Pollard's
ρ
-algorithm has a running-time
|
G
|
). If, however, we know
|
G
|
complexity of
O
(
|
G
|
) and requires almost no memory. It has been shown that this
running time is a lower bound for any general-purpose algorithm to compute discrete
logarithms in a cyclic group (if the factorization of the group order is not known)
[12].
, then we can use
the
Pohlig-Hellman algorithm
, which has a running time of
O
(
√
q
log
q
) (where
q
is
the largest prime factor of
If, in addition to
|
G
|
, we also know the factorization of
|
G
|
|
G
|
). This result implies, for example, that in DLP-based
Z
p
,
p
cryptosystems for
1 must have at least one large prime factor (as already
mentioned in Section 7.2.1).
−
7.4.2
Special-Purpose Algorithms
If we are talking about special-purpose algorithms, then we are talking about specific
groups. If, for example, we are talking about
Z
p
, then there are basically two
algorithms to solve the DLP in a subexponential running time.
The
index calculus algorithm
has a running time of
L
p
[
2
,c
] for some small
constant
c
;
•
•
The NFS algorithm can also be used to compute discrete logarithms. Remem-
ber that it has a running time of
L
p
[
3
,
1
.
923].
Consequently, the NFS algorithm is the algorithm of choice to solve the DLP
Z
p
.
in
