Hyperelliptic curves - Mathematics of Public Key Cryptography - page 192

has the solution

1
2 y P +

s 3 ( x )( H ( x P )

s 3 ( x ) = and s 1 ( x ) =− + ( x − x P ) G ( x ))

H ( x P )

H ( x P )( x x P ) 2 . Furthermore, note that

where G ( x ) = ( H ( x ) − H ( x P ) − − x P )) / ( x −

s 3 ( x )( y P + x P ) 2 ) . v ( x ) ≡ s 1 ( x )( x − x P ) y P + F ( x )) (mod ( x −

The core of Cantor's addition and semi-reduction algorithm is to decide which functions

( x x P ) are needed (and to which powers) to obtain a semi-reduced divisor equivalent to

D 1 +

−

D 2 .The crucial observation is that if P is in the support of D 1 and ι ( P )isinthe
support of D 2 then ( x

− x P ) | u 1 ( x ) , ( x − x P ) | u 2 ( x ) and v 1 ( x P ) =− v 2 ( x P ) − H ( x P ) and

so ( x H ( x )). The exact formulae are given in Theorem 10.3.14 .

The process is called Cantor's addition algorithm or Cantor's composition algorithm .

− x P ) | ( v 1 ( x ) + v 2 ( x ) +

Theorem 10.3.14 Let ( u 1 ( x ) ,v 1 ( x )) and ( u 2 ( x ) ,v 2 ( x )) be Mumford representations of two
semi-reduced divisorsD 1 andD 2 . Let s ( x )

= gcd( u 1 ( x ) ,u 2 ( x ) ,v 1 ( x ) + v 2 ( x ) + H ( x )) and

let s 1 ( x ) ,s 2 ( x ) ,s 3 ( x ) ∈ k [ x ] be such that

s ( x ) = s 1 ( x ) u 1 ( x ) + s 2 ( x ) u 2 ( x ) + s 3 ( x )( v 1 ( x ) + v 2 ( x ) + H ( x )) .

u 1 ( x ) u 2 ( x ) /s ( x ) 2 and Define u 3 ( x ) =

v 3 ( x ) = ( s 1 ( x ) u 1 ( x ) v 2 ( x ) + s 2 ( x ) u 2 ( x ) v 1 ( x ) + s 3 ( x )( v 1 ( x ) v 2 ( x ) + F ( x ))) /s ( x ) . (10.6)

Then u 3 ( x ) ,v 3 ( x ) ∈ k [ x ] and the Mumford representation of the semi-reduced divisor D

equivalent to D 1 + D 2 is ( u 3 ( x ) ,v 3 ( x )) .

2

Proof Let D = D 1 + D 2 − div( s ( x )) ∩ A so that D is equivalent to D 1 + D 2 .Bythe

“crucial observation” above, s ( x ) has a root x P for some point P ( x P ,y P ) on the curve if

and only if P and ι ( P ) lie in the supports of D 1 and D 2 . Taking multiplicities into account,
it follows that D is semi-reduced.
It is immediate that s ( x ) 2

=

[ x ]. It is also immediate that
u 3 ( x ) is the correct first component of the Mumford representation of D .
To show v 3 ( x )

| u 1 ( x ) u 2 ( x ) and so u 3 ( x ) ∈ k

∈ k [ x ] re-write v 3 ( x )as

v 2 ( s − s 2 u 2 − s 3 ( v 1 + v 2 + H )) + s 2 u 2 v 1 + s 3 ( v 1 v 2 + F )

v 3 = (10.7)

s

v 2 ) /s. = v 2 + s 2 ( v 1 − v 2 )( u 2 /s ) + s 3 ( F − v 2 H − (10.8)

v 2 ) the result follows.

Since s ( x ) | u 2 ( x ) and u 2 ( x ) | ( F − v 2 H −

We now need the equation

( v 1 + v 2 + H )( v 3 − y ) ≡ ( y − v 1 )( y − v 2 )(mod u 3 ) . (10.9)

This is proved by inserting the definition of v 3 from equation ( 10.6 ) to get

( s 1 u 1 ( v 2 + s 2 u 2 ( v 1 + ( v 1 + v 2 + H )( v 3 − y ) ≡− ( v 1 + v 2 + H ) y + Hv 2 − F ) + Hv 1 − F )

+ ( v 1 v 2 + F )( s 1 u 1 + s 2 u 2 + s 3 ( v 1 + v 2 + H )) /s (mod u 3 ( x )) .