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