Imaginary hyperelliptic curve
A hyperelliptic curve is a particular kind of algebraic curve. There exist hyperelliptic curves of every genus . If the genus of a hyperelliptic curve equals 1, we simply call the curve an elliptic curve. Hence we can see hyperelliptic curves as generalizations of elliptic curves. There is a well-known group structure on the set of points lying on an elliptic curve over some field , which we can describe geometrically with chords and tangents. Generalizing this group structure to the hyperelliptic case is not straightforward. We cannot define the same group law on the set of points lying on a hyperelliptic curve, instead a group structure can be defined on the so-called Jacobian of a hyperelliptic curve. The computations differ depending on the number of points at infinity. This article is about imaginary hyperelliptic curves, these are hyperelliptic curves with exactly 1 point at infinity. Real hyperelliptic curves have two points at infinity.
Formal definition
Hyperelliptic curves can be defined over fields of any characteristic. Hence we consider an arbitrary field and its algebraic closure . An (imaginary) hyperelliptic curve of genus over is given by an equation of the form
where is a polynomial of degree not larger than and is a monic polynomial of degree . Furthermore we require the curve to have no singular points. In our setting, this entails that no point satisfies both and the equations and . This definition differs from the definition of a general hyperelliptic curve in the fact that can also have degree in the general case. From now on we drop the adjective imaginary and simply talk about hyperelliptic curves, as is often done in literature. Note that the case corresponds to being a cubic polynomial, agreeing with the definition of an elliptic curve. If we view the curve as lying in the projective plane with coordinates , we see that there is a particular point lying on the curve, namely the point at infinity denoted by . So we could write .
Suppose the point not equal to lies on the curve and consider . As can be simplified to , we see that is also a point on the curve. is called the opposite of and is called a Weierstrass point if , i.e. . Furthermore, the opposite of is simply defined as .
Alternative definition
The definition of a hyperelliptic curve can be slightly simplified if we require that the characteristic of is not equal to 2. To see this we consider the change of variables and , which makes sense if char. Under this change of variables we rewrite to which, in turn, can be rewritten to . As we know that and hence is a monic polynomial of degree . This means that over a field with char every hyperelliptic curve of genus is isomorphic to one given by an equation of the form where is a monic polynomial of degree and the curve has no singular points. Note that for curves of this form it is easy to check whether the non-singularity criterion is met. A point on the curve is singular if and only if and . As and , it must be the case that and thus is a multiple root of . We conclude that the curve has no singular points if and only if has no multiple roots. Even though the definition of a hyperelliptic curve is quite easy when char, we should not forget about fields of characteristic 2 as hyperelliptic curve cryptography makes extensive use of such fields.
Example
As an example consider where over . As has degree 5 and the roots are all distinct, is a curve of genus . Its graph is depicted in Figure 1.
From this picture it is immediately clear that we cannot use the chords and tangents method to define a group law on the set of points of a hyperelliptic curve. The group law on elliptic curves is based on the fact that a straight line through two points lying on an elliptic curve has a unique third intersection point with the curve. Note that this is always true since lies on the curve. From the graph of it is clear that this does not need to hold for an arbitrary hyperelliptic curve. Actually, Bézout's theorem states that a straight line and a hyperelliptic curve of genus 2 intersect in 5 points. So, a straight line through two point lying on does not have a unique third intersection point, it has three other intersection points.
Coordinate ring
The coordinate ring of C over K is defined as
- .
The polynomial is irreducible over , so
is an integral domain.
Proof. If r (x,y) were reducible over , it would factor as (y - u(x)) · (y - v(x)) for some u,v ∈ . But then u(x) · v(x)= f(x) so it has degree 2g + 1, and u(x) + v(x) = h(x) so it has degree smaller than g, which is impossible.
Note that any polynomial function can be written uniquely as
- with , ∈
Norm and degree
The conjugate of a polynomial function G(x,y) = u(x) - v(x)y in is defined to be
- .
The norm of G is the polynomial function . Note that N(G) = u(x)2 + u(x)v(x)h(x) - v(x)2f(x), so N(G) is a polynomial in only one variable.
If G(x,y) = u(x) - v(x) · y, then the degree of G is defined as
- .
Properties:
Function field
The function field K(C) of C over K is the field of fractions of K[C], and the function field of C over is the field of fractions of . The elements of are called rational functions on C. For R such a rational function, and P a finite point on C, R is said to be defined at P if there exist polynomial functions G, H such that R = G/H and H(P) ≠ 0, and then the value of R at P is
- .
For P a point on C that is not finite, i.e. P = , we define R(P) as:
- If then , i.e. R has a zero at O.
- If then is not defined, i.e. R has a pole at O.
- If then is the ratio of the leading coefficients of G and H.
For and ,
- If then R is said to have a zero at P,
- If R is not defined at P then R is said to have a pole at P, and we write .
Order of a polynomial function at a point
For and , the order of G at P is defined as:
- if P = (a,b) is a finite point which is not Weierstrass. Here r is the highest power of (x-a) which divides both u(x) and v(x). Write G(x,y) = (x - a)r(u0(x) - v0(x)y) and if u0(a) - v0(a)b = 0, then s is the highest power of (x - a) which divides N(u0(x) - v0(x)y) = u02 + u0v0h - v02f, otherwise, s = 0.
- if P = (a,b) is a finite Weierstrass point, with r and s as above.
- if P = O.
The divisor and the Jacobian
In order to define the Jacobian, we first need the notion of a divisor. Consider a hyperelliptic curve over some field . Then we define a divisor to be a formal sum of points in , i.e. where and furthermore is a finite set. This means that a divisor is a finite formal sum of scalar multiples of points. Note that there is no simplification of given by a single point (as one might expect from the analogy with elliptic curves). Furthermore we define the degree of as . The set of all divisors of the curve forms an Abelian group where the addition is defined pointwise as follows . It is easy to see that acts as the identity element and that the inverse of equals . The set of all divisors of degree 0 can easily be checked to be a subgroup of .
Proof. Consider the map defined by , note that forms a group under the usual addition. Then and hence is a group homomorphism. Now, is the kernel of this homomorphism and thus it is a subgroup of .
Consider a function , then we can look at the formal sum div. Here ord denotes the order of at . We have that ord if has a pole of order -ord at , ord if is defined and non-zero at and ord if has a zero of order ord at .[1] It can be shown that has only a finite number of zeroes and poles,[2] and thus only finitely many of the ord are non-zero. This implies that div is a divisor. Moreover, as ,[2] it is the case that div is a divisor of degree 0. Such divisors, i.e. divisors coming from some rational function , are called principal divisors and the set of all principal divisors is a subgroup of .
Proof. The identity element comes from a constant function which is non-zero. Suppose are two principal divisors coming from and respectively. Then comes from the function , and thus is a principal divisor, too. We conclude that is closed under addition and inverses, making it into a subgroup.
We can now define the quotient group which is called the Jacobian or the Picard group of . Two divisors are called equivalent if they belong to the same element of , this is the case if and only if is a principal divisor. Consider for example a hyperelliptic curve over a field and a point on . For the rational function has a zero of order at both and and it has a pole of order at . Therefore we find div and we can simplify this to div if is a Weierstrass point.
Example: the Jacobian of an elliptic curve
For elliptic curves the Jacobian turns out to simply be isomorphic to the usual group on the set of points on this curve, this is basically a corollary of the Abel-Jacobi theorem. To see this consider an elliptic curve over a field . The first step is to relate a divisor to every point on the curve. To a point on we associate the divisor , in particular in linked to the identity element . In a straightforward fashion we can now relate an element of to each point by linking to the class of , denoted by . Then the map from the group of points on to the Jacobian of defined by is a group homomorphism. This can be shown by looking at three points on adding up to , i.e. we take with or . We now relate the addition law on the Jacobian to the geometric group law on elliptic curves. Adding and geometrically means drawing a straight line through and , this line intersects the curve in one other point. We then define as the opposite of this point. Hence in the case we have that these three points are collinear, thus there is some linear such that , and satisfy . Now, which is the identity element of as is the divisor on the rational function and thus it is a principal divisor. We conclude that .
The Abel-Jacobi theorem states that a divisor is principal if and only if has degree 0 and under the usual addition law for points on cubic curves. As two divisors are equivalent if and only if is principal, we conclude that and are equivalent if and only if . Now, every nontrivial divisor of degree 0 is equivalent to a divisor of the form , this implies that we have found a way to ascribe a point on to every class . Namely, to we ascribe the point . This maps extends to the neutral element 0 which is maped to . As such the map defined by is the inverse of . So is in fact a group isomorphism, proving that and are isomorphic.
The Jacobian of a hyperelliptic curve
The general hyperelliptic case is a bit more complicated. Consider a hyperelliptic curve of genus over a field . A divisor of is called reduced if it has the form where , for all and for . Note that a reduced divisor always has degree 0, also it is possible that if , but only if is not a Weierstrass point. It can be proven that for each divisor there is a unique reduced divisor such that is equivalent to .[3] Hence every class of the quotient group has precisely one reduced divisor. Instead of looking at we can thus look at the set of all reduced divisors.
Reduced divisors and their Mumford representation
A convenient way to look at reduced divisors is via their Mumford representation. A divisor in this representation consists of a pair of polynomials such that is monic, and . Every non-trivial reduced divisor can be represented by a unique pair of such polynomials. This can be seen by factoring in which can be done as such as is monic. The last condition on and then implies that the point lies on for every . Thus is a divisor and in fact it can be shown to be a reduced divisor. For example the condition ensures that . This gives the 1-1 correspondence between reduced divisors and divisors in Mumford representation. As an example, is the unique reduced divisor belonging to the identity element of . Its Mumford representation is and . Going back and forth between reduced divisors and their Mumford representation is now an easy task. For example consider the hyperelliptic curve of genus 2 over the real numbers. We can find the following points on the curve , and . Then we can define reduced divisors and . The Mumford representation of consists of polynomials and with and we know that the first coordinates of and , i.e. 1 and 3, must be zeroes of . Hence we have . As and it must be the case that and and thus has degree 1. There is exactly one polynomial of degree 1 with these properties, namely . Thus the Mumford representation of is and . In a similar fashion we can find the Mumford representation of , we have and . If a point appears with multiplicity n, the polynomial v needs to satisfy for .
Cantor's algorithm
There is an algorithm which takes two reduced divisors and in their Mumford representation and produces the unique reduced divisor , again in its Mumford representation, such that is equivalent to .[4] As every element of the Jacobian can be represented by the one reduced divisor it contains, the algorithm allows to perform the group operation on these reduced divisors given in their Mumford representation. The algorithm was originally developed by David G. Cantor (not to be confused with Georg Cantor), explaining the name of the algorithm. Cantor only looked at the case , the general case is due to Koblitz. The input is two reduced divisors and in their Mumford representation of the hyperelliptic curve of genus over the field . The algorithm works as follows
- Using the extended Euclidean algorithm compute the polynomials such that and .
- Again with the use of the extended Euclidean algorithm compute the polynomials with and .
- Put , and , which gives .
- Set and .
- Set and .
- If , then set and and repeat step 5 until .
- Make monic by dividing through its leading coefficient.
- Output .
The proof that the algorithm is correct can be found in .[5]
Example
As an example consider the curve
of genus 2 over the real numbers. For the points
- , and
and the reduced divisors
- and
we know that
- , and
are the Mumford representations of and respectively.
We can compute their sum using Cantor's algorithm. We begin by computing
- , and
for , and .
In the second step we find
- and
for and .
Now we can compute
- ,
- and
- .
So
- and
-
- .
Lastly we find
- and
- .
After making monic we conclude that
is equivalent to .
More on Cantor's algorithm
Cantor's algorithm as presented here has a general form, it holds for hyperelliptic curves of any genus and over any field. However, the algorithm is not very efficient. For example, it requires the use of the extended Euclidean algorithm. If we fix the genus of the curve or the characteristic of the field (or both), we can make the algorithm more efficient. For some special cases we even get explicit addition and doubling formulas which are very fast. For example, there are explicit formulas for hyperelliptic curves of genus 2[6] [7] and genus 3.
For hyperelliptic curves it is also fairly easy to visualize the adding of two reduced divisors. Suppose we have a hyperelliptic curve of genus 2 over the real numbers of the form
and two reduced divisors
- and
- .
Assume that
- ,
this case has to be treated separately. There is exactly 1 cubic polynomial
going through the four points
- .
Note here that it could be possible that for example , hence we must take multiplicities into account. Putting we find that
and hence
- .
As is a polynomial of degree 6, we have that has six zeroes and hence has besides two more intersection points with , call them and , with . Now, are intersection points of with an algebraic curve. As such we know that the divisor
is principal which implies that the divisor
is equivalent to the divisor
- .
Furthermore the divisor
is principal for every point on as it comes from the rational function . This gives that and are equivalent. Combining these two properties we conclude that
is equivalent to the reduced divisor
- .
In a picture this looks like Figure 2. It is possible to explicitly compute the coefficients of , in this way we can arrive at explicit formulas for adding two reduced divisors.
References
- ↑ Isabelle Déchène, The Picard Group, or how to build a group from a set
- ↑ 2.0 2.1 Alfred J. Menezes, Yi-Hong Wu, Robert J. Zuccherato, An elementary introduction to hyperelliptic curves, page 15
- ↑ Alfred J. Menezes, Yi-Hong Wu, Robert J. Zuccherato, An elementary introduction to hyperelliptic curves, page 20
- ↑ Alfred J. Menezes, Yi-Hong Wu, Robert J. Zuccherato, An elementary introduction to hyperelliptic curves, page 22–27
- ↑ Cantor, David G. (1987). "Computing in the Jacobian of a hyperelliptic curve". Mathematics of Computation 48: 95–101. doi:10.1090/S0025-5718-1987-0866101-0.
- ↑ Frank Leitenberger, About the Group Law for the Jacobi Variety of a Hyperelliptic Curve
- ↑ T. Lange (2005). "Formulae for Arithmetic on Genus $2$ Hyperelliptic Curves". Applicable Algebra in Engineering, Communication and Computing (AAECC) 15: 295–328. doi:10.1007/s00200-004-0154-8.