Cryptography Reference
In-Depth Information
degree of such a curve is the total degree of
F
(
x,y
) as a polynomial). Such curves are
essentially the opposite case to hyperelliptic curves (which have rather high degree in
x
relative to their genus). The trick is simply to note that if
F
(
x,y
) has relatively low degree
compared to its genus then so does
b
(
x
)
d
F
(
x,a
(
x
)) and so the divisor of the function
a
by
has relatively low weight. The main result is an algorithm with heuristic complexity
O
(
q
2
−
2
/
(
d
−
2)
) bit operations for a curve of degree
d
over
−
F
q
.
In the case of non-singular plane quartics (genus 3 curves
C
over
F
q
) Diem takes the
factor base to be a large set of points
B
⊆
C
(
F
q
). He generates relations by choosing
two distinct points
P
1
,P
2
∈
B
c
between them with
the curve
C
. There are two other points of intersection, corresponding to the roots of the
quadratic polynomial
F
(
x,bx
and intersecting the line
y
=
bx
+
+
−
−
x
P
2
)) and so with probability roughly
1
/
2 we expect to get a relation in the divisor class group among points in
C
(
c
)
/
((
x
x
P
1
)(
x
F
q
). Diem
shows that the algorithm has complexity
O
(
q
) bit operations.
Due to lack of space, and since our focus in this topic is hyperelliptic curves (though, it
is important to note that Smith [
514
] has given a reduction of the DLP from hyperelliptic
curves of genus 3 to plane quartics), we do not present any further details. Interested readers
should see [
161
,
165
].
15.9.2 The algorithm of Enge-Gaudry-Thome and Diem
The algorithms for the DLP in the divisor class group of a hyperelliptic curve in Sec-
tions
15.6.1
and
15.6.2
had complexity
L
q
g
(1
/
2
,
√
2
+
o
(1)) bit operations as
q
→∞
.A
natural problem is to find algorithms with complexity
L
q
g
(1
/
3
,c
o
(1)), and this is still
open in general. However, an algorithm is known for curves of the form
y
n
+
+
F
(
x,y
)
=
0
g
2
/
3
.Wedo
not have space to give the details, so simply quote the results and refer to Enge and
Gaudry [
181
], Enge, Gaudry and Thom´e[
182
] and Diem [
160
]. An algorithm to compute
the group structure of Pic
C
(
g
1
/
3
where deg
y
(
F
(
x,y
))
≤
n
−
1 and deg
x
(
F
(
x,y
))
=
d
for
n
≈
and
d
≈
o
(1)))
bit operations for some constant
c
. For the discrete logarithm problem the algorithm has
heuristic complexity
O
(
L
q
g
(1
/
3
,c
+
F
q
) is given with heuristic complexity of
O
(
L
q
g
(1
/
3
,c
+
o
(1))) bit operations where
c
is a constant.
o
(1)) algorithms for factoring or DLP in finite fields, the algo-
rithm does not use two different factor bases. Instead, the algorithm is basically the same
idea as Sections
15.6.2
and
15.9.1
with a complexity analysis tailored for curves of a certain
form.
Unlike the
L
N
(1
/
3
,c
+
15.9.3 Index calculus for general elliptic curves
In this section we briefly discuss why there does not seem to be a subexponential algorithm
for the DLP on general elliptic curves.
An approach to an index calculus algorithm for elliptic curves was already discussed by
Miller [
384
] in the paper that first proposed elliptic curves for cryptography. In particular,
