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

13.6 Let ( U, V ) be the pair corresponding to a semi-reduced divisor.

(a) Use Cantor's algorithm to show that ( U, V )+(1 , 0) = ( U, V ).
(b) Use Cantor's algorithm to show that ( U, V )+( U, −V )=(1 , 0).

13.7 Let C be a hyperelliptic curve and let D be a divisor of degree 0.

(a) Show that if 3 D is principal then 2 D is equivalent to w ( D )mod
principal divisors.
(b) Let P = ∞ be a point on C . Show that if the genus of C is at least
2then3([ P ] − [ ∞ ]) is not principal. ( Hint: Use the uniqueness
part of Proposition 13.6.)
This shows that the image of C in its Jacobian intersects the 3-
torsion on the Jacobian trivially.

13.8 Let E be an elliptic curve defined over a field K and let ( U, V )beapair
of polynomials with coe cients in K corresponding to a semi-reduced
divisor class.

(a) Show that the reduction algorithm applied to ( U, V ) yields either
the pair (1 , 0) or a pair ( x − a, b ), with a, b ∈ K .
(b) Show that (1 , 0) corresponds to the divisor 0, and ( x − a, b ) corre-

sponds to the divisor [( a, b )] − [ ∞ ].

13.9 Let E be an elliptic curve, regarded as a hyperelliptic curve. Show that
Cantor's algorithm corresponds to addition of points on E by showing
that ( x−a 1 ,b 1 )+( x−a 2 ,b 2 ) yields ( x−a 3 ,b 3 ), where ( a 1 ,b 1 )+( a 2 ,b 2 )=
( a 3 ,b 3 ).

13.10 Let f 1 ( T ) ,...,f n ( T ) be polynomials (with coe cients in some field K )
that are pairwise without common factors, and let a 1 ( T ) ,...,a n ( T )be
arbitrary polynomials with coe cients in K .Foreach i ,let F i ( T )=

j = i f j .Sincegcd( f i ,F i ) = 1, there exists g i ( T )with g i ( T ) F i ( T )

≡ 1

(mod f i ) (this can be proved using the Euclidean algorithm). Let

A ( T )= a 1 ( T ) g 1 ( T ) F 1 ( T )+ ··· + a n ( T ) g n ( T ) F n ( T ) .

Show that A a i (mod f i ) for all i . Remark: This is the Chinese

Remainder Theorem for polynomials.)

≡

13.11 Let q be a power of an odd prime. Let U ( T ) be an irreducible polynomial
in F q [ T ]ofdegree n .Then F q [ T ] / ( U ( T )) is a field with q n elements.
Let f ( T ) ∈ F q [ T ]with f ( T ) ≡ 0(mod U ( T )). Show that there exists
V ( T ) f (mod U ) if and only if f ( q n − 1) / 2 F q [ T ] such that V 2 1

(mod U ). ( Hint: The multiplicative group of a finite field is cyclic.)
( Remark. There are algorithms for finding square roots in finite fields.
See [25].)

∈ ≡ ≡