Cryptography Reference
In-Depth Information
therefore assume the expected number of trials to get an
L
q
g
(1
/
2
,c
)-smooth polynomial is
L
q
g
(1
/
2
,
1
/
(2
c
)
o
(1)) as
g
tends to infinity.
We also need some relations involving
D
1
and
D
2
. Adleman, DeMarrais and Huang do
this by first decomposing
D
1
and
D
2
as a sum of prime divisors. Then they “smooth” each
prime divisor div(
u
(
x
)
,y
+
−
v
(
x
)) by choosing polynomials
B
(
x
)
,W
(
x
)
∈ F
q
[
x
], setting
A
(
x
)
A
(
x
)
=
B
(
x
)(
v
(
x
)
+
H
(
x
)) (mod
u
(
x
)) and then
A
(
x
)
=
+
u
(
x
)
W
(
x
). One com-
(
A
(
x
)
2
F
(
x
)
B
(
x
)
2
). By construction,
u
(
x
)
putes
N
(
x
)
=
−
H
(
x
)
A
(
x
)
B
(
x
)
−
|
N
(
x
) and
one continues randomly choosing
A
and
W
until
N
(
x
)
/u
(
x
)is
b
-smooth.
The details of the algorithm are then the same as the algorithm in Section
15.5.1
: one
uses linear algebra modulo
r
to get a relation [
a
]
D
1
+
[
b
]
D
2
≡
0 (again, care is needed
when there are two points at infinity). We leave the details as an exercise.
Exercise 15.6.3
Write pseudocode for the Adleman, DeMarrais, Huang algorithm.
The heuristic complexity of the algorithm is of the same form as the earlier algorithm (the
cost of smoothing the divisors
D
1
and
D
2
is heuristically the same as finding less tha
n
2
g
relations, so is negligible. One obtains heuristic asymptotic complexity of
L
q
g
(1
/
2
,
√
2
+
o
(1)) bit operations as
g
tends to infinity. This is much better than the complexity claimed
in [
4
] since that paper also gives an algorithm to compute the group structure (and so the
linear algebra requires computing the Hermite normal form).
These ideas will be used again in Section
15.9.1
.
15.6.3 Gaudry's algorithm
Gaudry [
223
] considered the algorithm of Section
15.6.1
for fixed genus, rather than
asympotically as
g
→∞
. In particular, he chose the smoothness bound
b
=
1 (so the factor
base
only consists of degree 1 prime divisors, i.e. points). Good surveys of Gaudry's
algorithm are given in Chapter VII of [
61
] and Section 21.2 of [
16
].
B
Exercise 15.6.4
Let
C
be a hyperelliptic curve of genus
g
over a finite field
F
q
. Show
that the number of prime divisors on
C
of degree 1 is #
C
(
F
q
)
=
q
(1
+
o
(1)) for fixed
g
as
q
. Hence, show that the probability that a randomly chosen reduced divisor is
1-smooth is
→∞
1
g
!
(1
+
o
(1)) as
q
→∞
.
Exercise 15.6.5
Following Exercise
15.6.4
, it is natural to conjecture that one needs to
choose
O
(
g
!
q
(1
+
o
(1))) divisors (again, this is for fixed
g
as
q
→∞
, in which case it is
more common to write it as
O
(
q
(1
+
o
(1)))) to find enough relations to have a non-trivial
linear dependence in
. Under this assumption, show that the heuristic expected running
time of Gaudry's algorithm is at most
B
c
1
g
2
g
!
q
(1
c
2
g
3
q
2
M
(log(
q
)))
O
(
q
2
M
(log(
q
))(1
+
o
(1))
M
(log(
q
))
+
=
+
o
(1)))
(15.11)
bit operations (for some constants
c
1
and
c
2
) for fixed
g
as
q
→∞
.
