Imaginary hyperelliptic curve

A hyperelliptic curve is a particular kind of algebraic curve. 
There exist hyperelliptic curves of every genus formula_1. 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 formula_2, 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 formula_2 and its algebraic closure formula_4. An (imaginary) hyperelliptic curve of genus formula_5 over formula_2 is given by an equation of the form
where formula_7 is a polynomial of degree not larger than formula_5 and formula_9 is a monic polynomial of degree formula_10. Furthermore, we require the curve to have no singular points. In our setting, this entails that no point formula_11 satisfies both formula_12 and the equations formula_13 and formula_14. This definition differs from the definition of a general hyperelliptic curve in the fact that formula_15 can also have degree formula_16 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 formula_17 corresponds to formula_15 being a cubic polynomial, agreeing with the definition of an elliptic curve. If we view the curve as lying in the projective plane formula_19 with coordinates formula_20, we see that there is a particular point lying on the curve, namely the point at infinity formula_21 denoted by formula_22. So we could write formula_23.
Suppose the point formula_24 not equal to formula_22 lies on the curve and consider formula_26. As formula_27 can be simplified to formula_28, we see that formula_29 is also a point on the curve. formula_29 is called the opposite of formula_31 and formula_31 is called a Weierstrass point if formula_33, i.e. formula_34. Furthermore, the opposite of formula_22 is simply defined as formula_36.
Alternative definition.
The definition of a hyperelliptic curve can be slightly simplified if we require that the characteristic of formula_2 is not equal to 2. To see this we consider the change of variables formula_38 and formula_39, which makes sense if charformula_40. Under this change of variables we rewrite formula_12 to formula_42 which, in turn, can be rewritten to formula_43. As formula_44 we know that formula_45 and hence formula_46 is a monic polynomial of degree formula_10. This means that over a field formula_2 with charformula_40 every hyperelliptic curve of genus formula_5 is isomorphic to one given by an equation of the form formula_51 where formula_15 is a monic polynomial of degree formula_10 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 formula_24 on the curve is singular if and only if formula_55 and formula_56. As formula_57 and formula_58, it must be the case that formula_59 and thus formula_60 is a multiple root of formula_61. We conclude that the curve formula_62 has no singular points if and only if formula_61 has no multiple roots. Even though the definition of a hyperelliptic curve is quite easy when charformula_64, we should not forget about fields of characteristic 2 as hyperelliptic curve cryptography makes extensive use of such fields.
Example.
As an example consider formula_62 where formula_66 over formula_67. As formula_15 has degree 5 and the roots are all distinct, formula_69 is a curve of genus formula_70. 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 formula_22 lies on the curve. From the graph of formula_69 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 formula_69 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 formula_75 is irreducible over formula_4, so
is an integral domain. 
"Proof". If were reducible over formula_4, it would factor as for some ∈ formula_4. But then so it has degree , and so it has degree smaller than , which is impossible.
Note that any polynomial function formula_80 can be written uniquely as 
Norm and degree.
The conjugate of a polynomial function in formula_85 is defined to be
The norm of is the polynomial function formula_87. Note that , so is a polynomial in only one variable.
If , then the degree of is defined as
Properties:
Function field.
The function field of over is the field of fractions of , and the function field formula_92 of over formula_4 is the field of fractions of formula_85. The elements of formula_92 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. = formula_22, we define as: 
For formula_104 and formula_105, 
Order of a polynomial function at a point.
For formula_108 and formula_105, the order of at is defined as:
The divisor and the Jacobian.
In order to define the Jacobian, we first need the notion of a divisor. Consider a hyperelliptic curve formula_69 over some field formula_2. Then we define a divisor formula_115 to be a formal sum of points in formula_69, i.e. formula_117 where formula_118 and furthermore formula_119 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 formula_120 given by a single point (as one might expect from the analogy with elliptic curves). Furthermore, we define the degree of formula_115 as formula_122. The set of all divisors formula_123 of the curve formula_69 forms an Abelian group where the addition is defined pointwise as follows formula_125. It is easy to see that formula_126 acts as the identity element and that the inverse of formula_127 equals formula_128. The set formula_129 of all divisors of degree 0 can easily be checked to be a subgroup of formula_123. 
"Proof". Consider the map formula_131 defined by formula_132, note that formula_133 forms a group under the usual addition. Then formula_134 and hence formula_135 is a group homomorphism. Now, formula_136 is the kernel of this homomorphism and thus it is a subgroup of formula_123.
Consider a function formula_138, then we can look at the formal sum divformula_139. Here ordformula_140 denotes the order of formula_15 at formula_31. We have that ordformula_143 if formula_15 has a pole of order -ordformula_140 at formula_31, ordformula_147 if formula_15 is defined and non-zero at formula_31 and ordformula_150 if formula_15 has a zero of order ordformula_140 at formula_31. It can be shown that formula_15 has only a finite number of zeroes and poles, and thus only finitely many of the ordformula_140 are non-zero. This implies that divformula_156 is a divisor. Moreover, as formula_157, it is the case that divformula_156 is a divisor of degree 0. Such divisors, i.e. divisors coming from some rational function formula_15, are called principal divisors and the set of all principal divisors formula_160 is a subgroup of formula_136. 
"Proof". The identity element formula_126 comes from a constant function which is non-zero. Suppose formula_163 are two principal divisors coming from formula_15 and formula_5 respectively. Then formula_166 comes from the function formula_167, and thus formula_168 is a principal divisor, too. We conclude that formula_160 is closed under addition and inverses, making it into a subgroup.
We can now define the quotient group formula_170 which is called the Jacobian or the Picard group of formula_69. Two divisors formula_172 are called equivalent if they belong to the same element of formula_173, this is the case if and only if formula_168 is a principal divisor. Consider for example a hyperelliptic curve formula_175 over a field formula_2 and a point formula_24 on formula_69. For formula_179 the rational function formula_180 has a zero of order formula_181 at both formula_31 and formula_29 and it has a pole of order formula_184 at formula_22. Therefore, we find divformula_186 and we can simplify this to divformula_187 if formula_31 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 formula_189 over a field formula_2. The first step is to relate a divisor formula_115 to every point formula_31 on the curve. To a point formula_31 on formula_189 we associate the divisor formula_195, in particular formula_22 in linked to the identity element formula_197. In a straightforward fashion we can now relate an element of formula_198 to each point formula_31 by linking formula_31 to the class of formula_201, denoted by formula_202. Then the map formula_203 from the group of points on formula_189 to the Jacobian of formula_189 defined by formula_206 is a group homomorphism. This can be shown by looking at three points on formula_189 adding up to formula_22, i.e. we take formula_209 with formula_210 or formula_211. We now relate the addition law on the Jacobian to the geometric group law on elliptic curves. Adding formula_31 and formula_213 geometrically means drawing a straight line through formula_31 and formula_213, this line intersects the curve in one other point. We then define formula_216 as the opposite of this point. Hence in the case formula_217 we have that these three points are collinear, thus there is some linear formula_218 such that formula_31, formula_213 and formula_221 satisfy formula_222. Now, formula_223 which is the identity element of formula_198 as formula_225 is the divisor on the rational function formula_15 and thus it is a principal divisor. We conclude that formula_227.
The Abel-Jacobi theorem states that a divisor formula_228 is principal if and only if formula_115 has degree 0 and formula_230 under the usual addition law for points on cubic curves. As two divisors formula_231 are equivalent if and only if formula_168 is principal, we conclude that formula_233 and formula_234 are equivalent if and only if formula_235. Now, every nontrivial divisor of degree 0 is equivalent to a divisor of the form formula_236, this implies that we have found a way to ascribe a point on formula_189 to every class formula_202. Namely, to formula_239 we ascribe the point formula_240. This maps extends to the neutral element 0 which is maped to formula_241. As such the map formula_242 defined by formula_243 is the inverse of formula_244. So formula_244 is in fact a group isomorphism, proving that formula_189 and formula_198 are isomorphic.
The Jacobian of a hyperelliptic curve.
The general hyperelliptic case is a bit more complicated. Consider a hyperelliptic curve formula_248 of genus formula_5 over a field formula_2. A divisor formula_115 of formula_69 is called reduced if it has the form formula_253 where formula_254, formula_255 for all formula_256 and formula_257 for formula_258. Note that a reduced divisor always has degree 0, also it is possible that formula_259 if formula_258, but only if formula_261 is not a Weierstrass point. It can be proven that for each divisor formula_262 there is a unique reduced divisor formula_263 such that formula_115 is equivalent to formula_263. Hence every class of the quotient group formula_173 has precisely one reduced divisor. Instead of looking at formula_173 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 formula_268 such that formula_269 is monic, formula_270 and formula_271. Every non-trivial reduced divisor can be represented by a unique pair of such polynomials. This can be seen by factoring formula_272 in formula_4 which can be done as such as formula_269 is monic. The last condition on formula_269 and formula_276 then implies that the point formula_277 lies on formula_69 for every formula_256. Thus formula_280 is a divisor and in fact it can be shown to be a reduced divisor. For example, the condition formula_281 ensures that formula_254. This gives the 1-1 correspondence between reduced divisors and divisors in Mumford representation. As an example, formula_126 is the unique reduced divisor belonging to the identity element of formula_173. Its Mumford representation is formula_285 and formula_286. Going back and forth between reduced divisors and their Mumford representation is now an easy task. For example, consider the hyperelliptic curve formula_287 of genus 2 over the real numbers. We can find the following points on the curve formula_288, formula_289 and formula_290. Then we can define reduced divisors formula_291 and formula_292. The Mumford representation of formula_115 consists of polynomials formula_269 and formula_276 with formula_296 and we know that the first coordinates of formula_31 and formula_213, i.e. 1 and 3, must be zeroes of formula_269. Hence we have formula_300. As formula_301 and formula_302 it must be the case that formula_303 and formula_304 and thus formula_276 has degree 1. There is exactly one polynomial of degree 1 with these properties, namely formula_306. Thus the Mumford representation of formula_115 is formula_308 and formula_309. In a similar fashion we can find the Mumford representation formula_310 of formula_263, we have formula_312 and formula_313. If a point formula_314 appears with multiplicity "n", the polynomial "v" needs to satisfy
formula_315
for formula_316.
Cantor's algorithm.
There is an algorithm which takes two reduced divisors formula_317 and formula_318 in their Mumford representation and produces the unique reduced divisor formula_115, again in its Mumford representation, such that formula_115 is equivalent to formula_321. 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 formula_322, the general case is due to Koblitz. The input is two reduced divisors formula_323 and formula_324 in their Mumford representation of the hyperelliptic curve formula_248 of genus formula_5 over the field formula_2. The algorithm works as follows
The proof that the algorithm is correct can be found in 
Example.
As an example consider the curve
of genus 2 over the real numbers. For the points 
and the reduced divisors 
we know that 
are the Mumford representations of formula_317 and formula_318 respectively.
We can compute their sum using Cantor's algorithm. We begin by computing 
for formula_360, and formula_361.
In the second step we find 
for formula_364 and formula_365.
Now we can compute 
So 
Lastly we find 
After making formula_346 monic we conclude that 
is equivalent to formula_321.
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 
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 
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 formula_384, hence we must take multiplicities into account. Putting formula_385 we find that 
and hence 
As formula_388 is a polynomial of degree 6, we have that formula_389 has six zeroes and hence formula_390 has besides formula_383 two more intersection points with formula_69, call them formula_393 and formula_394, with formula_395. Now, formula_396 are intersection points of formula_69 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 formula_24 on formula_69 as it comes from the rational function formula_404. This gives that formula_405 and formula_406 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 formula_390, in this way we can arrive at explicit formulas for adding two reduced divisors.