Cryptography Reference
In-Depth Information
Example 10.3.4
Let
P
1
=
(
x
1
,y
1
) and
P
2
=
(
x
2
,y
2
) be points on a hyperelliptic curve
C
such that
x
1
=
x
2
.Let
D
=−
(
P
1
)
+
2(
P
2
)
+
(
ι
(
P
2
)). Then
D
is not semi-reduced. One has
D
+
div(
x
−
x
1
)
=
D
+
(
P
1
)
+
(
ι
(
P
1
))
=
(
ι
(
P
1
))
+
2(
P
2
)
+
(
ι
(
P
2
))
,
−
which is still not semi-reduced. Subtracting div(
x
x
2
) from the above gives
D
+
div((
x
−
x
1
)
/
(
x
−
x
2
))
=
(
ι
(
P
1
))
+
(
P
2
)
,
which is semi-reduced.
10.3.1 Mumford representation of semi-reduced divisors
Mumford [
399
] introduced
1
a representation for semi-reduced divisors. The condition that
the divisor is semi-reduced is crucial: if points
P
(
x
P
,y
P
) and (
x
P
,y
P
) with
y
P
=
y
P
=
both appear in the support of the divisor then no polynomial
v
(
x
) can satisfy both
v
(
x
P
)
=
y
P
.
y
P
and
v
(
x
P
)
=
=
l
i
=
1
e
i
(
x
i
,y
i
)
be a non-zero semi-reduced divisor on a hyperel-
Lemma 10.3.5
Let D
liptic curve C
:
y
2
+
H
(
x
)
y
=
F
(
x
)
(hence, D is affine and effective). Define
l
x
i
)
e
i
u
(
x
)
=
(
x
−
∈ k
[
x
]
.
i
=
1
Then there is a unique polynomial v
(
x
)
∈ k
[
x
]
such that
deg(
v
(
x
))
<
deg(
u
(
x
))
, v
(
x
i
)
=
y
i
for all
1
≤
i
≤
l, and
v
(
x
)
2
+
H
(
x
)
v
(
x
)
−
F
(
x
)
≡
0(mod
u
(
x
))
.
(10.5)
In particular, v
(
x
)
=
0
if and only if u
(
x
)
|
F
(
x
)
.
=
Proof
Since
D
is semi-reduced there is no conflict in satisfying the condition
v
(
x
i
)
y
i
.
If all
e
i
=
1 then the result is trivial. For each
i
such that
e
i
>
1 write
v
(
x
)
=
y
i
+
(
x
−
x
i
)
W
(
x
) for some polynomial
W
(
x
). We compute
v
(
x
)(mod(
x
−
x
i
)
e
i
) so it satisfies
v
(
x
)
2
x
i
)
e
i
) by Hensel lifting (see Section
2.13
)as
+
H
(
x
)
v
(
x
)
−
F
(
x
)
≡
0(mod(
x
−
follows: if
v
(
x
)
2
x
i
)
j
G
j
(
x
) then set
v
†
(
x
)
+
H
(
x
)
v
(
x
)
−
F
(
x
)
=
(
x
−
=
v
(
x
)
+
w
(
x
−
x
i
)
j
where
w
is an indeterminate and note that
v
†
(
x
)
2
H
(
x
)
v
†
(
x
)
x
i
)
j
(
G
j
(
x
)
x
i
)
j
+
1
)
.
+
−
F
(
x
)
≡
(
x
−
+
2
v
(
x
)
w
+
H
(
x
)
w
)(mod(
x
−
It suffices to find
w
such that this is zero, in other words, solve
G
j
(
x
i
)
+
w
(2
y
i
+
H
(
x
i
))
=
0. Since
D
is semi-reduced, we know 2
y
i
+
H
(
x
i
)
=
0 (since
P
=
ι
(
P
) implies
n
P
=
1).
The result follows by the Chinese remainder theorem.
1
Mumford remarks on pages 3-17 of [
399
] that a special case of these polynomials arises in the work of Jacobi. However, Jacobi
only gives a representation for semi-reduced divisors with
g
points in their support, rather than arbitrary semi-reduced divisors.