Next: 9.2 Closed points
Up: 9 Hyperelliptic Cryptosystems
Previous: 9 Hyperelliptic Cryptosystems
Loosely speaking, hyperelliptic curves represent the solutions of the
equations of the form
y^{2} + a(x)y + b(x) = 0
where a and b are polynomials in x. To put this in the language
of schemes developed earlier, we first restrict our attention to
schemes over
Spec() where
is a finite field called the ground field. Next we consider the d  tuple Veronese embedding of
^{1} in
^{d}; also known as the ``rational normal curve of
degree d''; this is given as the locus of
(1 : x : x^{2} : ^{ ... } : x^{d}) as
(1 : x) varies over
^{1}. Alternatively, it is described by the
system of equations
X_{p}X_{q} = X_{r}X_{s} for all p, q, r, s such
that p + q = r + s. Let us consider
^{d + 1} with
(X_{0} : ^{ ... } : X_{d} : Y)
as its coordinates so that
^{d} is obtained by projecting from
the point (vertex)
v = (0 : ^{ ... } : 0 : 1). Let S_{d} denote the ``cone''
over the rational normal curve of degree d; it is the subvariety of
^{d} defined by the same set of equations as above (in other words
the variable Y is ``free''). Now suppose that
a(x) = a_{i}x^{i}
is a polynomial of degree at most d and
b(x) = b_{i}x^{i} is a
polynomial of degree at most 2d. We consider the linear forms
A(X) 
= 
a_{i}X_{i} 

B(X) 
= 
b_{i}X_{i} 

C(X) 
= 
b_{d + i}X_{i} 

and the quadratic equation
Y^{2} + A(X)Y + B(X)X_{0} + C(X)X_{d} = 0. The addition
of this equation to the equations for S defines a subvariety T of
S. It is clear that the vertex v does not lie on T so that
projection gives a morphism on T which lands in the rational normal
curve of degree d. Thus, we have a morphism
T^{1}. There is
an involution on
^{d + 1} which fixes the X's and sends Y to
A(X)  Y. Clearly this involution sends T to itself and
pairs of points that are involutes of each other are sent to the same
point in
^{1}. The variety T is called a hyperelliptic curve,
the involution is called the hyperelliptic involution and the morphism
T^{1} is called the canonical morphism.
Now it is clear that a solution (x, y) of the equation
y^{2} + a(X)y + b(x) = 0 gives rise to the solution
(1 : x : ^{ ... } : x^{d} : y) of
the above system. Conversely, if we have a solution
(X_{0} : X_{1} : ^{ ... } : X_{d} : Y) of the system of equations with X_{0} a unit,
then we can put
(x, y) = (X_{1}/X_{0}, Y/X_{0}) to obtain a solution of the
two variable equation. Similarly, if
(X_{0} : ^{ ... } : X_{d} : Y) is a
solution of the system of equations and X_{d} is a unit then consider
the pair
(u, v) = (X_{d  1}/X_{d}, Y/X_{d}); this pair satisfies a two
variable equation
v^{2} + a'(u)v + b'(u) = 0, where
a'(u) = u^{d}a(1/u) and
b'(u) = u^{2d}b(1/u). One sees from the above system that either X_{0}
or X_{d} must be a unit so we have covered all cases. The Jacobian
criterion for regularity can be used to show that the curve defined by
y^{2} + a(x)y + b(x) = 0 is regular when either,
 the discriminant
a(x)^{2}  4b(x) has distinct roots, or
 the field
has characteristic 2, a(x) has distinct roots
and for each point (x_{0}, y_{0}) where x_{0} is a root of a(x), the
polynomial
b(x)  b(x_{0})  y_{0}a(x) vanishes with multiplicity one at
0.
To apply this to the equation
v^{2} + a'(u)v + b'(u) = 0, we note that
a'(u)^{2}  4b'(u) = u^{2d}(a(1/u)^{2}  4b(1/u))
Thus, if
a(x)^{2}  4b(x) has distinct roots, then the only multiple
root of
a'(u)^{2}  4(b'(u) can be at u = 0; moreover, this happens only
if a(x) has degree less than d  1 and b(x) has degree less than
2d  1. From now one we will assume the T is regular or
nonsingular; in fact we will assume that b(x) has degree equal to 2d  1. The point
(0 : ^{ ... } : 0 : 1 : 0) is a point on the
curve T is called the ``point at infinity'' and denoted .
The number g = d  1 is called the genus of the hyperelliptic curve. The
points on T where
a(x)^{2}  4b(x) vanishes and the point at infinity
are called the Weierstrass points of the hyperelliptic curve;
these are precisely the fixed points of the Weierstrass involution.
Next: 9.2 Closed points
Up: 9 Hyperelliptic Cryptosystems
Previous: 9 Hyperelliptic Cryptosystems
Kapil Hari Paranjape
20021020