Hyperelliptic Curves - Elliptic Curves: Number Theory and Cryptography - page 417

8. O utput ( U, V ) .

Thepair ( U, V ) isthe M um ford representation ofthe divisor class of D 1 + D 2 .

PROOF By modifying D 1 and D 2 by principal divisors, we may assume
that D i = gcd(div( U i ) , div( y−V i )), for i =1 , 2. The algorithm consists of two
parts. The first part, which is steps (1), (2), and (3), constructs a pair ( U, V ).
It essentially corresponds to D 1 + D 2 , but terms of the form [ P ]+[ w ( P )] − 2[ ∞ ]
need to be removed. This is the role of the polynomial d ( x ). The second part,
steps (4) through (7), lowers the degree of U ( x )sothatdeg U ( x ) ≤ g .
First, we need to check that V 0 in step (2) is a polynomial. Since U 1 ,U 2
are multiples of d , it remains to show that V 1 V 2 + f is a multiple of d .But
V 1 V 2 + f = V 1 ( V 1 + V 2 )+ f V 1 ≡ − 0(mod d ) ,

V 1

since V 1 + V 2 is a multiple of d and since f − is a multiple of U 1 , hence a

multiple of d . Therefore, V 0 is a polynomial.
We now show that gcd ( U ( x ) ,y V 0 ( x )) equals the semi-reduction of D 1 +

D 2 ,namely, D 1 + D 2 with any terms of the form [ P ]+[ w ( P )] − 2[ ∞ ] removed.
To do so, we need to explain the definition of V 0 ( x ). Consider a point P =
( a, b ) and let the coecient of [ P ] − [ ∞ ]in D i be r i ≥ 0. The functions U i
and y − V i vanish to order at least r i at P . Therefore, the products

−

U 1 U 2 , ( y − V 1 ) U 2 , ( y − V 2 ) U 1 , ( y − V 1 )( y − V 2 )= f + V 1 V 2 − ( V 1 + V 2 ) y

vanish to order at least r 1 + r 2 at P . The coe cients of y in the last three
functions are U 2 ,U 1 , ( V 1 + V 2 ), and the polynomial d is the gcd of these.

The linear combination for d in step (1) implies that

−

( y − V 2 ) U 1 h 1 +( y − V 1 ) U 2 h 2 +(( V 1 + V 2 ) y − f − V 1 V 2 ) h 3

= dy − dV 0 .

Therefore, ( y V 0 ) d vanishes to order at least r 1 + r 2 at P .

We now need to consider in detail what happens at each point P =( a, b ).
It is convenient to work with both P and w ( P )=( a,

−

− b ) at the same time.

For simplicity, let ( U, y − V ) denote the divisor gcd(div( U ) , div( y − V )).

Write

( U 1 ,y− V 1 )= D 1 = r 1 ([ P ] − [ ∞ ]) + s 1 ([ w ( P )] − [ ∞ ]) + ···
( U 2 ,y− V 2 )= D 2 = r 2 ([ P ] − [ ∞ ]) + s 2 ([ w ( P )] − [ ∞ ]) + ··· .

Since D 1 and D 2 are semi-reduced, either r 1 =0or s 1 = 0, and either r 2 =0
or s 2 =0.
We need to show that the coecients of [ P ] − [ ∞ ]andof[ w ( P )] − [ ∞ ]in
the semi-reduction of D 1 + D 2 match those in ( U, y − V 0 ), where U is the
polynomial obtained in step (3). There are several cases to consider.