Cryptography Reference
In-Depth Information
section, we describe an algorithm that produces the Mumford representation
for the sum of two divisor classes of degree 0.
] is the only point with
a negative coe
cient, then it is easy to find a semi-reduced divisor in the
same divisor class; namely, we remove divisors of suitable polynomials in
x
. However, the proof of Proposition 13.6 does not immediately give an
algorithm for changing the semi-reduced divisor to the reduced divisor in the
same divisor class. Nevertheless, if we work with the pair (
U, V
) associated to
the semi-reduced divisor, there is a straightforward procedure that produces
the pair corresponding to the reduced divisor.
If we start with a divisor of degree 0 where [
∞
THEOREM 13.9 (Reduction Procedure)
Let
(
U, V
)
be a pairrepresenting a sem i-redu ced divisor
D
of degree 0. D o
the follow ing:
1. Let
U
=(
f
V
2
)
/U
.
−
2. Let
V
U
)
with
deg(
V
)
<
deg
U
.
≡−
V
(mod
U
and
V
=
V
.
3. Let
U
=
4. M ultiply
U
by a constant tomake
U
monic.
5. If
deg(
U
)
>g
,go backtostep 1. O therw ise, con tinue.
6. O utput
(
U, V
)
.
Thereduction procedure term inates, and the output isthe pairrepresenting
the reduced divisor inthe divisor class of
D
.
PROOF
The divisor of
U
(
x
)is
D
+
w
(
D
). The divisor of
y − V
(
x
)is
D
+
E
,where
E
has the form
j
e
j
([
Q
j
]
−
[
∞
]) for some points
Q
j
and some
coecients
e
j
≥
0. The divisor of
y
+
V
(
x
)is
w
(
D
+
E
). Since
U U
=
f − V
2
=(
y
+
V
)(
y − V
)
,
we have
D
+
w
(
D
) + div(
U
)=div(
U
)+div(
U
)=
D
+
E
+
w
(
D
+
E
)
.
Therefore,
div(
U
)=
E
+
w
(
E
)
.
(13.3)
Since div(
y
+
V
)=
w
(
D
)+
w
(
E
),
gcd
div(
U
)
,
div(
y
+
V
)
=
w
(
E
)
(13.4)
Search WWH ::
Custom Search