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

(as remarked earlier, a divisor of the form div( y + V ) is semi-reduced, so it
cannot contain contributions from both E and w ( E )). But

D − div( y − V )= −E = w ( E ) − div( U ) ,

so w ( E ) is in the same divisor class as D . We claim that ( U, V ) represents
w ( E ).

U equals e j , the number of summands

By (13.3), the degree of

in E .Since V 2 f (mod U ), Theorem 13.5 implies that ( U, V )

represents a divisor. By (13.4), it represents w ( E ).
Finally, suppose deg( U ) ≥ g +1. Then deg( f ) < 2deg( U ) and deg( V 2 ) <
2deg( U ), so deg( U )+deg( U )=deg( f −V 2 ) < 2deg( U ). Therefore, deg( U ) <
deg( U ). This means that the degree decreases at every iteration of steps (1)
through (4) until we obtain a polynomial of degree at most g .Atthispoint,
the corresponding divisor is reduced and we are done.

V ) 2 ≡ ( − ≡

13.3 Cantor's Algorithm

Although very useful from a theoretical point of view, the description of
the points of the Jacobian J in terms of divisor classes of degree 0 is not very
useful from a computational point of view. On the other hand, the Mumford
representation gives a very concrete representation of points of J .Inth s
section, we present an algorithm due to David Cantor [22] for adding divisor
classes that are given by their Mumford representations. The algorithm has
its origins in Gauss's theory of composition of quadratic forms.

THEOREM 13.10 (Cantor's algorithm)
Let D 1 and D 2 be divisors of degree 0, w hose classes correspon d topa rs
( U 1 ,V 1 ) and ( U 2 ,V 2 ) ,asin T heorem 13.7.

1. Let d =gcd( U 1 ,U 2 ,V 1 + V 2 ) .F nd polynom ials h 1 ,h 2 ,h 3 su ch that
d = U 1 h 1 + U 2 h 2 +( V 1 + V 2 ) h 3 .

2. Let V 0 =( U 1 V 2 h 1 + U 2 V 1 h 2 +( V 1 V 2 + f ) h 3 ) /d .

3. Let U = U 1 U 2 /d 2 and V ≡ V 0 (mod U ) with deg V< deg U .

4. Let U =( f

V U ) ,with deg( V ) < deg U .

V 2 ) /U and − ≡− V (mod

U and V = V .

5. Let U =

6. M ultiply U by a constant tomake U monic.

7. If deg( U ) >g ,go backtostep 4. O therw ise, con tinue.