Cryptography Reference
In-Depth Information
is notable that performing a Cantor reduction step on a divisor of degree
d
in this case
usually yields another divisor of degree
d
. This phenomena will be discussed in detail in
Section
10.4.2
.
We now consider the uniqueness of the reduced divisor of Theorem
10.3.21
.
Lemma
10.3.24
below shows that non-uniqueness can only arise with split or inert models.
It follows that there is a unique reduced divisor in every divisor class for hyperelliptic
curves with ramified model. For hyperelliptic curves with split or inert model there is not
necessarily a unique reduced divisor.
Lemma 10.3.24
Let y
2
+
H
(
x
)
y
=
F
(
x
)
be a hyperelliptic curve over
k
of genus g. Let
d
H
=
deg(
F
(
x
))
. Let D
1
and D
2
be semi-reduced divisors of degree
at most g. Assume that D
1
=
deg(
H
(
x
))
and d
F
=
D
2
but D
1
≡
D
2
. Then d
F
=
2
g
+
2
or d
H
=
g
+
1
.
2. Let
D
3
=
ι
∗
(
D
2
) so that
D
3
≡
Proof
First note that
d
H
≤
g
+
1 and
d
F
≤
2
g
+
D
1
+
0 as an affine divisor. Let
D
3
be the semi-reduced divisor equivalent to
D
3
(i.e., by removing all occurences (
P
)
D
1
−
D
2
≡
+
(
ι
(
P
))). Note that the degree of
D
3
is at most
2
g
and that
D
3
=
0. Since
D
3
≡
0 and
D
3
is an effective affine divisor we have
D
3
=
div(
G
(
x,y
)) on
C
∩ A
2
for some non-zero polynomial
G
(
x,y
). Without loss of generality,
G
(
x,y
)
=
a
(
x
)
−
b
(
x
)
y
. Furthermore,
b
(
x
)
=
0 (since div(
a
(
x
)) is not semi-reduced for
any non-constant polynomial
a
(
x
)).
Exercise
10.1.21
shows that the degree of div(
a
(
x
)
2
−
b
(
x
)
y
)on
C
∩ A
is the degree
of
a
(
x
)
2
F
(
x
)
b
(
x
)
2
. We need this degree to be at most 2
g
.Thisis
+
H
(
x
)
a
(
x
)
b
(
x
)
−
easily achieved if
d
F
≤
2
g
(in which case
d
H
=
g
+
1 for the curve to have genus
g
).
2 then we need either deg(
a
(
x
)
2
)
deg(
F
(
x
)
b
(
x
)
2
)or
However, if 2
g
+
1
≤
d
F
≤
2
g
+
=
deg(
F
(
x
)
b
(
x
)
2
). The former case is only possible if
d
F
is even
deg(
H
(
x
)
a
(
x
)
b
(
x
))
=
(i.e.,
d
F
=
2
g
+
2). If
d
F
=
2
g
+
1 and
d
H
≤
g
then the latter case implies deg(
a
(
x
))
≥
deg(
b
(
x
)) and so deg(
a
(
x
)
2
)
>
deg(
F
(
x
)
b
(
x
)
2
) and deg(
G
(
x,y
))
>
2
g
.
g
+
1
+
For hyperelliptic curves of fixed (small) genus it is possible to give explicit formulae for
the general cases of the composition and reduction algorithms. For genus 2 curves this was
done by Harley [
251
] (the basic idea is to formally solve for
u
†
(
x
) such that
u
†
(
x
)
u
(
x
)
=
monic(
v
(
x
)
2
F
(
x
)) as in equation (
10.10
)). For extensive discussion and
details (and also for non-affine coordinate systems for efficient hyperelliptic arithmetic) we
refer to Sections 14.4, 14.5 and 14.6 of [
16
].
+
H
(
x
)
v
(
x
)
−
10.4 Addition in the divisor class group
We now show how Cantor's addition and reduction algorithms for divisors on the affine
curve can be used to perform arithmetic in the divisor class group of the projective curve.
A first remark is that Lemma
10.3.3
implies that every degree zero divisor class on a
hyperelliptic curve has a representative of the form
D
n
+
(
∞
+
)
n
−
(
∞
−
) where
D
is a
+
+
semi-reduced (hence, affine and effective) divisor and
n
+
,n
−
∈ Z
(necessarily, deg(
D
)
+
n
+
+
n
−
=
0).
