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

The problem is now reduced to solving congruences of the form W ( x ) 2 ≡

a ) c )with W ( a )= b ,where b 2 = f ( a ). The solutions W will be
the desired polynomials V j .If b =0,then f ( a ) = 0 and, by Proposition 13.2,
we know that c =1,sowecantake W ( x ) = 0. This yields

f ( x )(mod( x −

W ( x ) 2 =0 2 = f ( a ) ≡ f ( x )(mod x − a ))

since f ( x ) ≡ f ( a )(mod( x − a )) for any polynomial f ( x ). Suppose now that
b =0. Let W 1 ( x )= b .Then W 1 ( x ) 2 = b 2 = f ( a ), so W 1 ( x ) 2 − f ( x )is0at

x = a , hence is 0 mod x − a . Now suppose that 1 ≤ n<c and that we have

found W n ( x ) such that W n ( x ) 2 a ) n )and W n ( a )= b .Write ≡ f ( x )(mod( x −

W n +1 ( x )= W n ( x )+ k ( x − a ) n

for some constant k to be determined. Then

W n +1 ( x ) 2 W n ( x ) 2 a ) n W n ( x )(mod x a ) n +1 ) .

− f ( x ) ≡ − f ( x )+2 k ( x − −

Since W n ( x ) 2 − f ( x ) is a multiple of ( x − a ) n , we can form the polynomial

P ( x )= W n ( x ) 2 − f ( x ) / ( x−a ) n .Let k = −P ( a ) / 2. Then W n +1 ( x ) 2 −f ( x )

is a multiple of ( x − a ) n +1 . Continuing in this way, we obtain a function
W ( x )= W c ( x ) that has the desired properties. ( Remark: This method is
actually the same as Newton's method for finding numerical approximations
to solutions of equations.)
As mentioned previously, we combine the functions V j ( x ) via the Chinese
remainder theorem to obtain V ( x ). Now that we have a function V ( x )with
V ( x ) 2 f ( x ) divisible by U ( x ), we can reduce V mod U to get a new function

V with deg V ( x ) < deg U ( x ). We have therefore found the desired pair ( U, V ).
Finally, we need to show that V ( x ) is uniquely determined by D . Suppose
V 1 ( x )and V 2 ( x ) are two such polynomials. The functions y − V i ( x )vanish
to order at least c j at P j , and therefore their difference V 2 ( x ) − V 1 ( x )must

−

also vanish to this order. Therefore, V 2 ( x ) − V 1 ( x ) has at least j c j =
deg U ( x ) zeros, counting multiplicity. But deg( V 2 ( x ) − V 1 ( x )) < deg U ( x ), so
V 1 ( x ) − V 2 ( x ) must be identically 0. This completes the proof.

The next result shows that the reduced divisors represent all divisor classes
of degree 0.

PROPOSITION 13.6
Let D be a divisor of degree 0 on C .Thereexistsauniqu e redu ced divisor
D 1 su ch that D − D 1 isaprincipal divisor.

PROOF Recall the Riemann-Roch theorem (Theorem 11.15): For any

divisor D ,

( D ) − ( K−D )=deg( D ) − g +1 .