Cryptography Reference
In-Depth Information
Recall from Exercise
10.3.12
that a reduced divisor with Mumford representation
(
u
(
x
)
,v
(
x
)) is said to be a
prime divisor
if the polynomial
u
(
x
) is irreducible over
F
q
.The
degree
of the effective affine divisor is deg(
u
(
x
)). Any effective affine divisor
D
can be
written as a sum of prime effective affine divisors by factoring the
u
(
x
) polynomial of its
Mumford representation. Hence, it is natural to define
D
to be
b
-smooth if it is a sum of
prime effective divisors of degree at most
b
. This suggests selecting the factor base
to
consist of all prime effective affine divisors of degree at most
b
for some smoothness bound
1
B
g
.
One can obtain an algorithm for the DLP of a familiar form, by generating reduced
divisors and testing whether they are smooth. One issue is that our smoothness results for
polynomials apply when polynomials are sampled uniformly from the set of all polynomials
of degree
n
in
≤
b
≤
F
q
[
x
], whereas we now need to apply the results to the set of polynomials
u
(
x
)
∈ F
q
[
x
]ofdegree
g
that arise in Mumford's representation. This issue is handled
using Theorem
15.6.1
.
There are two rather different ways to generate reduced divisors, both of which are
useful for the algorithm.
1. One can take random group elements of the form [
n
]
D
1
or [
n
1
]
D
1
+
[
n
2
]
D
2
and compute
the Mumford representation of the corresponding reduced effective affine divisor. This
is the same approach as used in Section
15.5.1
and, in the context of ideal/divisor
class groups, is sometimes called the
Hafner-McCurley algorithm
. If the divisor is
B
B
and
D
1
and
D
2
.
2. One can consider the effective affine divisor of the function
a
(
x
)
-smooth then we obtain a relation between elements of
yb
(
x
) for random
polynomials
a
(
x
)
,b
(
x
). This idea is due to Adleman, DeMarrais and Huang [
4
]. Since a
principal divisor is equivalent to zero in the ideal class group, if the divisor is
+
B
-smooth
then we get a relation in
B
.
To introduce the instance of the DLP into the system it is necessary to have some relations
involving
D
1
and
D
2
. This can either be done using the first method, or by choosing
a
(
x
) and
b
(
x
) so that points in the support of either
D
1
or
D
2
lie in the support of div(
a
(
x
)
+
yb
(
x
))
(we have seen this kind of idea already, e.g. in Coppersmith's algorithm).
It is convenient to add to
B
∈
F
q
) such that
all points at infinity and all points
P
C
(
F
q
-rational prime divisors with this property). Since the latter
divisors all have order 2 one automatically obtains relations that can be used to eliminate
them during the linear algebra stage of the algorithm. Hence, we say that a reduced divisor
D
=
P
ι
(
P
) (equivalently all
v
(
x
)) in Mumford representation is
b
-
smooth
if
u
(
x
)is
b
-smooth after
any factors corresponding to points of order 2 have been removed.
Let
C
be a hyperelliptic curve over
=
div(
u
(
x
)
,y
−
b<g
. Prime effective
affine divisors on
C
of degree
b
correspond to irreducible polynomials
u
(
x
)ofdegree
b
(and for roughly half of all such polynomials
u
(
x
) there are two solutions
v
(
x
)to
v
(
x
)
2
F
q
of genus
g
and 1
≤
0(mod
u
(
x
))). Hence, it is natural to expect that there are
approximately
q
b
/b
such divisors. It follows that #
+
v
(
x
)
H
(
x
)
−
F
(
x
)
≡
should be around
i
=
1
q
i
/i
B
≈
1
b
p
b
(1
+
2
/
(
p
−
1)) by the same argument as Exercise
15.5.14
.
