Imaginary hyperelliptic curve

A hyperelliptic curve is a particular kind of algebraic curve. There exist hyperelliptic curves of every genus $g\geq 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 $K$, 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 $K$ and its algebraic closure ${\overline {K}}$. An (imaginary) hyperelliptic curve of genus $g$ over $K$ is given by an equation of the form

${\displaystyle C:y^{2}+h(x)y=f(x)\in K[x,y]}$

where $h(x)\in K[x]$ is a polynomial of degree not larger than $g$ and $f(x)\in K[x]$ is a monic polynomial of degree $2g+1$. Furthermore, we require the curve to have no singular points. In our setting, this entails that no point ${\displaystyle (x,y)\in {\overline {K}}\times {\overline {K}}}$ satisfies both ${\displaystyle y^{2}+h(x)y=f(x)}$ and the equations ${\displaystyle 2y+h(x)=0}$ and ${\displaystyle h'(x)y=f'(x)}$. This definition differs from the definition of a general hyperelliptic curve in the fact that $f$ can also have degree ${\displaystyle 2g+2}$ 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 $g=1$ corresponds to $f$ being a cubic polynomial, agreeing with the definition of an elliptic curve. If we view the curve as lying in the projective plane ${\displaystyle \mathbb {P} ^{2}(K)}$ with coordinates ${\displaystyle (X:Y:Z)}$, we see that there is a particular point lying on the curve, namely the point at infinity $(0:1:0)$ denoted by $O$. So we could write ${\displaystyle C=\{(x,y)\in K^{2}|y^{2}+h(x)y=f(x)\}\cup \{O\}}$.

Suppose the point ${\displaystyle P=(a,b)}$ not equal to $O$ lies on the curve and consider ${\displaystyle {\overline {P}}=(a,-b-h(a))}$. As ${\displaystyle (-b-h(a))^{2}+h(a)(-b-h(a))}$ can be simplified to ${\displaystyle b^{2}+h(a)b}$, we see that $\overline{P}$ is also a point on the curve. $\overline{P}$ is called the opposite of $P$ and $P$ is called a Weierstrass point if ${\displaystyle P={\overline {P}}}$, i.e. ${\displaystyle h(a)=-2b}$. Furthermore, the opposite of $O$ is simply defined as ${\displaystyle {\overline {O}}=O}$.

Alternative definition

The definition of a hyperelliptic curve can be slightly simplified if we require that the characteristic of $K$ is not equal to 2. To see this we consider the change of variables $x\rightarrow x$ and ${\displaystyle y\rightarrow y-{\frac {h(x)}{2}}}$, which makes sense if char${\displaystyle (K)\not =2}$. Under this change of variables we rewrite ${\displaystyle y^{2}+h(x)y=f(x)}$ to ${\displaystyle \left(y-{\frac {h(x)}{2}}\right)^{2}+h(x)\left(y-{\frac {h(x)}{2}}\right)=f(x)}$ which, in turn, can be rewritten to ${\displaystyle y^{2}=f(x)+{\frac {h(x)^{2}}{4}}}$. As ${\displaystyle \deg(h)\leq g}$ we know that ${\displaystyle \deg(h^{2})\leq 2g}$ and hence ${\displaystyle f(x)+{\frac {h(x)^{2}}{4}}}$ is a monic polynomial of degree $2g+1$. This means that over a field $K$ with char${\displaystyle (K)\not =2}$ every hyperelliptic curve of genus $g$ is isomorphic to one given by an equation of the form ${\displaystyle C:y^{2}=f(x)}$ where $f$ is a monic polynomial of degree $2g+1$ 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 ${\displaystyle P=(a,b)}$ on the curve is singular if and only if $b=0$ and ${\displaystyle f'(a)=0}$. As ${\displaystyle b=0}$ and ${\displaystyle b^{2}=f(a)}$, it must be the case that ${\displaystyle f(a)=0}$ and thus $a$ is a multiple root of $f$. We conclude that the curve $C:y^{2}=f(x)$ has no singular points if and only if $f$ has no multiple roots. Even though the definition of a hyperelliptic curve is quite easy when char${\displaystyle (K)\not =2}$, we should not forget about fields of characteristic 2 as hyperelliptic curve cryptography makes extensive use of such fields.

Example

Figure 1: Example of a hyperelliptic curve

As an example consider $C:y^{2}=f(x)$ where ${\displaystyle f(x)=x^{5}-2x^{4}-7x^{3}+8x^{2}+12x=x(x+1)(x-3)(x+2)(x-2)}$ over $\mathbb {R}$. As $f$ has degree 5 and the roots are all distinct, $C$ is a curve of genus ${\displaystyle g=2}$. 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 $O$ lies on the curve. From the graph of $C$ 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 $C$ 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

${\displaystyle \;K[C]=K[x,y]/(y^{2}+h(x)y-f(x))}$.

The polynomial ${\displaystyle \,r(x,y)=y^{2}+h(x)y-f(x)}$ is irreducible over ${\overline {K}}$, so

${\displaystyle {\overline {K}}[C]={\overline {K}}[x,y]/(y^{2}+h(x)y-f(x))}$

is an integral domain.
Proof. If r (x,y) were reducible over ${\overline {K}}$, it would factor as (y - u(x)) · (y - v(x)) for some u,v ∈ ${\overline {K}}$. 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 ${\displaystyle G(x,y)\in {\overline {K}}[C]}$ can be written uniquely as

${\displaystyle \,G(x,y)=u(x)-v(x)y}$   with $u(x)$, $v(x)$ ∈ ${\displaystyle {\overline {K}}[x]}$

Norm and degree

The conjugate of a polynomial function G(x,y) = u(x) - v(x)y in ${\displaystyle {\overline {K}}[C]}$ is defined to be

${\displaystyle {\overline {G}}(x,y)=u(x)+v(x)(h(x)+y)}$.

The norm of G is the polynomial function ${\displaystyle N(G)=G{\overline {G}}}$. Note that N(G) = u(x)² + u(x)v(x)h(x) - v(x)²f(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

${\displaystyle \,\deg(G)=\max[2\deg(u),2g+1+2\deg(v)]}$.

Properties:

${\displaystyle \;\deg(G)=\deg _{x}(N(G))}$

${\displaystyle \;\deg(GH)=\deg(G)+\deg(H)}$

${\displaystyle \deg(G)=\deg({\overline {G}})}$

Function field

The function field K(C) of C over K is the field of fractions of K[C], and the function field ${\displaystyle {\overline {K}}(C)}$ of C over ${\overline {K}}$ is the field of fractions of ${\displaystyle {\overline {K}}[C]}$. The elements of ${\displaystyle {\overline {K}}(C)}$ 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

${\displaystyle \,R(P)=G(P)/H(P)}$.

For P a point on C that is not finite, i.e. P = $O$, we define R(P) as:

If ${\displaystyle \;\deg(G)<\deg(H)}$  then ${\displaystyle R(O)=0}$, i.e. R has a zero at O.

If ${\displaystyle \;\deg(G)>\deg(H)}$  then ${\displaystyle R(O)}$  is not defined, i.e. R has a pole at O.

If ${\displaystyle \;\deg(G)=\deg(H)}$  then ${\displaystyle R(O)}$  is the ratio of the leading coefficients of G and H.

For ${\displaystyle R\in {\overline {K}}(C)^{*}}$ and ${\displaystyle P\in C}$,

If ${\displaystyle \;R(P)=0}$ 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 ${\displaystyle R(P)=\infty }$.

Order of a polynomial function at a point

For ${\displaystyle G=u(x)-v(x)\cdot y\in {\overline {K}}[C]^{2}}$ and ${\displaystyle P\in C}$, the order of G at P is defined as:

${\displaystyle \;ord_{P}(G)=r+s}$ 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(u₀(x) - v₀(x)y) and if u₀(a) - v₀(a)b = 0, then s is the highest power of (x - a) which divides N(u₀(x) - v₀(x)y) = u₀² + u₀v₀h - v₀²f, otherwise, s = 0.

${\displaystyle \;ord_{P}(G)=2r+s}$ if P = (a,b) is a finite Weierstrass point, with r and s as above.

${\displaystyle \;ord_{P}(G)=-\deg(G)}$ 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 $C$ over some field $K$. Then we define a divisor $D$ to be a formal sum of points in $C$, i.e. ${\displaystyle D=\sum _{P\in C}{c_{P}[P]}}$ where ${\displaystyle c_{P}\in \mathbb {Z} }$ and furthermore ${\displaystyle \{c_{P}|c_{P}\not =0\}}$ 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 ${\displaystyle c_{P}[P]}$ given by a single point (as one might expect from the analogy with elliptic curves). Furthermore, we define the degree of $D$ as ${\displaystyle \deg(D)=\sum _{P\in C}{c_{P}}\in \mathbb {Z} }$. The set of all divisors ${\displaystyle \mathrm {Div} (C)}$ of the curve $C$ forms an Abelian group where the addition is defined pointwise as follows ${\displaystyle \sum _{P\in C}{c_{P}[P]}+\sum _{P\in C}{d_{P}[P]}=\sum _{P\in C}{(c_{P}+d_{P})[P]}}$. It is easy to see that ${\displaystyle 0=\sum _{P\in C}{0[P]}}$ acts as the identity element and that the inverse of ${\displaystyle \sum _{P\in C}{c_{P}[P]}}$ equals ${\displaystyle \sum _{P\in C}{-c_{P}[P]}}$. The set ${\displaystyle \mathrm {Div} ^{0}(C)=\{D\in \mathrm {Div} (C)|\deg(D)=0\}}$ of all divisors of degree 0 can easily be checked to be a subgroup of ${\displaystyle \mathrm {Div} (C)}$.
Proof. Consider the map ${\displaystyle \varphi :\mathrm {Div} (C)\rightarrow \mathbb {Z} }$ defined by ${\displaystyle \varphi (D)=\deg(D)}$, note that $\mathbb {Z}$ forms a group under the usual addition. Then ${\displaystyle \varphi (\sum _{P\in C}{c_{P}[P]}+\sum _{P\in C}{d_{P}[P]})=\varphi (\sum _{P\in C}{(c_{P}+d_{P})[P]})=\sum _{P\in C}{c_{P}+d_{P}}=\sum _{P\in C}{c_{p}}+\sum _{P\in C}{d_{p}}=\varphi (\sum _{P\in C}{c_{P}[P]})+\varphi (\sum _{P\in C}{d_{P}[P]})}$ and hence $\varphi$ is a group homomorphism. Now, ${\displaystyle \mathrm {Div} ^{0}(C)}$ is the kernel of this homomorphism and thus it is a subgroup of ${\displaystyle \mathrm {Div} (C)}$.

Consider a function ${\displaystyle f\in {\overline {K}}(C)^{*}}$, then we can look at the formal sum div${\displaystyle (f)=\sum _{P\in C}{\mathrm {ord} _{P}(f)[P]}}$. Here ord${\displaystyle _{P}(f)}$ denotes the order of $f$ at $P$. We have that ord${\displaystyle _{P}(f)<0}$ if $f$ has a pole of order -ord${\displaystyle _{P}(f)}$ at $P$, ord${\displaystyle _{P}(f)=0}$ if $f$ is defined and non-zero at $P$ and ord${\displaystyle _{P}(f)>0}$ if $f$ has a zero of order ord${\displaystyle _{P}(f)}$ at $P$.^[1] It can be shown that $f$ has only a finite number of zeroes and poles,^[2] and thus only finitely many of the ord${\displaystyle _{P}(f)}$ are non-zero. This implies that div$(f)$ is a divisor. Moreover, as ${\displaystyle \sum _{P\in C}{\mathrm {ord} _{P}(f)}=0}$,^[2] it is the case that div$(f)$ is a divisor of degree 0. Such divisors, i.e. divisors coming from some rational function $f$, are called principal divisors and the set of all principal divisors ${\displaystyle \mathrm {Princ} (C)}$ is a subgroup of ${\displaystyle \mathrm {Div} ^{0}(C)}$.
Proof. The identity element ${\displaystyle 0=\sum _{P\in C}{0[P]}}$ comes from a constant function which is non-zero. Suppose ${\displaystyle D_{1}=\sum _{P\in C}{\mathrm {ord} _{P}(f)[P]},D_{2}=\sum _{P\in C}{\mathrm {ord} _{P}(g)[P]}\in \mathrm {Princ} (C)}$ are two principal divisors coming from $f$ and $g$ respectively. Then ${\displaystyle D_{1}-D_{2}=\sum _{P\in C}{(\mathrm {ord} _{P}(f)-\mathrm {ord} _{P}(g))[P]}}$ comes from the function ${\displaystyle f/g}$, and thus ${\displaystyle D_{1}-D_{2}}$ is a principal divisor, too. We conclude that ${\displaystyle \mathrm {Princ} (C)}$ is closed under addition and inverses, making it into a subgroup.

We can now define the quotient group ${\displaystyle J(C):=\mathrm {Div} ^{0}(C)/\mathrm {Princ} (C)}$ which is called the Jacobian or the Picard group of $C$. Two divisors ${\displaystyle D_{1},D_{2}\in \mathrm {Div} ^{0}(C)}$ are called equivalent if they belong to the same element of $J(C)$, this is the case if and only if ${\displaystyle D_{1}-D_{2}}$ is a principal divisor. Consider for example a hyperelliptic curve ${\displaystyle C:y^{2}+h(x)y=f(x)}$ over a field $K$ and a point ${\displaystyle P=(a,b)}$ on $C$. For ${\displaystyle n\in \mathbb {Z} _{>0}}$ the rational function ${\displaystyle f(x)=(x-a)^{n}}$ has a zero of order $n$ at both $P$ and $\overline{P}$ and it has a pole of order $2n$ at $O$. Therefore, we find div${\displaystyle (f)=nP+n{\overline {P}}-2nO}$ and we can simplify this to div${\displaystyle (f)=2nP-2nO}$ if $P$ 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 $E$ over a field $K$. The first step is to relate a divisor $D$ to every point $P$ on the curve. To a point $P$ on $E$ we associate the divisor ${\displaystyle D_{P}=1[P]-1[O]}$, in particular $O$ in linked to the identity element ${\displaystyle O-O=0}$. In a straightforward fashion we can now relate an element of ${\displaystyle J(E)}$ to each point $P$ by linking $P$ to the class of $D_{P}$, denoted by ${\displaystyle [D_{P}]}$. Then the map ${\displaystyle \varphi :E\rightarrow J(E)}$ from the group of points on $E$ to the Jacobian of $E$ defined by ${\displaystyle \varphi (P)=[D_{P}]}$ is a group homomorphism. This can be shown by looking at three points on $E$ adding up to $O$, i.e. we take ${\displaystyle P,Q,R\in E}$ with ${\displaystyle P+Q+R=O}$ or ${\displaystyle P+Q=-R}$. We now relate the addition law on the Jacobian to the geometric group law on elliptic curves. Adding $P$ and $Q$ geometrically means drawing a straight line through $P$ and $Q$, this line intersects the curve in one other point. We then define ${\displaystyle P+Q}$ as the opposite of this point. Hence in the case ${\displaystyle P+Q+R=O}$ we have that these three points are collinear, thus there is some linear ${\displaystyle f\in K[x,y]}$ such that $P$, $Q$ and $R$ satisfy $f(x,y)=0$. Now, ${\displaystyle \varphi (P)+\varphi (Q)+\varphi (R)=[D_{P}]+[D_{Q}]+[D_{R}]=[[P]+[Q]+[R]-3[O]]}$ which is the identity element of ${\displaystyle J(E)}$ as ${\displaystyle [P]+[Q]+[R]-3[O]}$ is the divisor on the rational function $f$ and thus it is a principal divisor. We conclude that ${\displaystyle \varphi (P)+\varphi (Q)+\varphi (R)=\varphi (O)=\varphi (P+Q+R)}$.

The Abel-Jacobi theorem states that a divisor ${\displaystyle D=\sum _{P\in E}{c_{P}[P]}}$ is principal if and only if $D$ has degree 0 and ${\displaystyle \sum _{P\in E}{c_{P}P}=O}$ under the usual addition law for points on cubic curves. As two divisors ${\displaystyle D_{1},D_{2}\in \mathrm {Div} ^{0}(E)}$ are equivalent if and only if ${\displaystyle D_{1}-D_{2}}$ is principal, we conclude that ${\displaystyle D_{1}=\sum _{P\in E}{c_{P}[P]}}$ and ${\displaystyle D_{2}=\sum _{P\in E}{d_{P}[P]}}$ are equivalent if and only if ${\displaystyle \sum _{P\in E}{c_{P}P}=\sum _{P\in E}{d_{P}P}}$. Now, every nontrivial divisor of degree 0 is equivalent to a divisor of the form ${\displaystyle [P]-[O]}$, this implies that we have found a way to ascribe a point on $E$ to every class ${\displaystyle [D_{P}]}$. Namely, to ${\displaystyle [D_{P}]=[1[P]-1[O]]}$ we ascribe the point ${\displaystyle (P-O)+O=P}$. This maps extends to the neutral element 0 which is maped to ${\displaystyle 0+O=O}$. As such the map ${\displaystyle \psi :J(E)\rightarrow E}$ defined by ${\displaystyle \psi ([D_{P}])=P}$ is the inverse of $\varphi$. So $\varphi$ is in fact a group isomorphism, proving that $E$ and ${\displaystyle J(E)}$ are isomorphic.

The Jacobian of a hyperelliptic curve

The general hyperelliptic case is a bit more complicated. Consider a hyperelliptic curve ${\displaystyle C:y^{2}+h(x)y=f(x)}$ of genus $g$ over a field $K$. A divisor $D$ of $C$ is called reduced if it has the form ${\displaystyle D=\sum _{i=1}^{k}{[P_{i}]}-k[O]}$ where ${\displaystyle k\leq g}$, ${\displaystyle P_{i}\not =O}$ for all $i=1,...,k$ and ${\displaystyle P_{i}\not ={\overline {P_{j}}}}$ for $i\not =j$. Note that a reduced divisor always has degree 0, also it is possible that ${\displaystyle P_{i}=P_{j}}$ if $i\not =j$, but only if $P_{i}$ is not a Weierstrass point. It can be proven that for each divisor ${\displaystyle D\in \mathrm {Div} ^{0}(C)}$ there is a unique reduced divisor $D'$ such that $D$ is equivalent to $D'$.^[3] Hence every class of the quotient group $J(C)$ has precisely one reduced divisor. Instead of looking at $J(C)$ 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 ${\displaystyle u,v\in K[x]}$ such that $u$ is monic, ${\displaystyle \deg(v)<\deg(u)\leq g}$ and ${\displaystyle u|v^{2}+vh-f}$. Every non-trivial reduced divisor can be represented by a unique pair of such polynomials. This can be seen by factoring ${\displaystyle u(x)=\prod _{i=1}^{k}{(x-x_{i})}}$ in ${\overline {K}}$ which can be done as such as $u$ is monic. The last condition on $u$ and $v$ then implies that the point ${\displaystyle P_{i}=(x_{i},v(x_{i}))}$ lies on $C$ for every $i=1,...,k$. Thus ${\displaystyle D=\sum _{i=1}^{k}{[P_{i}]}-k[O]}$ is a divisor and in fact it can be shown to be a reduced divisor. For example, the condition ${\displaystyle \deg(u)\leq g}$ ensures that ${\displaystyle k\leq g}$. This gives the 1-1 correspondence between reduced divisors and divisors in Mumford representation. As an example, ${\displaystyle 0=\sum _{P\in C}{0[P]}}$ is the unique reduced divisor belonging to the identity element of $J(C)$. Its Mumford representation is ${\displaystyle u(x)=1}$ and ${\displaystyle v(x)=0}$. Going back and forth between reduced divisors and their Mumford representation is now an easy task. For example, consider the hyperelliptic curve ${\displaystyle C:y^{2}=x^{5}-4x^{4}-14x^{3}+36x^{2}+45x=x(x+1)(x-3)(x+3)(x-5)}$ of genus 2 over the real numbers. We can find the following points on the curve ${\displaystyle P=(1,8)}$, ${\displaystyle Q=(3,0)}$ and ${\displaystyle R=(5,0)}$. Then we can define reduced divisors ${\displaystyle D=[P]+[Q]-2[O]}$ and ${\displaystyle D'=[P]+[R]-2[O]}$. The Mumford representation of $D$ consists of polynomials $u$ and $v$ with ${\displaystyle \deg(v)<\deg(u)\leq g=2}$ and we know that the first coordinates of $P$ and $Q$, i.e. 1 and 3, must be zeroes of $u$. Hence we have ${\displaystyle u(x)=(x-1)(x-3)=x^{2}-4x+3}$. As ${\displaystyle P=(1,v(1))}$ and ${\displaystyle Q=(3,v(3))}$ it must be the case that ${\displaystyle v(1)=8}$ and ${\displaystyle v(3)=0}$ and thus $v$ has degree 1. There is exactly one polynomial of degree 1 with these properties, namely ${\displaystyle v(x)=-4x+12}$. Thus the Mumford representation of $D$ is ${\displaystyle u(x)=x^{2}-4x+3}$ and ${\displaystyle v(x)=-4x+12}$. In a similar fashion we can find the Mumford representation ${\displaystyle (u',v')}$ of $D'$, we have ${\displaystyle u'(x)=(x-1)(x-5)=x^{2}-6x+5}$ and ${\displaystyle v(x)=-2x+10}$. If a point $P_i=(x_i,y_i)$ appears with multiplicity n, the polynomial v needs to satisfy ${\displaystyle \left({\frac {d}{dt}}\right)^{j}\left[v(x)^{2}+v(x)h(x)-f(x)\right]_{|_{x=x_{i}}}=0}$ for ${\displaystyle 0\leq j\leq n_{i}-1}$.

Cantor's algorithm

There is an algorithm which takes two reduced divisors $D_{1}$ and $D_{2}$ in their Mumford representation and produces the unique reduced divisor $D$, again in its Mumford representation, such that $D$ is equivalent to ${\displaystyle D_{1}+D_{2}}$.^[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 $h(x) = 0$, the general case is due to Koblitz. The input is two reduced divisors ${\displaystyle D_{1}=(u_{1},v_{1})}$ and ${\displaystyle D_{2}=(u_{2},v_{2})}$ in their Mumford representation of the hyperelliptic curve ${\displaystyle C:y^{2}+h(x)y=f(x)}$ of genus $g$ over the field $K$. The algorithm works as follows

1. Using the extended Euclidean algorithm compute the polynomials ${\displaystyle d_{1},e_{1},e_{2}\in K[x]}$ such that ${\displaystyle d_{1}=\gcd(u_{1},u_{2})}$ and ${\displaystyle d_{1}=e_{1}u_{1}+e_{2}u_{2}}$.
2. Again with the use of the extended Euclidean algorithm compute the polynomials ${\displaystyle d,c_{1},c_{2}\in K[x]}$ with ${\displaystyle d=\gcd(d_{1},v_{1}+v_{2}+h)}$ and ${\displaystyle d=c_{1}d_{1}+c_{2}(v_{1}+v_{2}+h)}$.
3. Put ${\displaystyle s_{1}=c_{1}e_{1}}$, ${\displaystyle s_{2}=c_{1}e_{2}}$ and ${\displaystyle s_{3}=c_{2}}$, which gives ${\displaystyle d=s_{1}u_{1}+s_{2}u_{2}+s_{3}(v_{1}+v_{2}+h)}$.
4. Set ${\displaystyle u={\frac {u_{1}u_{2}}{d^{2}}}}$ and ${\displaystyle v={\frac {s_{1}u_{1}v_{2}+s_{2}u_{2}v_{1}+s_{3}(v_{1}v_{2}+f)}{d}}\mod u}$.
5. Set ${\displaystyle u'={\frac {f-vh-v^{2}}{u}}}$ and ${\displaystyle v'=-h-v\mod u'}$.
6. If ${\displaystyle \deg(u')>g}$, then set ${\displaystyle u=u'}$ and ${\displaystyle v=v'}$ and repeat step 5 until ${\displaystyle \deg(u')\leq g}$.
7. Make $u'$ monic by dividing through its leading coefficient.
8. Output ${\displaystyle D=(u',v')}$.

The proof that the algorithm is correct can be found in .^[5]

Example

As an example consider the curve

${\displaystyle C:y^{2}=x^{5}-4x^{4}-14x^{3}+36x^{2}+45x=x(x+1)(x-3)(x+3)(x-5)}$

of genus 2 over the real numbers. For the points

${\displaystyle P=(1,8)}$, ${\displaystyle Q=(3,0)}$ and ${\displaystyle R=(5,0)}$

and the reduced divisors

${\displaystyle D_{1}=[P]+[Q]-2[O]}$ and ${\displaystyle D_{2}=[P]+[R]-2[O]}$

we know that

${\displaystyle (u_{1}=x^{2}-4x+3,v_{1}=-4x+12)}$, and

${\displaystyle (u_{2}=x^{2}-6x+5,v_{2}=-2x+10)}$

are the Mumford representations of $D_{1}$ and $D_{2}$ respectively.

We can compute their sum using Cantor's algorithm. We begin by computing

${\displaystyle d_{1}=\gcd(u_{1},u_{2})=x-1}$, and

${\displaystyle d_{1}=e_{1}u_{1}+e_{2}u_{2}}$

for ${\displaystyle e_{1}={\frac {1}{2}}}$, and ${\displaystyle e_{2}=-{\frac {1}{2}}}$.

In the second step we find

${\displaystyle d=\gcd(d_{1},v_{1}+v_{2}+h)=\gcd(x-1,-6x+22)=1}$ and

${\displaystyle 1=c_{1}d_{1}+c_{2}(v_{1}+v_{2}+h)}$

for ${\displaystyle c_{1}={\frac {3}{8}}}$ and ${\displaystyle c_{2}={\frac {1}{16}}}$.

Now we can compute

${\displaystyle s_{1}=c_{1}e_{1}={\frac {3}{16}}}$,

${\displaystyle s_{2}=c_{1}e_{2}=-{\frac {3}{16}}}$ and

${\displaystyle s_{3}=c_{2}={\frac {1}{16}}}$.

So

${\displaystyle u={\frac {u_{1}u_{2}}{d^{2}}}=u_{1}u_{2}=x^{4}-10x^{3}+32x^{2}-38x+15}$ and

${\displaystyle v={\frac {s_{1}u_{1}v_{2}+s_{2}u_{2}v_{1}+s_{3}(v_{1}v_{2}+f)}{d}}\mod u}$

${\displaystyle ={\frac {1}{16}}(x^{5}-4x^{4}-8x^{3}-10x^{2}+119x+30)\mod u}$

${\displaystyle ={\frac {1}{4}}(5x^{3}-41x^{2}+83x-15)}$.

Lastly we find

${\displaystyle u'={\frac {f-v^{2}}{u}}={\frac {1}{16}}(-25x^{2}+176x-15)}$ and

${\displaystyle v'=-v\mod u'=-{\frac {72}{125}}(17x-5)}$.

After making $u'$ monic we conclude that

${\displaystyle D=(-25x^{2}+176x-15,-{\frac {72}{125}}(17x-5))}$

is equivalent to ${\displaystyle D_{1}+D_{2}}$.

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

${\displaystyle C:y^{2}=f(x)}$

and two reduced divisors

${\displaystyle D_{1}=[P]+[Q]-2[O]}$ and

${\displaystyle D_{2}=[R]+[S]-2[O]}$.

Assume that

${\displaystyle P,Q\not ={\overline {R}},{\overline {S}}}$,

this case has to be treated separately. There is exactly 1 cubic polynomial

${\displaystyle a(x)=a_{0}x^{3}+a_{1}x^{2}+a_{2}x+a_{3}}$

going through the four points

${\displaystyle P,Q,R,S}$.

Note here that it could be possible that for example $P=Q$, hence we must take multiplicities into account. Putting ${\displaystyle y=a(x)}$ we find that

${\displaystyle y^{2}=f(x)=a^{2}(x)}$

and hence

${\displaystyle f(x)-a^{2}(x)=0}$.

As ${\displaystyle f(x)-a^{2}(x)}$ is a polynomial of degree 6, we have that ${\displaystyle f(x)-a^{2}(x)}$ has six zeroes and hence $a(x)$ has besides ${\displaystyle P,Q,R,S}$ two more intersection points with $C$, call them $T$ and $U$, with ${\displaystyle T\not ={\overline {U}}}$. Now, ${\displaystyle P,Q,R,S,T,U}$ are intersection points of $C$ with an algebraic curve. As such we know that the divisor

${\displaystyle D=[P]+[Q]+[R]+[S]+[T]+[U]-6[O]}$

is principal which implies that the divisor

${\displaystyle [P]+[Q]+[R]+[S]-4[O]}$

is equivalent to the divisor

${\displaystyle -([T]+[U]-2[O])}$.

Furthermore, the divisor

${\displaystyle [P]+[{\overline {P}}]-2[O]}$

is principal for every point ${\displaystyle P=(a,b)}$ on $C$ as it comes from the rational function ${\displaystyle b(x)=x-a}$. This gives that ${\displaystyle -([P]-[O])}$ and ${\displaystyle [{\overline {P}}]-[O]}$ are equivalent. Combining these two properties we conclude that

${\displaystyle D_{1}+D_{2}=([P]+[Q]-2[O])+([R]+[S]-2[O])}$

is equivalent to the reduced divisor

${\displaystyle [{\overline {T}}]+[{\overline {U}}]-2[O]}$.

In a picture this looks like Figure 2. It is possible to explicitly compute the coefficients of $a(x)$, in this way we can arrive at explicit formulas for adding two reduced divisors.

Figure 2: Example of adding two elements of the Jacobian

References

1. Isabelle Déchène, The Picard Group, or how to build a group from a set
2. Alfred J. Menezes, Yi-Hong Wu, Robert J. Zuccherato, An elementary introduction to hyperelliptic curves, page 15
3. Alfred J. Menezes, Yi-Hong Wu, Robert J. Zuccherato, An elementary introduction to hyperelliptic curves, page 20
4. Alfred J. Menezes, Yi-Hong Wu, Robert J. Zuccherato, An elementary introduction to hyperelliptic curves, page 22–27
5. 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.
6. Frank Leitenberger, About the Group Law for the Jacobi Variety of a Hyperelliptic Curve
7. T. Lange (2005). "Formulae for Arithmetic on Genus $2$ Hyperelliptic Curves". Applicable Algebra in Engineering, Communication and Computing. 15: 295–328. doi:10.1007/s00200-004-0154-8.