Cryptography Reference
In-Depth Information
≤
≤
−
deg(
u
(
x
)) note that Lemma
10.4.14
maps
n
to
n
†
=
+
+
may assume 0
n
g
n
(
g
deg(
u
(
x
)) then
n>n
†
≥
1)
0 and continuing the process
gives a reduced divisor. On the other hand, if
n<
0 then using
G
−
(
x
) instead one has
n
†
=
−
deg(
u
(
x
)). Hence, if
n>g
−
deg(
u
†
(
x
))
deg(
u
†
(
x
)).
n
+
g
+
1
−
≤
g
−
Exercise 10.4.17
Let
C
:
y
2
+
H
(
x
)
y
=
F
(
x
) be a hyperelliptic curve of genus
g
over
F
q
with split model. If
g
is even, show that the inverse of div(
u
(
x
)
,v
(
x
)
,n
)isdiv(
u
(
x
)
,
−
v
(
x
)
−
(
H
(
x
)(mod
u
(
x
)))
,g
n
). If
g
is odd then show that computing the inverse
of a divisor may require performing composition and reduction at infinity.
−
deg(
u
(
x
))
−
Example 10.4.18
Let
C
:
y
2
x
6
3 and
G
+
(
x
)
x
3
.Let
=
+
x
+
1 over
F
37
. Then
d
=
=
∞
+
)
∞
−
)
D
=
(1
,
22)
+
(2
,
17)
+
(
−
(
−
D
∞
, which is represented as div(
u
(
x
)
,v
(
x
)
,
1)
x
2
where
u
(
x
)
=
(
x
−
1)(
x
−
2)
=
+
34
x
+
2 and
v
(
x
)
=
32
x
+
27. This divisor is not
reduced. Then
v
‡
(
x
)
=
x
3
+
+
33 and deg(
v
‡
(
x
)
2
−
=
4. Indeed,
v
‡
(
x
)
2
−
25
x
F
(
x
))
=
13
u
(
x
)
u
†
(
x
) where
u
†
(
x
)
=
x
2
+
+
2. It follows that
v
†
(
x
)
=
+
F
(
x
)
28
x
7
x
22 and
that
div(
u
†
(
x
)
,v
†
(
x
)
,
0)
,
div(
u
(
x
)
,v
(
x
)
,
1)
≡
which is reduced.
Explicit formulae for all these operations for genus 2 curves of the form
y
2
x
6
=
+
F
4
x
4
F
3
x
3
F
2
x
2
+
+
+
F
1
x
+
F
0
have been given by Erickson, Jacobson, Shang, Shen
and Stein [
184
].
Uniqueness of the representation
We have shown that every divisor class for hyperelliptic curves with a split model contains
a reduced divisor. We now discuss the uniqueness of this reduced divisor, following Paulus
and R uck [
429
].
Theorem 10.4.19
Let C be a hyperelliptic curve over
of genus g with split model. Then
every divisor class has a unique representative of the form
k
∞
+
)
∞
−
)
D
+
n
(
+
(
g
−
deg(
D
)
−
n
)(
−
D
∞
where D is a semi-reduced divisor (hence, affine and effective) and
0
≤
n
≤
g
−
deg(
D
)
.
Proof
Existence has already been proved using the reduction algorithms above, so it suffices
to prove uniqueness. Hence, suppose
∞
+
)
∞
−
)
D
1
+
n
1
(
+
(
g
−
deg(
D
1
)
−
n
1
)(
−
D
∞
∞
+
)
∞
−
)
≡
D
2
+
n
2
(
+
(
g
−
deg(
D
2
)
−
n
2
)(
−
D
∞
with all terms satisfying the conditions of the theorem. Then, taking the difference and
adding div(
u
2
(
x
))
∞
+
)
∞
−
)), there is a function
f
(
x,y
)
=
D
2
+
ι
(
D
2
)
−
deg(
D
2
)((
+
(
