Cryptography Reference
In-Depth Information
15.5.6 Number field sieve for the DLP
Concepts from the number field sieve for factoring have been applied in the setting of the
DLP. Again, one uses two factor bases, corresponding to ideals in the ring of integers of
some number field (one of the number fields may be
). As with Coppersmith's method,
once sufficiently many relations have been found among elements of the factor bases, special
q
-descent is needed to solve a general instance of the DLP. We refer to Schirokauer [
465
]
for details of the NFS algorithm for the DLP, and also for the heuristic arguments that one
can solve the DLP in
Q
F
p
in
L
p
(1
/
3
,
(64
/
9)
1
/
3
+
o
(1)) bit operations. When
p
has a special
2
n
form (e.g.,
p
1) then the
special number field sieve
(SNFS) can be used to solve
the DLP in (heuristic)
L
p
(1
/
3
,
(32
/
9)
1
/
3
=
±
+
o
(1)) bit operations, see [
466
].
We should also mention the
special function field sieve
(SFFS) for solving the DLP in
F
p
n
, which has heuristic complexity
L
p
n
(1
/
3
,
(32
/
9)
1
/
3
+
o
(1)) bit operations as
p
n
→∞
n
o
(
√
n
)
, see Schirokauer [
464
,
465
].
as long as
p
≤
15.5.7 Discrete logarithms for all finite fields
F
p
when
p
is large or
F
p
n
where
p
is relatively
We have sketched algorithms for the DLP in
p
n
with
p
large and
n>
1. The basic
concepts can be extended to cover all cases, but ensuring that subexponential complexity is
achieved for all combinations of
p
and
n
is non-trivial. Adleman and Demarrais [
2
] were the
first to give a heuristic subexponential algorithm for all finite fields. They split the problem
space into
p>n
and
p
F
q
where
q
small. We have not considered cases
=
≤
n
; in the latter case they have complexity
L
q
(1
/
2
,
3
+
o
(1)) bit
operations as
q
→∞
and in the former case heuristic complexity
L
q
(1
/
2
,c
+
o
(1)) for a
non-explicit constant
c
.
Heuristic algorithms with complexity
L
q
(1
/
3
,c
o
(1)) for all finite fields are given by
Joux and Lercier [
284
] and Joux, Lercier, Smart and Vercauteren [
285
].
+
15.6 Discrete logarithms on hyperelliptic curves
Some index calculus algorithms for the discrete logarithm problem in finite fields generalise
naturally to solving the DLP in the divisor class group of a curve. Indeed, some of these
algorithms also apply to the ideal class group of a number field, but we do not explore that
situation in this topic. An excellent survey of discrete logarithm algorithms for divisor class
groups is Chapter VII of [
61
].
We consider hyperelliptic curves
C
:
y
2
+
H
(
x
)
y
=
F
(
x
) over
F
q
of genus
g
,so
deg(
H
(
x
))
2. Recall that elements of the divisor class
group have a Mumford representation (
u
(
x
)
,y
≤
g
+
1 and deg(
F
(
x
))
≤
2
g
+
−
v
(
x
)) (for curves with a split model there
is also an integer 0
deg(
u
(
x
)) to take into account the behaviour at infinity). Let
D
1
and
D
2
be reduced divisors representing divisor classes of order
r
(where
r
is a prime
such that
r
2
≤
n
≤
g
−
#Pic
0
F
q
(
C
)). The goal is to compute
a
∈ Z
/r
Z
such that
D
2
≡
[
a
]
D
1
.
