Cryptography Reference
In-Depth Information
We refer to Jacobson and van der Poorten [
289
] and Section VII.2.2 of [
61
] for details. It
seems that NUCOMP should be used once the genus of the curve exceeds 10 (and possibly
even for
g
≥
7).
Exercise 10.4.4
Let
C
be a hyperelliptic curve of genus 2 over a field
k
with a ramified
model. Show that every
k
-rational divisor class has a unique representative of one of the
following four forms:
−
∞
∈
k
=∞
=
−
=
1. (
P
)
(
) where
P
C
(
), including
P
.Here
u
(
x
)
(
x
x
P
)or
u
(
x
)
1.
2. 2(
P
)
−
2(
∞
) where
P
∈
C
(
k
), excluding points
P
such that
P
=
ι
(
P
). Here
u
(
x
)
=
(
x
−
x
P
)
2
.
3. (
P
)
+
(
Q
)
−
2(
∞
) where
P,Q
∈
C
(
k
) are such that
P,Q
=∞
,
P
=
Q
,
P
=
ι
(
Q
).
Here
u
(
x
)
=
(
x
−
x
P
)(
x
−
x
Q
).
4. (
P
)
+
(
σ
(
P
))
−
2(
∞
) where
P
∈
C
(
K
)
−
C
(
k
) for any quadratic field extension
K
/
k
,
Gal(
K
/
k
)
=
σ
and
σ
(
P
)
∈{
P,ι
(
P
)
}
.Here
u
(
x
) is an irreducible quadratic in
k
[
x
].
Exercise
10.4.5
can come in handy when computing pairings on hyperelliptic curves.
2
Exercise 10.4.5
Let
D
1
=
div(
u
1
(
x
)
,y
−
v
1
(
x
))
∩ A
and
D
2
=
div(
u
2
(
x
)
,y
−
v
2
(
x
))
∩
2
A
be semi-reduced divisors on a hyperelliptic curve with ramified model over
k
. Write
2
d
1
=
deg(
u
1
(
x
)) and
d
2
=
deg(
u
2
(
x
)). Let
D
3
=
div(
u
3
(
x
)
,y
−
v
3
(
x
))
∩ A
be a semi-
reduced divisor of degree
d
3
such that
D
3
−
d
3
(
∞
)
≡
D
1
−
d
1
(
∞
)
+
D
2
−
d
2
(
∞
). Show
that if
d
2
=
d
3
then
D
1
−
d
1
(
∞
)
≡
D
3
−
D
2
.
10.4.2 Addition of divisor classes on split models
This section is rather detailed and can safely be ignored by most readers. It presents results
of Paulus and Ruck [
429
] and Galbraith, Harrison and Mireles [
202
].
Let
C
be a hyperelliptic curve of genus
g
over
with a split model. We have
already observed that every degree zero divisor class has a representative of the form
D
k
n
+
(
∞
+
)
n
−
(
∞
−
) where
D
is semi-reduced and
n
+
,n
−
∈ Z
+
+
. Lemma
10.3.20
has
shown that we may assume 0
1. One could consider the divisor to be
reduced if this is the case, but this would not be optimal.
The Riemann-Roch theorem implies we should be able to take deg(
D
)
≤
deg(
D
)
≤
g
+
≤
g
but Cantor
+
reduction becomes “stuck” if the input divisor has degree
g
1. The following simple trick
allows us to reduce to semi-reduced divisors of degree
g
(and this essentially completes the
proof of the “Riemann-Roch theorem” for these curves). Recall the polynomial
G
+
(
x
)of
degree
d
=
g
+
1 from Exercise
10.1.22
.
Lemma 10.4.6
Lety
2
+
H
(
x
)
y
=
F
(
x
)
be a hyperelliptic curve of genusg over
k
with split
model. Let u
(
x
)
,v
(
x
)
be a Mumford representation such that
deg(
u
(
x
))
=
g
+
1
. Define
v
‡
(
x
)
G
+
(
x
)
G
+
(
x
)(mod
u
(
x
)))
=
+
(
v
(
x
)
−
∈ k
[
x
]
