Cryptography Reference
In-Depth Information
Let
C
:
y
2
Exercise 10.4.12
+
H
(
x
)
y
=
F
(
x
) where deg(
F
(
x
))
<
2
d
=
2
g
+
2bea
hyperelliptic curve over
of genus
g
with split model. Let div(
u
(
x
)
,v
(
x
)
,n
)beadegree
zero divisor as in Definition
10.4.9
such that
d
k
deg(
u
(
x
)). Let (
u
†
(
x
)
,v
†
(
x
)) be the poly-
nomials arising from a Cantor reduction step. Show that div(
u,v,n
)
≤
div(
u
†
,v
†
,n
†
)
≡
where if deg(
v
(
x
))
<d
then
n
†
=
deg(
u
†
(
x
)) and if deg(
v
(
x
))
n
+
g
+
1
−
≥
d
then
n
†
=
deg(
u
†
(
x
)).
n
+
deg(
v
(
x
))
−
Let
C
:
y
2
=
x
6
+
F
7
.Let
D
1
=
−
−
=
Example 10.4.13
3 over
div((
x
1)(
x
2)
,
2
,
0)
(1
,
2)
+
(2
,
2)
−
D
∞
and
D
2
=
div((
x
−
3)(
x
−
4)
,
2
,
0)
=
(3
,
2)
+
(4
,
2)
−
D
∞
. Cantor
addition gives
D
1
+
D
2
=
D
3
=
div((
x
−
1)(
x
−
2)(
x
−
3)(
x
−
4)
,
2
,
−
1), which is not
a reduced divisor. Applying Cantor reduction to
D
3
results in
u
†
(
x
)
=
(
x
−
5)(
x
−
6)
and
v
†
(
x
)
2 and
n
†
=
deg(
u
†
(
x
))
=−
n
3
+
(
g
+
1)
−
=−
1
+
3
−
2
=
0. Hence, we have
D
3
≡
div((
x
−
5)(
x
−
6)
,
−
2
,
0), which is a reduced divisor.
We now explain the behaviour of a composition at infinity and reduction step.
Lemma 10.4.14
LetC
:
y
2
+
H
(
x
)
y
=
F
(
x
)
where
deg(
F
(
x
))
=
2
d
=
2
g
+
2
be a hyper-
elliptic curve over
of genus g with split model. Let
div(
u
(
x
)
,v
(
x
)
,n
)
beadegreezero
divisor as in Definition
10.4.9
such that
1
k
1
. Let v
‡
(
x
)
, u
†
(
x
)
and v
†
(
x
)
≤
deg(
u
(
x
))
≤
g
+
be as in Lemma
10.4.6
. Let n
†
=
1)
and D
†
=
div(
u
†
(
x
)
,v
†
(
x
)
,n
†
)
.
n
+
deg(
u
(
x
))
−
(
g
+
Then
D
†
+
v
‡
(
x
))
div(
u
†
(
x
))
.
D
=
div(
y
−
−
If one uses G
−
(
x
)
in Lemma
10.4.6
then n
†
=
deg(
u
†
(
x
))
.
n
+
g
+
1
−
2
and
there is no adjustment at infinity (the point of the operation in this case is to lower the degree
from deg(
u
(
x
))
2
div(
u
†
,y
v
†
)
It follows that if deg(
u
(
x
))
=
g
+
1 then div(
u,y
−
v
)
∩ A
≡
−
∩ A
1todeg(
u
†
(
x
))
deg(
u
†
(
x
))
=
g
+
≤
g
). But if, for example, deg(
u
(
x
))
=
=
g
then we have
2
div(
u
†
,y
v
†
)
2
∞
+
)
∞
−
)
div(
u,y
−
v
)
∩ A
−
D
∞
≡
−
∩ A
+
(
−
(
−
D
∞
(10.17)
∞
−
)
and so the operation corresponds to addition of
D
with the degree zero divisor (
−
∞
+
). This justifies the name “composition at infinity”. To add (
∞
+
)
−
∞
−
) one should
(
(
use
G
−
(
x
) instead of
G
+
(
x
) in Lemma
10.4.6
.
Exercise 10.4.15
Prove Lemma
10.4.14
.
We can finally put everything together and obtain the main result about reduced divisors
on hyperelliptic curves with split model.
Theorem 10.4.16
Let C be a hyperelliptic curve over
of genus g with split model. Then
every divisor class contains a reduced divisor as in Definition
10.4.9
.
k
Proof
We have shown the existence of a divisor in the divisor class with semi-reduced affine
part, and hence of the form (
u
(
x
)
,v
(
x
)
,n
) with
n
. Cantor reduction and composition
and reduction at infinity show that we can assume deg(
u
(
x
))
∈ Z
≤
g
. Finally, to show that one
