Imaginary hyperelliptic curve
Encyclopedia
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 curve
s have two points at infinity.
. 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 
.
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.
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.
.
The polynomial
is irreducible
over
, so
is an integral domain.
Proof. If were reducible over
, it would factor as for some ∈ 
. But then so it has degree , and so it has degree smaller than , which is impossible.
Note that any polynomial function
can be written uniquely
as
with 
, 
∈ 
is defined to be
.
The norm of is the polynomial function
. Note that , so is a polynomial in only one variable
.
If , then the degree of is defined as
.
Properties:
of over is the field of fractions
of , and the function field
of over 
is the field of fractions of 
. The elements of 
are called rational functions on .
For such a rational function, and a finite point on , is said to be defined at if there exist polynomial functions such that and , and then the value
of at is
.
For a point on that is not finite, i.e. =
, we define as:
For
and 
,
and 
, the order of at is defined as:
if is a finite point which is not Weierstrass. Here is the highest power of which divides both and . Write and if , then is the highest power of which divides , otherwise, .
if is a finite Weierstrass point, with and as above.
if .
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 
. It can be shown that 
has only a finite number of zeroes and poles, and thus only finitely many of the ord
are non-zero. This implies that div
is a divisor. Moreover, as 
, 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.
s 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.
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 
. 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.
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
.
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 
. 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 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
The proof that the algorithm is correct can be found in
. As an example look again at
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 
and after making 
monic we conclude that 
is equivalent to 
.
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
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.
Algebraic curve
In algebraic geometry, an algebraic curve is an algebraic variety of dimension one. The theory of these curves in general was quite fully developed in the nineteenth century, after many particular examples had been considered, starting with circles and other conic sections.- Plane algebraic curves...
.
There exist hyperelliptic curves of every genus
Genus (mathematics)
In mathematics, genus has a few different, but closely related, meanings:-Orientable surface:The genus of a connected, orientable surface is an integer representing the maximum number of cuttings along non-intersecting closed simple curves without rendering the resultant manifold disconnected. It...
. If the genus of a hyperelliptic curve equals 1, we simply call the curve an elliptic curveElliptic curve
In mathematics, an elliptic curve is a smooth, projective algebraic curve of genus one, on which there is a specified point O. An elliptic curve is in fact an abelian variety — that is, it has a multiplication defined algebraically with respect to which it is a group — and O serves as the identity...
. Hence we can see hyperelliptic curves as generalizations of elliptic curves. There is a well-known group
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
structure on the set of points lying on an elliptic curve over some field
Field (mathematics)
In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...
, 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 curveReal hyperelliptic curve
A hyperelliptic curve is a class of algebraic curves. Hyperelliptic curves exist for every genus g \geq 1. The general formula of Hyperelliptic curve over a finite field K is given byC : y^2 + h y = f \in K[x,y]...
s have two points at infinity.
Formal definition
Hyperelliptic curves can be defined over fields of any characteristicCharacteristic (algebra)
In mathematics, the characteristic of a ring R, often denoted char, is defined to be the smallest number of times one must use the ring's multiplicative identity element in a sum to get the additive identity element ; the ring is said to have characteristic zero if this repeated sum never reaches...
. Hence we consider an arbitrary field
and its algebraic closureAlgebraic closure
In mathematics, particularly abstract algebra, an algebraic closure of a field K is an algebraic extension of K that is algebraically closed. It is one of many closures in mathematics....
. An (imaginary) hyperelliptic curve of genus over is given by an equation of the formwhere
is a polynomial of degree not larger than and is a monic polynomial of degree . Furthermore we require the curve to have no singular pointsSingular point of a curve
In geometry, a singular point on a curve is one where the curve is not given by a smooth embedding of a parameter. The precise definition of a singular point depends on the type of curve being studied.-Algebraic curves in the plane:...
. 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 planeProjective plane
In mathematics, a projective plane is a geometric structure that extends the concept of a plane. In the ordinary Euclidean plane, two lines typically intersect in a single point, but there are some pairs of lines that do not intersect...
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 pointWeierstrass point
In mathematics, a Weierstrass point P on a nonsingular algebraic curve C defined over the complex numbers is a point such that there are extra functions on C, with their poles restricted to P only, than would be predicted by looking at the Riemann–Roch theorem...
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 rootMultiplicity (mathematics)
In mathematics, the multiplicity of a member of a multiset is the number of times it appears in the multiset. For example, the number of times a given polynomial equation has a root at a given point....
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 cryptographyHyperelliptic curve cryptography
Hyperelliptic curve cryptography is similar to elliptic curve cryptography insofar as the Jacobian of a hyperelliptic curve is an Abelian group on which to do arithmetic, just as we use the group of points on an elliptic curve in ECC.-Definition:...
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 theoremBézout's theorem
Bézout's theorem is a statement in algebraic geometry concerning the number of common points, or intersection points, of two plane algebraic curves. The theorem claims that the number of common points of two such curves X and Y is equal to the product of their degrees...
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 over is defined as.The polynomial
Polynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
is irreducibleIrreducible polynomial
In mathematics, the adjective irreducible means that an object cannot be expressed as the product of two or more non-trivial factors in a given set. See also factorization....
over
, sois an integral domain.
Proof. If were reducible over
, it would factor as for some ∈ . But then so it has degree , and so it has degree smaller than , which is impossible.Note that any polynomial function
can be written uniquelyUniqueness quantification
In mathematics and logic, the phrase "there is one and only one" is used to indicate that exactly one object with a certain property exists. In mathematical logic, this sort of quantification is known as uniqueness quantification or unique existential quantification.Uniqueness quantification is...
as
with , ∈ Norm and degree
The conjugate of a polynomial function in is defined to be.The norm of is the polynomial function
. Note that , so is a polynomial in only one variableVariable (mathematics)
In mathematics, a variable is a value that may change within the scope of a given problem or set of operations. In contrast, a constant is a value that remains unchanged, though often unknown or undetermined. The concepts of constants and variables are fundamental to many areas of mathematics and...
.
If , then the degree of is defined as
.Properties:
Function field
The function fieldFunction field of an algebraic variety
In algebraic geometry, the function field of an algebraic variety V consists of objects which are interpreted as rational functions on V...
of over is the field of fractions
Field of fractions
In abstract algebra, the field of fractions or field of quotients of an integral domain is the smallest field in which it can be embedded. The elements of the field of fractions of the integral domain R have the form a/b with a and b in R and b ≠ 0...
of , and the function field
of over is the field of fractions of . The elements of are called rational functions on .For such a rational function, and a finite point on , is said to be defined at if there exist polynomial functions such that and , and then the value
Value (mathematics)
In mathematics, value commonly refers to the 'output' of a function. In the most basic case, that of unary, single-valued functions, there is one input and one output .The function f of the example is real-valued, since each and every possible function value is real...
of at is
.For a point on that is not finite, i.e. =
, we define as:- If
then 
, i.e. R has a zero at O. - If
then 
is not definedUndefinedUndefined may refer to:* Something that lacks definition* In mathematics, something which lacks well-definition* In calculus, an indeterminate form* Undefined citizenship, a term used sometimes for statelessness- In computing :...
, i.e. R has a pole at O. - If
then 
is the ratio of the leading coefficients of and .
For
and ,
- If
then is said to have a zero at , - If is not defined at then is said to have a pole at , and we write
.
Order of a polynomial function at a point
For and , the order of at is defined as: if is a finite point which is not Weierstrass. Here is the highest power of which divides both and . Write and if , then is the highest power of which divides , otherwise, . if is a finite Weierstrass point, with and as above. if .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 groupAbelian group
In abstract algebra, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on their order . Abelian groups generalize the arithmetic of addition of integers...
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 subgroupSubgroup
In group theory, given a group G under a binary operation *, a subset H of G is called a subgroup of G if H also forms a group under the operation *. More precisely, H is a subgroup of G if the restriction of * to H x H is a group operation on H...
of
.Proof. Consider the map
defined by , note that forms a group under the usual addition. Then and hence is a group homomorphismGroup homomorphism
In mathematics, given two groups and , a group homomorphism from to is a function h : G → H such that for all u and v in G it holds that h = h \cdot h...
. Now,
is the kernelKernel (algebra)
In the various branches of mathematics that fall under the heading of abstract algebra, the kernel of a homomorphism measures the degree to which the homomorphism fails to be injective. An important special case is the kernel of a matrix, also called the null space.The definition of kernel takes...
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 . It can be shown that has only a finite number of zeroes and poles, and thus only finitely many of the ord are non-zero. This implies that div is a divisor. Moreover, as , 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 closedClosure (mathematics)
In mathematics, a set is said to be closed under some operation if performance of that operation on members of the set always produces a unique member of the same set. For example, the real numbers are closed under subtraction, but the natural numbers are not: 3 and 8 are both natural numbers, but...
under addition and inverses, making it into a subgroup.
We can now define the quotient group
Quotient group
In mathematics, specifically group theory, a quotient group is a group obtained by identifying together elements of a larger group using an equivalence relation...
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 curveElliptic curve
In mathematics, an elliptic curve is a smooth, projective algebraic curve of genus one, on which there is a specified point O. An elliptic curve is in fact an abelian variety — that is, it has a multiplication defined algebraically with respect to which it is a group — and O serves as the identity...
s 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 isomorphismGroup isomorphism
In abstract algebra, a group isomorphism is a function between two groups that sets up a one-to-one correspondence between the elements of the groups in a way that respects the given group operations. If there exists an isomorphism between two groups, then the groups are called isomorphic...
, 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 . 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 satisfyfor
.Cantor's algorithm
There is an algorithmAlgorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
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 . 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 CantorGeorg Cantor
Georg Ferdinand Ludwig Philipp Cantor was a German mathematician, best known as the inventor of set theory, which has become a fundamental theory in mathematics. Cantor established the importance of one-to-one correspondence between the members of two sets, defined infinite and well-ordered sets,...
), explaining the name of the algorithm. Cantor only looked at the case
, the general case is due to KoblitzNeal Koblitz
Neal I. Koblitz is a Professor of Mathematics at the University of Washington in the Department of Mathematics. He is also an adjunct professor with the Centre for Applied Cryptographic Research at the University of Waterloo. He is the creator of hyperelliptic curve cryptography and the...
. 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 algorithmExtended Euclidean algorithmThe extended Euclidean algorithm is an extension to the Euclidean algorithm. Besides finding the greatest common divisor of integers a and b, as the Euclidean algorithm does, it also finds integers x and y that satisfy Bézout's identityThe extended Euclidean algorithm is particularly useful when a...
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
. As an example look again at
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 and after making monic we conclude that is equivalent to .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
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 multiplicitiesMultiplicity (mathematics)
In mathematics, the multiplicity of a member of a multiset is the number of times it appears in the multiset. For example, the number of times a given polynomial equation has a root at a given point....
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.