Hyperelliptic curves - Mathematics of Public Key Cryptography - page 201

2 . Let m

div( s ( x )) ∩ A = g/ 2 when g is even and m = ( g + 1) / 2 otherwise. Then

div( u 1 ,v 1 ,n 1 ) + div( u 2 ,v 2 ,n 2 ) ≡ div( u 3 ,v 3 ,n 1 + n 2 + deg( s ) − m ) . (10.14)

Proof We will show that

div( u 1 ,v 1 ,n 1 ) + div( u 2 ,v 2 ,n 2 ) = div( u 3 ,v 3 ,n 1 + n 2 + deg( s ) − m ) + div( s ( x )) .

The left-hand side is

∞ + ) D 1 + D 2 + ( n 1 + n 2 − m )( + (3 m − deg( u 1 ) − deg( u 2 )

∞ − )

−

n 1 −

−

n 2 )( D ∞ . (10.15)

2

∞ + Replacing D 1 + D 2 by D 3 + div( s ( x )) ∩ A has no effect on the coefficients of

∞ − , but since we actually need div( s ( x )) on the whole of C we have D 1 + or D 2 =

∞ + ) ∞ − )).

D 3 + div( s ( x )) + deg( s ( x ))(( + ( Writing div( u 3 ,v 3 ,n 3 ) = div( u 3 ,y − v 3 ) ∩

2

∞ + ) ∞ − )

A + n 3 ( + ( g − deg( u 3 ) − n 3 )( − D ∞ gives n 3 = n 1 + n 2 + deg( s ( x )) − m as

required.
Note that deg( u 3 ) ∞ − in equa- + deg( s ) = deg( u 1 ) + deg( u 2 ), so the coefficient of

tion ( 10.15 ) is also correct (as it must be).

We now discuss reduction of divisors on a hyperelliptic curve with a split model. We
first consider the basic Cantor reduction step. There are two relevant cases for split models
(namely, the first and third cases in Lemma 10.3.20 ) that we handle as Lemma 10.4.11 and
Exercise 10.4.12 .

Lemma 10.4.11 LetC : y 2 + H ( x ) y = F ( x ) where deg( F ( x )) = 2 d = 2 g + 2 be a hyper-

elliptic curve over of genus g with split model. Let div( u ( x ) ,v ( x ) ,n ) be a degree zero

divisor as in Definition 10.4.9 . Let ( u † ( x ) ,v † ( x )) be the polynomials arising from a Cantor
reduction step (i.e., u † ( x ) and v † ( x ) are given by equation ( 10.10 )). If deg( v ( x ))

k

≥ d =

1 then set n † = deg( u † ( x )) deg( u † ( x ))) / 2 and if g + n + deg( v ( x )) − = n + (deg( u ( x )) −

1 < deg( u ( x )) then set n † = deg( u † ( x )) . Then deg( v ( x )) <g + n + g + 1 −

div( u † ,v † ,n † ) div( u † ( x ))

= + − −

div( u,v,n ) div( y v ( x )) (10.16)

div( u † ,v † ,n † ) .

and div( u,v,n ) ≡

deg( u † ( x )) Proof If deg( v ( x )) ≥ d then deg( u ( x )) + = 2deg( v ( x )) and v ∞ + ( y − v ( x )) =

v ∞ − ( y − v ( x )) =− deg( v ( x )). For equation ( 10.16 ) to be satisfied we require

n † + v ∞ + ( u † ( x )) n = v ∞ + ( y − v ( x )) −

and the formula for n † follows (the coefficients of ∞ − must also be correct, as the divisors

all have degree zero).
In the second case of reduction, we have deg( v ( x )) <d< deg( u ( x )) and hence
deg( u ( x )) deg( u † ( x )) + = 2 d and v ∞ + ( y − v ( x )) = v ∞ − ( y − v ( x )) =− d . The formula for

n † follows as in the first case.