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

all) divisors D in the divisor class. These correspond to the points on the
Jacobian variety that are defined over F q . We denote this set by J ( F q ).
Suppose D is a divisor of degree 0 such that φ ( D ) is in the same divisor class
as D . The divisor class of D contains a unique reduced divisor R , and the
divisor class of φ ( D )contains φ ( R ) (proof: D φ ( R )=

div( φ ( F ))), and φ ( R ) is also reduced. The uniqueness implies that R = φ ( R ).
Therefore, the divisor class contains a divisor fixed by φ . The reduced divisor
R corresponds to a unique pair ( U, V ) of polynomials. The divisor φ ( R )
corresponds to the pair ( U φ ,V φ ), where U φ denotes the polynomial obtained
by applying φ to the coecients of U .Since φ ( R )= R ,wehave U φ = U
and V φ = V , because the pair corresponding to a divisor is unique. It follows
that a divisor class that is mapped to itself by φ corresponds to a unique
pair ( U, V ) of polynomials, with U, V ∈ F q [ x ] (= the set of polynomials with
coe cients in F q ). Conversely, if U, V ∈ F q [ x ], then gcd (div( U ) , div( y − V ))
is fixed by φ , hence yields a divisor class fixed by φ . Wehaveprovedthe
following.

− R =div( F ), so φ ( D ) −

PROPOSITION 13.11
Thereisaone-to-one correspondence between J ( F q ) and pairs ( U, V ) ofpoly-
nom ialswith coe cientsin F q satisfying

1. U ismonic.

2. deg V< deg U

≤ g .

3. V 2

− f ( x ) isamultipleof U .

Since there are only finitely many polynomials U ∈ F q [ x ]ofdegreeatmost
g , there are only finitely many divisor classes of degree 0 that are defined over
F q . In other words, J ( F q ) is finite. It is easy to see that it is closed under
addition, so it forms a group. Alternatively, Cantor's algorithm clearly takes
pairs of polynomials defined over F q to pairs defined over F q .Infact,we
could ignore the geometry completely and consider a group whose elements
are suitable pairs of polynomials and whose law of composition is given by
Cantor's algorithm. This defines a group (although the associativity might
be di cult to prove without the geometric interpretation).

Example 13.2
Let's consider the case where deg U =1. Then U = x − a for some a ,and
V = b for some b ∈ F q .Also, f ( x ) ≡ f ( a )(mod x − a ), so b 2 = V 2

≡ f ( a ),
hence b 2 = f ( a ). This means that ( a, b ) is a point on the curve. The divisor
class for ( U, V ) is defined over F q if and only if the polynomials x − a and
b have coe cients in F q , which happens if and only if the point ( a, b )has
coordinates in F q .