Cryptography Reference
In-Depth Information
Exercise 10.3.19
Show that the straight lines
l
(
x,y
) and
v
(
x
) in the elliptic curve addition
law (Definition
7.9.1
) correspond to the polynomials
y
v
(
x
) and
u
†
(
x
) (beware of the
−
double meaning of
v
(
x
) here) in a Cantor reduction step.
Lemma 10.3.20
Let C
:
y
2
F
(
x
)
and let
(
u
(
x
)
,v
(
x
))
be the Mumford rep-
resentation of a semi-reduced divisor D. Write d
H
=
+
H
(
x
)
y
=
deg(
H
(
x
))
,d
F
=
deg(
F
(
x
))
,d
u
=
deg(
u
(
x
))
and d
v
=
=
{
}
. Let
(
u
†
(
x
)
,v
†
(
x
))
be the poly-
deg(
v
(
x
))
. Let d
max
d
H
,
d
F
/
2
nomials arising from a Cantor reduction step.
d then
deg(
u
†
(
x
))
1. If d
v
≥
≤
d
u
−
2
.
d>d
v
then
deg(
u
†
(
x
))
2. If d
F
≤
2
d
−
1
and d
u
≥
≤
d
−
1
(this holds even if d
H
=
d).
2
d and d
u
>d>d
v
then
deg(
u
†
(
x
))
3. If d
F
=
≤
d
−
1
.
Proof
Note that
d
u
>d
v
.If
d
v
≥
d
then
deg(
v
(
x
)
2
+
H
(
x
)
v
(
x
)
−
F
(
x
))
≤
max
{
2
d
v
,d
H
+
d
v
,d
F
}
≤
max
{
2(
d
u
−
1)
,d
+
(
d
u
−
1)
,
2
d
}
.
Hence, deg(
u
†
(
x
))
deg(
v
2
=
+
Hv
−
F
)
−
d
u
≤
max
{
d
u
−
2
,d
−
1
,
2
d
−
d
u
}=
d
u
−
2.
d>d
v
then, by a similar argument, deg(
u
†
(
x
))
If
d
F
≤
2
d
−
1 and
d
u
≥
≤
2
d
−
2
d
and
d
u
>d>d
v
then deg(
v
2
1
−
d
u
≤
d
−
1. Finally, if
d
F
=
+
Hv
+
F
)
=
2
d
and
deg(
u
†
)
=
−
2
d
d
u
<d
.
Theorem 10.3.21
Suppose C
:
y
2
+
H
(
x
)
y
=
F
(
x
)
is a hyperelliptic curve of genus g
with
deg(
F
(
x
))
1
. Then every semi-reduced divisor is equivalent to a semi-reduced
divisor of degree at most g.
≤
2
g
+
Proof
Perform Cantor reduction steps repeatedly. By Lemma
10.3.20
the desired condition
will eventually hold.
Theorem
10.3.21
is an “explicit Riemann-Roch theorem” for hyperelliptic curves with
a single point at infinity (also for hyperelliptic curves
y
2
+
H
(
x
)
y
=
F
(
x
) with two points
at infinity but deg(
F
(
x
))
1) as it shows that every divisor class contains a represen-
tative as an affine effective divisor of degree at most
g
. The general result is completed in
Lemma
10.4.6
below.
≤
2
g
+
Definition 10.3.22
Let
C
:
y
2
+
=
F
(
x
) be a hyperelliptic curve of genus
g
.A
semi-reduced divisor on
C
is
reduced
if its degree is at most
g
.
H
(
x
)
y
Let
C
:
y
2
Exercise
10.3.23
+
H
(
x
)
y
=
F
(
x
)
be
a
hyperelliptic
curve
with
d
=
max
.Let(
u
(
x
)
,v
(
x
)) be the Mumford representation of a divisor
with deg(
v
(
x
))
<
deg(
u
(
x
))
<d
. Show that if deg(
F
(
x
))
{
deg(
H
)
,
deg(
F
)
/
2
}
1 and one performs a
Cantor reduction step on (
u
(
x
)
,v
(
x
)) then the resulting polynomials (
u
†
(
x
)
,v
†
(
x
)) are such
that deg(
u
†
(
x
))
≥
2
d
−
≥
d
.
2
d
then Lemma
10.3.20
is not sufficient to prove an analogue of
Theorem
10.3.21
. However, one can at least reduce to a divisor of degree
d
When deg(
F
)
=
=
g
+
1. It
