Modular equations for hyperelliptic curves

P. Gaudry and É. Schost

LIX – GAGE École polytechnique 91128 Palaiseau, France

                        {gaudry@lix, schost@gage}.polytechnique.fr

July 15, 2002

Abstract

We define modular equations describing the ℓ-torsion subgroups of the Jacobian of a hyperelliptic curve. Over a finite base field, we prove factorization properties that extend the well-known results used in Atkin’s improvement of Schoof’s genus 1 point counting algorithm.

2000 Mathematics Subject Classification: Primary 11Y40; Secondary 11G20, 11Y16.

Introduction

Modular equations relating invariants of ℓ-isogenous elliptic curves are a fundamental tool in computational arithmetic geometry. A great effort has been devoted to obtain equations sparser or with smaller coefficients than the classical polynomials Φ_{ℓ} [12], so nowadays these equations can be computed efficiently even for quite large ℓ. One of their important applications is the determination of the cardinality of an elliptic curve defined over a finite field [23]: the best method to date, at least for prime finite fields, is the Schoof-Elkies-Atkin algorithm in which the ℓ-torsion structure is widely used.

Nevertheless, very little is known about similar equations for higher genus curves. Since the hyperelliptic case is the best suited for computations, we restrict to this situation. Our goal in this article is then twofold:

• We define modular equations for hyperelliptic curves, without appealing to modular forms. In the particular case of genus 1, our equations coincide with those introduced by Charlap, Cooley and Robbins in [11].

• When the base field is finite, we prove that the well-known factorization properties of genus 1 modular equations extend to our higher genus construction. This makes them amenable for use in higher genus extensions of the Atkin improvement of Schoof’s initial algorithm [26].

Here is a brief overview of our construction. Consider an hyperelliptic curve C of genus g, Jac(C) its Jacobian, and ℓ a prime. The quotient of the Jacobian by a subgroup of order ℓ is an abelian variety ℓ-isogenous to Jac(C), but in genus greater than 1, it is in general not the Jacobian of a curve. General abelian varieties are more intricate to handle than Jacobians of curves, for which invariants can be easily computed, so we rather study directly the ℓ-torsion subgroup of the Jacobian. Our modular equations are thus defined using the group structure of the ℓ-torsion subgroup.

More precisely, these equations are univariate polynomials whose roots are in correspondence with the cyclic subgroups of the ℓ-torsion group. This definition avoids the use of modular forms, so it is valid over any perfect field. The construction is very similar to that of resolvants in Galois theory; as such, when the base field is finite, the factorization patterns of the modular equations are very specific, and carry enough information to be of use in higher genus Schoof point-counting algorithms. As an example, we have detailed the relationship between the 3-torsion modular equation of a genus 2 curve and the cardinality of its Jacobian modulo 3. These results are now used for point-counting within Magma’s hyperelliptic curve package [1].

The paper is organized as follows. In Section 1, we precise the notations used in the sequel. The modular equations are defined in Section 2, where we also give their basic properties and detail the example of genus 1. In Section 3, we prove that the modular equations have the expected specialization properties. This is crucial for the computational point of view, which is studied in Section 4. In Section 5, we finally consider the finite field case, and show how the factorization patterns of our modular equations extend the well-known case of genus 1; we apply this for the point-counting problem.

Acknowledgments. We thank François Morain for his numerous comments and suggestions. We are grateful to John Boxall for giving us references about the Manin-Mumford conjecture. The heaviest computations were done on the machines of the CNRS – École polytechnique MEDICIS computation center [2], using the Magma computer algebra system [1]. The second author is a member of the TERA project [3].

1 Notations

Let k be a perfect field of characteristic different from 2 and C a genus g hyperelliptic curve defined over k. We suppose that the affine part of C is defined by the equation y^{2} = f(x), with f monic of degree 2g + 1 and for simplicity, we shall say that C is the curve defined by y^{2} = f(x). The unique point at infinity on C is denoted by ∞.

We also assume that the characteristic of k is different from 2g + 1, so that we can transform f(x) into a polynomial whose coefficient in x^{2g} is zero. This simplification is similar to what is often done in genus 1 when taking an equation of the form y^{2} = x^{3} + Ax + B. In principle, our results also hold in characteristic 2g + 1, but with different equations.

We denote the Jacobian of C by Jac(C). This is a projective variety defined over k; the canonical injection C → Jac(C) associates to P ∈ C the divisor class of P − ∞; it is also defined over k.

If K is an extension field of k, we may distinguish the curves defined on k and K by y^{2} = f(x), by denoting them C/k and C/K. Then the injection C/K → Jac(C/K) extends the injection C/k → Jac(C/k), and the group law on Jac(C/K) extends that of Jac(C/k).

In particular, let \overline{k} be an algebraic closure of k. Then for a prime ℓ, we will denote by Jac[ℓ] the subgroup of ℓ-torsion elements of Jac(C/\overline{k}).

Let τ be the hyperelliptic involution on C/\overline{k}, and let ι denote the injection C/\overline{k} → Jac(C/\overline{k}). As a consequence of the Riemann-Roch theorem, any element in Jac(C/\overline{k}) can be uniquely represented by a divisor of the form D = ∑_{1≤j≤r} ι(P_{j}) with the following properties:

1. all P_{j} are points on the affine part of C/\overline{k},

2. P_{j} ≠ τ(P_{j′}) for all j ≠ j′,

3. r is at most g.

The integer r is called the weight of D.

Let D and {P_{j}}_{1≤j≤r} be as above; since the points P_{j} are not at infinity, we may take P_{j} = (x_{j}, y_{j}, 1). Then the Mumford-Cantor representation of D [24, 9] is defined by

D = ⟨u(x), v(x)⟩ = ⟨x^{r} + u_{r−1}x^{r−1} + ⋯ + u_{0}, v_{r−1}x^{r−1} + ⋯ + v_{0}⟩,

where u = ∏_{1≤j≤r}(x − x_{j}) and v(x_{j}) = y_{j} holds with suitable multiplicities, so that u divides v^{2} − f. Since k is perfect, the divisor D is defined over a field K containing k if and only if the polynomials u and v have coefficients in K.

For j in 0, …, r − 1, we will denote by u_{j}(D) (resp. v_{j}(D)) the coefficient u_{j} (resp. v_{j}) in this representation.

2 Modular equations

2.1 Definition

Let ℓ be an odd prime different from the characteristic of k. In this paragraph, we define the ℓ-th modular equation of a genus g hyperelliptic curve C defined over k.

To this end, we consider the ℓ-torsion divisors in Jac(C/\overline{k}). The assumption that ℓ differs from the characteristic of k implies that the number of ℓ-torsion divisors of non-zero weight is ℓ^{2g} − 1 [21]. From now on, we assume that all these divisors have weight exactly g; see Subsection 2.3 for the relevance of this assumption.

Genericity Assumption All non-zero ℓ-torsion divisors in Jac(C/\overline{k}) have weight g.

Let D be an ℓ-torsion divisor. The divisors

⟨D⟩ = \{− [\frac{ℓ − 1}{2}] D, …, −D, 0, D, …, [\frac{ℓ − 1}{2}] D\}

form a cyclic subgroup of cardinality ℓ in Jac[ℓ]. Our objective is to be able to “separate” these subgroups, using only algebraic constructions. To this effect we choose a function t_{ℓ}(D) with values in \overline{k}, which takes a constant value on each of the subgroups ⟨D⟩. Our modular equations may then be thought as a minimal polynomial of t_{ℓ}.

Precisely, we define t_{ℓ} as the following sum:

t_{ℓ}(D) = ∑_{1≤i≤ \frac{ℓ−1}{2}} u_{g−1}([i]D).  (1)

Our genericity assumption implies that this sum is well-defined for all non-zero ℓ-torsion divisors D. Note that [−i]D and [i]D have the same u_{g−1}-coordinate, so even though we restrict the number of summands to (ℓ − 1)/2, t_{ℓ}(D) depends only on the subgroup generated by D, as requested.

We next define the polynomial χ_{ℓ} ∈ \overline{k}[T], whose roots are the values taken by t_{ℓ} on the non-zero ℓ-torsion divisors:

χ_{ℓ} = ∏_{D∈Jac[ℓ]\{0}} (T − t_{ℓ}(D)).

The polynomial χ_{ℓ} is a (ℓ − 1)-th power in \overline{k}[T]. Indeed Jac[ℓ] \ \{0\} can be written as the disjoint union of the \frac{ℓ^{2g}−1}{ℓ−1} sets ⟨D⟩ \ \{0\}, and the function t_{ℓ}(D) takes a constant value on each part of this partition.

We now show that χ_{ℓ} is actually in k[T]. Let σ be in Gal(\overline{k}/k). If D is any divisor, σ(u_{g−1}(D)) = u_{g−1}(σ(D)). Also, σ commutes with the group law, whence σ([i]D) = [i]σ(D), so σ induces a permutation among the non-zero ℓ-torsion divisors. If D is such a divisor, then equality

σ(t_{ℓ}(D)) = t_{ℓ}(σ(D))

obviously holds. Since σ permutes the ℓ-torsion divisors, this equality shows that χ_{ℓ} is left invariant by σ, so χ_{ℓ} is in k[T]. Since k is a perfect field, and χ_{ℓ} is a (ℓ − 1)-th power in \overline{k}[T], there exists a polynomial Ξ_{ℓ} with coefficients in k such that χ_{ℓ} = Ξ_{ℓ}^{ℓ−1}.

Definition 1 The unique monic polynomial Ξ_{ℓ} such that χ_{ℓ} = Ξ_{ℓ}^{ℓ−1} is called the ℓ-th modular equation of C.

The polynomial Ξ_{ℓ} has degree \frac{ℓ^{2g}−1}{ℓ−1}. To emphasize the dependence on the curve C, it may also be denoted by Ξ_{ℓ}(C).

The rest of this article is devoted to describe the main properties of these equations, how to compute them and how to use them for cardinality computation, in the case when k is a finite field.

Remark 1 Our choice of the function t_{ℓ} is arbitrary. In Section 5, we show that the interesting case is when Ξ_{ℓ} is squarefree, which happens when t_{ℓ} takes distinct values on distinct cyclic subgroups. Unfortunately, this will not be the case for all curves; then, an alternative choice of t_{ℓ} may solve the problem:

Instead of considering the sum of the u_{g−1}-coordinates of half of the divisors in the subgroup, we choose some integer k and form the sum of the k-th power of any linear combination of all the coordinates (u, v). Then, we might have to extend the summation in Equation (1) to all elements in the subgroup ⟨D⟩, since not all coordinates are negation-invariant. The subsequent results follow in a similar manner for such alternative constructions.

Yet in practice, choosing the coordinate u_{g−1} yields the polynomial with smallest coefficients when working over ℚ, and in most of our experiments in genus 1 and 2, this polynomial turned out to be squarefree, as requested.

Remark 2 In the sequel, we will often consider curves with generic coefficients. Thus we define for once the generic curve of genus g as the curve of equation

C_{g} : y^{2} = x^{2g+1} + F_{2g−1}x^{2g−1} + ⋯ + F_{0},

over the rational function field ℚ(F_{0}, …, F_{2g−1}). In this case, the polynomial Ξ_{ℓ} belongs to ℚ(F_{0}, …, F_{2g−1})[T], and satisfies the following homogeneity property.

Theorem 1 The ℓ-th modular equation of the curve C_{g} is weighted homogeneous, when giving weight 1 to T and weight 2g + 1 − i to F_{i} for i = 0, …, 2g − 1.

Proof. Let λ be a non-zero rational, and let C̃_{g} be the curve defined by

y^{2} = x^{2g+1} + { \atop F_{2g−1}}x^{2g−1} + ⋯ + F̃_{0},

where F̃_{i} = λ^{2g+1−i}F_{i}, for i = 1, …, 2g − 1. Then the map φ : C_{g} → C̃_{g} defined by φ(x, y) = (λx, λ^{2g+1}y) is an isomorphism between C_{g} and C̃_{g}. This isomorphism extends to an isomorphism between Jac(C_{g}) and Jac(C̃_{g}), which acts as follows in Mumford-Cantor’s representation:

(u_{0}, …, u_{g−1}, v_{0}, …, v_{g−1}) ↦ (λ^{g}u_{0}, …, λu_{g−1}, λ^{2g+1}v_{0}, …, λ^{g+2}v_{g−1}).

Given an ℓ-torsion divisor D on Jac(C_{g}), the value t_{ℓ}(D) is sent to λt_{ℓ}(D). Thus

Ξ_{ℓ}(F_{0}, …, F_{2g−1}, t_{ℓ}) = 0 ⟺ Ξ_{ℓ}(λ^{2g+1}F_{0}, …, λ^{2}F_{2g−1}, λt_{ℓ}) = 0.

This proves the theorem. □

The weighted homogeneity implies that not all monomials appear in the modular equation for the generic curve. As a consequence, our modular equations are somewhat sparse, and we shall see below that for elliptic curves they provide a much smaller alternative to the classical Φ_{ℓ} modular polynomials.

Remark 3 In our formalism, the modular equation for 2-torsion Ξ_{2} is ill-defined in genus greater than 1. Indeed, the genericity assumption for 2-torsion is never satisfied, since the 2g + 1 roots of the defining polynomial f(x) give the abscissae of 2g + 1 weight 1 divisors of 2-torsion. In the particular case of elliptic curves, we can set Ξ_{2} = f.

2.2 The elliptic case

We illustrate our definition on an elliptic curve E, given by an equation y^{2} = f(x), with f monic of degree 3. In genus 1, the genericity assumption is always verified, since the only divisor whose weight is not maximal is zero.

If P = (x, y) is a point on E and i a positive integer, the coordinates of [i]P are rational functions of P, see [29]:

[i]P = (\frac{ϕ_{i}(P)}{ψ_{i}(P)^{2}} , \frac{ω_{i}(P)}{ψ_{i}(P)^{3}} ) .

The polynomials ϕ_{i}(P), ψ_{i}(P)^{2}, and also ψ_{i}(P) if i is odd, are polynomials in x only. To follow the notation of the previous subsection, we see them as polynomials in the variable T.

Given an odd prime ℓ, the abscissae of the ℓ-torsion points are the roots of ψ_{ℓ}. Let P be such a point; for i in 1, …, \frac{ℓ−1}{2}, the denominator in the rational function

(\frac{ϕ_{i}(P)}{ψ_{i}(P)^{2}} )

is coprime to ψ_{ℓ}. The image of this rational function modulo ψ_{ℓ} is a polynomial h_{i,ℓ} in k[T] which gives the abscissa of [i]P in terms of the abscissa of P, for P of ℓ-torsion. Then, for all ℓ-torsion points P, t_{ℓ}(P) is given by the sum

t_{ℓ}(P) = ∑_{1≤i≤ \frac{ℓ−1}{2}} h_{i,ℓ}(x(P)).

The polynomial χ_{ℓ} is thus the characteristic polynomial of ∑_{1≤i≤ \frac{ℓ−1}{2}} h_{i,ℓ} modulo ψ_{ℓ}, and the modular equation Ξ_{ℓ} ∈ k[T] is the (ℓ − 1)-th root of χ_{ℓ}.

Let us take f = x^{3} + F_{1}x + F_{0}, defining what we called the generic curve of genus 1 over ℚ(F_{0}, F_{1}). Then the first values of Ξ_{ℓ} are:

Ξ_{3} = T^{4} + 2F_{1}T^{2} + 4F_{0}T − \frac{1}{3}F_{1}^{2},
Ξ_{5} = T^{6} + 20F_{1}T^{4} + 160F_{0}T^{3} − 80F_{1}^{2}T^{2} − 128F_{1}F_{0}T − 80F_{0}^{2},
Ξ_{7} = T^{8} + 84F_{1}T^{6} + 1512F_{0}T^{5} − 1890F_{1}^{2}T^{4} − 9072F_{1}F_{0}T^{3} + (−21168F_{0}^{2} + 644F_{1}^{3})T^{2}
+5832F_{1}^{2}F_{0}T − 567F_{1}^{4},
Ξ_{11} = T^{12} + 550F_{1}T^{10} + 27500F_{0}T^{9} − 103125F_{1}^{2}T^{8} − 1650000F_{1}F_{0}T^{7} + (−13688400F_{0}^{2}+
645700F_{1}^{3})T^{6} + 20625000F_{1}^{2}F_{0}T^{5} + (35793120F_{1}F_{0}^{2} − 11407385F_{1}^{4})T^{4}+
(34041920F_{0}^{3} − 58614160F_{1}^{3}F_{0})T^{3} + (−175832976F_{1}^{2}F_{0}^{2} − 2177802F_{1}^{5})T^{2}+

(−235016704F_{1}F_{0}^{3} + 1351692F_{1}^{4}F_{0})T − 110680064F_{0}^{4} + 6297984F_{1}^{3}F_{0}^{2} − 321651F_{1}^{6}.

These polynomials were already considered by Charlap, Cooley and Robbins in [11], where the authors constructed them via modular forms. Our modular equations are a generalization to higher genus.

Remark 4 Except for Ξ_{3} for which a factor \frac{1}{3} occurs, there are no denominators in the coefficients of the modular equations of the generic elliptic curve. This fact is proven in [11] using properties of modular forms. In higher genus we do not know a priori whether there are denominators in the modular equations of the generic curves. The computation in Section 4 shows that the modular equation Ξ_{3} of the genus 2 generic curve does not have any denominator, but we do not expect this to be true in general.

2.3 Relevance of the genericity assumption

As mentioned in the previous subsection, the genericity assumption is satisfied in genus 1 for all curves, for all torsion indices coprime to the characteristic of the base field.

This condition is also satisfied for all genus 2 curves for 3-torsion. To see this, consider a genus 2 curve C. A divisor with non maximal weight is of the form P − ∞ for some point P ∈ C. Then the equality [3](P − ∞) = 0 can be rewritten as [2](P − ∞) = −(P − ∞), which implies that P = ∞ by the Riemann-Roch theorem. Thus except zero, all 3-torsion divisors have weight 2.

More generally, the genericity assumption is closely related to the Manin-Mumford conjecture which states that the Jacobian of a curve over the complex field contains only finitely many torsion elements of weight 1. More generally, Lang’s conjecture, which is now known to be true [17, p. 435], implies that the Jacobian of a given curve over the complex field contains only finitely many torsion elements of non-maximal weight, as soon as this Jacobian is simple. As a consequence, for a given curve with simple Jacobian, the number of primes ℓ for which the genericity assumption does not hold is finite, hence the name.

Note finally that this condition is true for all ℓ for the curve of genus 2 defined by y^{2} = x^{5} + 5x^{3} + x, see [7]. Using the specialization theorem given in Section 3, we deduce that the genericity assumption is also true for all ℓ for the generic curve of genus 2.

3 Specialization properties

In the elliptic curve point-counting methods, a widely used strategy is to compute modular equations over the rationals and then reduce them modulo the characteristic of the base field. In this section, we want to legitimate this approach for our modular equations. Our purpose is thus to prove the intuitive result that the reduction of the modular equations of a curve C coincide with the modular equations of the reduction of C.

We are interested in both specializing the coefficients of a curve defined over a rational function field, and also in reducing the coefficients of a curve defined over a number field. Thus we work in the setting of local and global fields, which will help encompass both notions. Throughout this section, we assume once and for all that all the fields are perfect.

We recall below the definition of reduction and good reduction of a curve defined on a local or a global field. Then Theorem 2 proves that if C is a curve with good reduction, and if the reduced curve satisfies the genericity assumption for some prime ℓ, then this is also the case for C and its ℓ-modular equation specializes as expected; the main ingredient of the proof is the injectivity of the reduction of the ℓ-torsion, as proven for instance in [17]. We will use Theorem 2 for computational purposes in Section 4.

First, a few notations are necessary. If (K, v) is a non-Archimedian local field, we denote by

R_{K} = {a ∈ K, v(a) ≤ 1}, 𝔪_{K} = {a ∈ K, v(a) < 1}

respectively the ring of integers of K and its maximal ideal.

With these notations, let C : y^{2} = f(x) be a hyperelliptic curve defined over K, such that f has its coefficients in R_{K}. We say that C has good reduction if 2disc(f) is not in 𝔪_{K}. In this case, the curve defined by the reduction of y^{2} = f(x) modulo 𝔪_{K} has the same genus as C. This curve is called the reduction of C; its Jacobian is the reduction of the Jacobian of C modulo 𝔪_{K}, see [22].

If now K is a global field and v a non-Archimedian valuation of K, the completion K of K at v is a local field. Thus the above discussion enables us to define the notion of good reduction at v of a curve C defined over K: if C is defined by an equation with coefficients in K ∩ R_{K}, C has good reduction at v if C/K has good reduction. Then the specialization properties are stated as follows.

Theorem 2 Let K be a global field, and v a non-Archimedian valuation of K. Let K be the completion of K at v, R_{K} its ring of integers, 𝔪_{K} its maximal ideal and k the residual field R_{K}/𝔪_{K}. Let C be a genus g hyperelliptic curve defined over K, and ℓ an odd prime different from the characteristic of k.

Assume that C is defined by an equation with coefficients in K ∩ R_{K}, that C has good reduction at v, and that the reduced curve \overline{C} satisfies the genericity assumption for the prime ℓ. Then C satisfies the genericity assumption for ℓ, all coefficients of Ξ_{ℓ}(C) are in K ∩ R_{K} and Ξ_{ℓ}(\overline{C}) = Ξ_{ℓ}(C) modulo 𝔪_{K}.

Before proving the theorem, a few comments are in order. Theorem 2 applies to specializations at non-Archimedian places of number fields, so for instance it allows for the reduction modulo prime numbers of modular equations with rational coefficients. The second obvious application is the specialization of modular equations with coefficients in univariate function fields defined over a perfect field.

We considered in Section 2 the case of the generic curve of genus g, which is defined over the rational function field ℚ(F_{0}, …, F_{2g−1}) by the equation

y^{2} = x^{2g+1} + F_{2g−1}x^{2g−1} + ⋯ + F_{0}.

Its modular equations have coefficients in ℚ(F_{0}, …, F_{2g−1}). For g > 1, the fraction field of ℚ[[F_{0}, …, F_{2g−1}]] is not a local field, so Theorem 2 does not apply directly, i.e. it does not allow to specialize F_{0}, …, F_{2g−1} at once. Yet we may circumvent this difficulty. Consider the isomorphism ℚ(F_{0}, …, F_{2g−1}) ≃ ℚ(F_{0}, …, F_{2g−2})(F_{2g−1}). The right-hand side is a univariate function field over ℚ(F_{0}, …, F_{2g−2}), for which Theorem 2 applies; i.e. specializing F_{2g−1} is allowed. Iterating this process allows to successively specialize F_{2g−2}, …, F_{0}, as requested.

Proof of Theorem 2. Since K is an extension field of K, the modular equations Ξ_{ℓ}(C/K) and Ξ_{ℓ}(C/K) coincide. Thus it is enough to prove the result for the curve C/K, defined over the local field K.

Let 𝔎 be an algebraic closure of K, let Jac[ℓ] be the ℓ-torsion divisors on Jac(C/𝔎) and let ℑ be the canonical injection C/𝔎 → Jac(C/𝔎). Each divisor D ≠ 0 in Jac[ℓ] can be uniquely written D = ∑_{1≤j≤r(D)} ℑ(P_{j}^{D}), where P_{1}^{D}, …, P_{r(D)}^{D} are points in C/𝔎, not at infinity and not pairwise conjugate, and where r(D) is at most g.

We let L be a finite extension of K, such that all ℓ-torsion divisors D and all points P_{1}^{D}, …, P_{r(D)}^{D} are L-rational. Then L is a non-Archimedian local field, for a valuation that extends that of K, and that is still denoted by v. We denote by R_{L} and 𝔪_{L} the ring of integers of L and its maximal ideal, and the reduction modulo 𝔪_{L} is denoted by a bar. We still denote by ℑ the canonical injection C/L → Jac(C/L).

The curve C/L has good reduction; the reduced curve, defined over the residual field of L, is still denoted by \overline{C}; the canonical injection \overline{C} → Jac(\overline{C}) is denoted by ι. Note that the residual fields of K and L have the same characteristic.

Let D be a ℓ-torsion divisor on Jac(C/L). We simplify the notation D = ∑_{1≤j≤r(D)} ℑ(P_{j}^{D}), writing D = ∑_{1≤j≤r} ℑ(P_{j}) instead. Then, due to the good reduction of C, the following holds:

\overline{D} = \overline{∑_{1≤j≤r} ℑ(P_{j})} = ∑_{1≤j≤r} \overline{ℑ(P_{j})} = ∑_{1≤j≤r} ι (\overline{P_{j}}) .

Moreover, \overline{D} is a ℓ-torsion divisor on Jac(\overline{C}). Since the characteristic of k is different from ℓ, Theorem C.2.6 in [17] shows that \overline{D} is not zero. Using the genericity assumption on \overline{C}, this shows that \overline{D} has weight g, which implies that r = g, so C satisfies the genericity assumption too. This also implies that all points \overline{P_{j}} are on the affine part of \overline{C}.

Let us write P_{j} = (x_{j}, y_{j}, z_{j}), with all coordinates in the ring of integers R_{L}, and at least one of them not in 𝔪_{L}. By the above remark, z_{j} does not reduce to zero modulo 𝔪_{L}, so v(z_{j}) = 1. Dividing by z_{j}, we write P_{j} as (X_{j}, Y_{j}, 1), with coordinates in R_{L}; then \overline{P_{j}} is given by (\overline{X_{j}}, \overline{Y_{j}}, 1). Taking all points P_{j} into account, this shows that u_{g−1}(D) is in R_{L}, and a short calculation also gives that u_{g−1} (\overline{D}) = \overline{u_{g−1} (D)}. Recall now that the function t_{ℓ}(D) is defined as

t_{ℓ}(D) = ∑_{1≤i≤ \frac{ℓ−1}{2}} u_{g−1}([i]D),

so that t_{ℓ}(D) is in R_{L}. Since \overline{[i]D} = [i]\overline{D}, we finally conclude that \overline{t_{ℓ}(D)} = t_{ℓ}(\overline{D}).

The set of non-zero ℓ-torsion divisors on C reduces to the set of non-zero ℓ-torsion divisors on \overline{C}, so χ_{ℓ}(C) = ∏_{D∈Jac[ℓ]\\{0\}} (T − t_{ℓ}(D)) is in R_{L}[T], and (χ_{ℓ}(C) mod 𝔪_{L}) = χ_{ℓ}(\overline{C}). Since C is defined over K, χ_{ℓ}(C) is actually in R_{K}[T], and (χ_{ℓ}(C) mod 𝔪_{K}) = χ_{ℓ}(\overline{C}).

From the definition χ_{ℓ}(C) = Ξ_{ℓ}(C)^{ℓ−1}, we see that Ξ_{ℓ}(C) is also in R_{K}[T] by Gauss’ lemma. The above reduction can then be written (Ξ_{ℓ}(C)^{ℓ−1} mod 𝔪_{K}) = Ξ_{ℓ}(\overline{C})^{ℓ−1}. Since both polynomials are monic, (Ξ_{ℓ}(C) mod 𝔪_{K}) = Ξ_{ℓ}(\overline{C}). □

4 Algorithms

We consider now the question of computing the modular equations, with an emphasis on the genus 2 case. In the first subsection, we show how Cantor’s division polynomials [10] can be used to give a description of the ℓ-torsion subgroup of a hyperelliptic Jacobian in genus 2, from which its ℓ-th modular equation can be deduced; we illustrate this with examples for 3 and 5-torsion. We also present a solution by specialization techniques for 3-torsion in genus 2. The arbitrary genus case is finally addressed, using Adleman and Huang’s algorithm for computing the ℓ-torsion points on a hyperelliptic Jacobian [4].

4.1 Computing Ξ_{ℓ} in genus 2

Computing Ξ_{ℓ} is a two-stage process: first compute a representation of the ℓ-torsion divisors, then compute the modular equation using this information. This strategy was already hinted at in Subsection 2.2, where we addressed the elliptic case. In genus 1, the ℓ-torsion divisors are the roots of the elliptic division polynomials, and the modular equations come from characteristic polynomial computations modulo these division polynomials. In genus 2, the torsion divisors can be characterized using Cantor’s division polynomials [10]; the subsequent characteristic polynomial computations are analogous to the elliptic case.

The solution we present here demands further conditions on the ℓ-torsion divisors, which are generically satisfied. In Subsection 4.2, we will present a more intricate solution, but which is valid in all cases. In this subsection, C is a genus 2 curve defined over a field k by the equation y^{2} = f(x), with f of degree 5.

First step: computing the torsion divisors. We use the strategy from [13]. For a weight 2 divisor D = P_{1} + P_{2} − 2∞, the condition [ℓ]D = 0 can be restated as

[ℓ](P_{1} − ∞) = −[ℓ](P_{2} − ∞).

Let x_{1}, x_{2}, y_{1}, y_{2} be new variables, and take P_{1} = (x_{1}, y_{1}), P_{2} = (x_{2}, y_{2}). Then the Mumford-Cantor coordinates of [ℓ](P_{1} − ∞) and −[ℓ](P_{2} − ∞) are rational functions of x_{1}, x_{2}, y_{1}, y_{2} with coefficients in k. These rational functions can be derived efficiently by recursive formulae given in [10]:

[ℓ]P_{1} = ⟨x^{2} + \frac{d_{1}^{(ℓ)}(x_{1})}{d_{0}^{(ℓ)}(x_{1})}x + \frac{d_{2}^{(ℓ)}(x_{1})}{d_{0}^{(ℓ)}(x_{1})}, \frac{y_{1}e_{1}^{(ℓ)}(x_{1})}{e_{0}^{(ℓ)}(x_{1})}x + \frac{y_{1}e_{2}^{(ℓ)}(x_{1})}{e_{0}^{(ℓ)}(x_{1})}⟩ ,

where d_{0}^{(ℓ)}, d_{1}^{(ℓ)}, d_{2}^{(ℓ)}, e_{0}^{(ℓ)}, e_{1}^{(ℓ)}, e_{2}^{(ℓ)} are univariate polynomials of degrees respectively 2ℓ^{2} −1, 2ℓ^{2} −2, 2ℓ^{2} −3, 3ℓ^{2} −2, 3ℓ^{2} −2, 3ℓ^{2} −3. From now on we assume that ℓ is fixed, and drop the superscript (ℓ) for simplicity.

The genericity assumption on C can then be made explicit: in [10] it is shown that a weight 1 divisor D = (x_{1}, y_{1}) − ∞ is a ℓ-torsion divisor if and only if d_{1}(x_{1}) = d_{0}(x_{1}) = 0. Hence the genericity assumption is valid on C if and only if d_{1} and d_{0} are coprime polynomials.

If this is the case, we form the equations in x_{1}, x_{2}, y_{1}, y_{2} expressing that [ℓ](P_{1} −∞) = −[ℓ](P_{2} −∞):

\frac{d_{1}(x_{1})}{d_{0}(x_{1})} = \frac{d_{1}(x_{2})}{d_{0}(x_{2})},
\frac{d_{2}(x_{1})}{d_{0}(x_{1})} = \frac{d_{2}(x_{2})}{d_{0}(x_{2})},
\frac{y_{1}e_{1}(x_{1})}{e_{0}(x_{1})} = −\frac{y_{2}e_{1}(x_{2})}{e_{0}(x_{2})},
\frac{y_{1}e_{2}(x_{1})}{e_{0}(x_{1})} = −\frac{y_{2}e_{2}(x_{2})}{e_{0}(x_{2})}.

Further equations and inequalities must be added to this system:

y_{1}^{2} = f(x_{1}), y_{2}^{2} = f(x_{2}),
x_{1} ≠ x_{2}, d_{0}(x_{1})e_{0}(x_{1}) ≠ 0.

The equations specify that P_{1} and P_{2} are indeed points on the curve. The first inequality is necessary to discard the obvious solutions P_{1} = −P_{2}, but may also eliminate points P_{1} such that [ℓ](P_{1}−∞) is of 2-torsion. The second inequality allows to clean the denominators, and is equivalent to the assumption that [ℓ](P_{1} − ∞) has weight 2.

Due to the symmetry in (P_{1}, P_{2}), for a general curve, this system has 2(ℓ^{2g} − 1) solutions, but this number may drop if [ℓ](P_{1} − ∞) is of 2-torsion or has weight 1, for some ℓ-torsion divisor of the form D = P_{1} + P_{2} − 2∞. Letting I_{ℓ} ⊂ k[x_{1}, x_{2}, y_{1}, y_{2}] be the ideal defining the solutions of the above system, we thus have to check that I_{ℓ} has the maximal number of solutions, i.e. 2(ℓ^{2g} − 1). To this effect, we can use standard effective elimination algorithms such as Gröbner bases [8] or geometric resolution procedures [14, 15]. We refer to [13] for a faster solution based on resultant computations, which relies on the very specific shape of the system to solve.

Whatever routine we choose, we consider from now on that we are in the favorable case of an ideal I_{ℓ} having 2(ℓ^{2g} − 1) solutions, and that, as an outcome of the elimination procedure, we can compute effectively modulo I_{ℓ}.

Second step: deducing Ξ_{ℓ}. In genus 2, the function t_{ℓ}(D) defined in Section 2 becomes

t_{ℓ}(D) = ∑_{1≤i≤ \frac{ℓ−1}{2}} u_{1}([i]D).

Roughly speaking, we want to compute t_{ℓ} modulo I_{ℓ}. To this effect, for i = 1, …, (ℓ − 1)/2, we let h_{i,ℓ} be the polynomial in k[x_{1}, x_{2}, y_{1}, y_{2}] which takes the value u_{1}([i]D) when evaluated on an ℓ-torsion divisor D. The reader may refer to Subsection 2.2 where similar polynomials are derived in genus 1.

To obtain h_{i,ℓ}, we compute the Mumford-Cantor coordinates of [i](P_{1} − ∞) + [i](P_{2} − ∞), where P_{1} (resp. P_{2}) is the point of coordinates (x_{1}, y_{1}), resp. (x_{2}, y_{2}), all computations being done modulo I_{ℓ}. These computations can be done using Cantor’s division polynomials and Cantor’s addition algorithm [9]. As such, they involve divisions modulo I_{ℓ}, which are possible in general, but may fail in unlucky cases.

We assume from now on that all these divisions can be done. In this lucky case, the polynomial χ_{ℓ} defined in Section 2 is the characteristic polynomial of ∑_{1≤i≤ \frac{ℓ−1}{2}} h_{i,ℓ} modulo I_{ℓ}; so it can be computed using linear algebra in the quotient k[x_{1}, x_{2}, y_{1}, y_{2}]/I_{ℓ}. Knowing χ_{ℓ}, we then deduce the modular equation Ξ_{ℓ} using the squarefree factorization of χ_{ℓ}. If we write

χ_{ℓ} = p_{1}^{M_{1}} ⋯ p_{s}^{M_{s}},

with all p_{i} pairwise coprime squarefree polynomials in k[T], then all M_{i} are multiples of ℓ − 1, and

Ξ_{ℓ} = p_{1}^{m_{1}} ⋯ p_{s}^{m_{s}},

with M_{i} = (ℓ − 1)m_{i} for all i. Since the base field is perfect, the squarefree factorization of χ_{ℓ} can be computed using for instance Yun’s algorithm [30].

First example: 3-torsion. For the particular case of the 3-torsion in genus 2, we already noted that the genericity assumption is always satisfied. Further simplifications arise in this case.

Consider again the equations in x_{1}, x_{2}, y_{1}, y_{2} expressing that [3](P_{1} − ∞) = −[3](P_{2} − ∞). The computation shows that all denominators in these equations are powers of f(x_{1}) and f(x_{2}); the Riemann-Roch theorem shows that these are non-zero quantities if P_{1} + P_{2} − 2∞ is of 3-torsion. In other words, the ideal I_{3} described above always has the maximal number of solutions, i.e. 2 × (3^{4} − 1) = 160.

Cantor’s division polynomials d_{0}, d_{1}, d_{2}, e_{0}, e_{1}, e_{2} for 3-torsion have degrees 17, 16, 15, 25, 25, 24. We define the ideal I_{3} ⊂ k[x_{1}, x_{2}, y_{1}, y_{2}] using these polynomials; then the definitions in Section 2 show that for 3-torsion, t_{3}(D) coincides with u_{1}(D), so χ_{3} is the characteristic polynomial of x_{1}+x_{2} modulo I_{3}, and Ξ_{3} is the square-root of χ_{3}.

As an example, if C is the genus 2 curve defined over 𝔽_{p} with p = 101009 by the equation

y^{2} = x^{5} + x^{3} − 2233x^{2} + 1944x + 21551,

then its modular equation for 3-torsion is

Ξ_{3}(T) = T^{40} + 312T^{38} + 74066T^{37} + 21549T^{36} + 98476T^{35} + 77413T^{34} + 11876T^{33}+
87429T^{32} + 62497T^{31} + 26387T^{30} + 53806T^{29} + 55344T^{28} + 3150T^{27}+
85491T^{26} + 39525T^{25} + 66578T^{24} + 43546T^{23} + 37423T^{22}+
17475T^{21} + 96511T^{20} + 45626T^{19} + 38344T^{18} + 36106T^{17} + 88202T^{16}+
80287T^{15} + 16826T^{14} + 27075T^{13} + 64347T^{12} + 84421T^{11}+
99539T^{10} + 78579T^{9} + 29813T^{8} + 30858T^{7} + 58361T^{6} + 37204T^{5}+
39712T^{4} + 98618T^{3} + 92702T^{2} + 47474T + 57754.

Second example: 5-torsion. We illustrate the case of 5-torsion with the same curve. The ideal I_{5} ⊂ 𝔽_{p}[x_{1}, x_{2}, y_{1}, y_{2}] is generated using the univariate polynomials d_{0}, d_{1}, d_{2}, e_{0}, e_{1}, e_{2} for 5-torsion, of respective degrees 49, 48, 47, 73, 73, 72. As indicated above, we apply the resolution techniques of [13], so as to obtain a basis of 𝔽_{p}[x_{1}, x_{2}, y_{1}, y_{2}]/I_{5}.

For 5-torsion in genus 2, t_{5}(D) equals u_{1}(D) + u_{1}([2]D). Taking P_{1} = (x_{1}, y_{1}), P_{2} = (x_{2}, y_{2}) and D = P_{1} + P_{2} − 2∞, we compute the Mumford-Cantor coordinates of [2]D modulo I_{5}, from which we deduce t_{5} as a function defined modulo I_{5}, its characteristic polynomial χ_{5}, and finally Ξ_{5}:

Ξ_{5}(T) = T^{156} + 100894T^{155} + 45811T^{154} + 44233T^{153} + 39740T^{152} + 95818T^{151} + 4458T^{150} + 93570T^{149}
+28550T^{148} + 1113T^{147} + 63748T^{146} + 65156T^{145} + 19143T^{144} + 19730T^{143} + 33367T^{142}+
20907T^{141} + 63820T^{140} + 51940T^{139} + 42326T^{138} + 29817T^{137} + 75942T^{136} + 59745T^{135}+
97234T^{134} + 85218T^{133} + 24915T^{132} + 16689T^{131} + 93260T^{130} + 46818T^{129} + 27999T^{128}+
93775T^{127} + 2219T^{126} + 19973T^{125} + 1129T^{124} + 52225T^{123} + 6886T^{122} + 85816T^{121}+
77152T^{120} + 12511T^{119} + 64657T^{118} + 14966T^{117} + 42288T^{116} + 90382T^{115} + 60923T^{114}+
40482T^{113} + 43464T^{112} + 61885T^{111} + 2196T^{110} + 60160T^{109} + 78999T^{108} + 88624T^{107}+
86206T^{106} + 1602T^{105} + 73726T^{104} + 27596T^{103} + 4276T^{102} + 93140T^{101} + 58403T^{100}+

1234T^{99} + 88895T^{98} + 59594T^{97} + 13604T^{96} + 6248T^{95} + 30964T^{94} + 40104T^{93} + 58036T^{92}+ 38120T^{91} + 69691T^{90} + 75816T^{89} + 22051T^{88} + 36408T^{87} + 59984T^{86} + 96659T^{85} + 35117T^{84}+ 96676T^{83} + 62595T^{82} + 51710T^{81} + 38161T^{80} + 68329T^{79} + 99009T^{78} + 10635T^{77} + 97403T^{76}+ 58767T^{75} + 74987T^{74} + 26947T^{73} + 100504T^{72} + 6849T^{71} + 50414T^{70} + 38143T^{69} + 82683T^{68}+ 24600T^{67} + 83911T^{66} + 80258T^{65} + 98589T^{64} + 76450T^{63} + 89676T^{62} + 9956T^{61} + 58260T^{60}+ 92379T^{59} + 57187T^{58} + 40082T^{57} + 33146T^{56} + 20951T^{55} + 77435T^{54} + 3376T^{53} + 67384T^{52}+ 96487T^{51} + 74090T^{50} + 65498T^{49} + 61846T^{48} + 62046T^{47} + 30397T^{46} + 18364T^{45} + 55016T^{44}+ 32487T^{43} + 94900T^{42} + 33300T^{41} + 25231T^{40} + 71704T^{39} + 59710T^{38} + 44750T^{37} + 31125T^{36}+ 10050T^{35} + 7371T^{34} + 29794T^{33} + 72166T^{32} + 14168T^{31} + 53045T^{30} + 80342T^{29} + 20690T^{28}+ 79145T^{27} + 74121T^{26} + 1983T^{25} + 37232T^{24} + 76446T^{23} + 6132T^{22} + 98206T^{21} + 94392T^{20}+ 81694T^{19} + 43792T^{18} + 60209T^{17} + 98392T^{16} + 60483T^{15} + 71502T^{14} + 94495T^{13} + 77466T^{12}+

61989T^{11} + 51160T^{10} + 65902T^{9} + 28152T^{8} + 70740T^{7} + 94924T^{6} + 4993T^{5} + 30256T^{4}+
62697T^{3} + 27820T^{2} + 55949T + 63692.

The particular case of the generic curve. We have a special interest for the generic curve of genus 2 defined over ℚ(F_{0}, F_{1}, F_{2}, F_{3}) by the equation

C_{2} : y^{2} = x^{5} + F_{3}x^{3} + F_{2}x^{2} + F_{1}x + F_{0},

and its modular equations in ℚ(F_{0}, F_{1}, F_{2}, F_{3})[T]. Computing these polynomials is a one-time job, which becomes useful in conjunction with the specialization Theorem of Section 3, as illustrated below.

The first case of interest is for 3-torsion. To compute Ξ_{3}(C_{2}), the elimination techniques mentioned above become cumbersome: the base field is now a rational function field, and we have no control on the degrees in (F_{0}, F_{1}, F_{2}, F_{3}) of the intermediate expressions we have to handle. Thus we used alternative resolution techniques, based on the work of the TERA group [3]: the algorithm we used is based on a symbolic Newton operator, which enables to compute successive approximations of Ξ_{3}(C_{2}), with increasing precisions in (F_{0}, F_{1}, F_{2}, F_{3}), starting from the data of Ξ_{3} for a curve with rational coefficients.

Using these techniques, computing Ξ_{3}(C_{2}) requires approximately 4 hours of CPU time using Magma, on a 4 GB, 500 MHz Compac DS20 processor. We mention that a direct approach based on a Gröbner basis computation fails, by lack of memory. For more details, we refer to [28].

The resulting polynomial Ξ_{3}(C_{2}) can be downloaded from the web-page of the second author

http://www.medicis.polytechnique.fr/~schost/. It has 1747 monomials with non-zero co-

efficients, belongs to ℤ[F_{0}, F_{1}, F_{2}, F_{3}][T], and is monic in T. To have an estimate of its size, here are its first coefficients:

Ξ_{3} = T^{40} + 312F_{3}T^{38} − 7904F_{2}T^{37} + (−16344F_{3}^{2} + 183488F_{1})T^{36}+
(337536F_{3}F_{2} − 4179456F_{0})T^{35} + (345456F_{3}^{3} + 464064F_{3}F_{1} − 2381088F_{2}^{2})T^{34}+
(−6044256F_{3}^{2}F_{2} − 196322688F_{3}F_{0} + 33608832F_{2}F_{1})T^{33} + ⋯

The largest coefficient in absolute value is 304960695828480.

Let now p be a prime greater than 3 and C a genus 2 curve defined over ℤ/pℤ by the equation

C : y^{2} = x^{5} + f_{3}x^{3} + f_{2}x^{2} + f_{1}x + f_{0}.

Theorem 2 shows that the polynomial Ξ_{3}(C) ∈ ℤ/pℤ[T] is obtained by substituting the values f_{i} for the indeterminates F_{i} in Ξ_{3}(C_{2}) after reducing its coefficient modulo p. We note that this solution is used within Magma’s hyperelliptic curve package [1].

Until now, we always excluded the case ℓ = p. To get a hint about the problems that can arise, we can reduce all the coefficients of Ξ_{3}(C_{2}) modulo 3, expecting some degeneracy similar to the Kronecker relations for the elliptic modular polynomials Φ_{ℓ}. We obtain

Ξ_{3}(C_{2}) ≡ (T^{4} + f_{1}T − f_{2}) (T^{12} + f_{1}T^{9} − f_{0}f_{2}T^{6} + (f_{0}^{3}f_{1} − f_{0}f_{1}f_{2} − f_{1}^{3})T^{3}+
f_{0}^{3}f_{1}^{2} − f_{0}^{2}f_{2}^{2} − f_{0}f_{1}^{2}f_{2} − f_{0}^{4}f_{2} − f_{1}^{4} − f_{2}^{3})^{3} mod 3
≡ (T^{4} + f_{1}T − f_{2}) (T^{4} + \sqrt[3]{f_{1}}T^{3} − \sqrt[3]{f_{0}f_{2}}T^{2} + \sqrt[3]{f_{0}^{3}f_{1} − f_{0}f_{1}f_{2} − f_{1}^{3}}T +
\sqrt[3]{f_{0}^{3}f_{1}^{2} − f_{0}^{2}f_{2}^{2} − f_{0}f_{1}^{2}f_{2} − f_{0}^{4}f_{2} − f_{1}^{4} − f_{2}^{3}})^{9} mod 3

In characteristic 3, the Jacobian of a curve of genus 2 has at most 9 points of 3-torsion. Therefore there are at most 4 distinct values for the u_{1}-coordinate of 3-torsion elements, whereas Ξ_{3} modulo 3 has 8 roots. We deduce that Theorem 2 cannot be generalized easily to the case p = ℓ.

The next interesting case is that of Ξ_{5}(C_{2}) for 5-torsion. We estimate that this polynomial has several million monomials, so new techniques will be needed to store it, relying on the evaluation philosophy of [16].

4.2 Computing the modular equation: the general case

The solution of Subsection 4.1 is specific to genus 2, and requires additional non-vanishing assumptions. We turn here to the general case of a genus g hyperelliptic curve C defined over a field k, and indicate how to compute its ℓ-th modular equation. This process is very similar to the one described above: first compute a representation of the ℓ-torsion divisors on Jac(C), then compute the modular equation. The previous additional assumptions are ruled out now, at the cost notably of a more delicate pre-computation.

As in the genus 2 case, the Mumford-Cantor coordinates of the ℓ-torsion divisors are algebraic over k. For the general case, Adleman and Huang propose in [4] an algorithm that computes a representation of these numbers by the following objects, whose existence is guaranteed if C satisfies the genericity assumption for ℓ:

1. A function q in k[u_{0}, …, u_{g−1}, v_{0}, …, v_{g−1}], for instance a linear form. The function q must take ℓ^{2g} − 1 distinct values on Jac[ℓ] \ {0}, i.e. q must separate the points of Jac[ℓ] \ {0}.

2. The squarefree polynomial Q = ∏_{D∈Jac[ℓ]\{0}} (S − q(D)) in k[S].

3. The interpolating polynomials U_{0}, …, U_{g−1}, V_{0}, …, V_{g−1} in k[S] of degree less than ℓ^{2g} − 1 such that for all ℓ-torsion divisors D, U_{i} (resp. V_{i}) takes the value u_{i}(D) (resp. v_{i}(D)) when evaluated at q(D).

Adleman and Huang’s algorithm works in a complex setting of semi-algebraic maps, which reflects the fact that in the general case, the multiplication by ℓ-map cannot be represented by a single rational function in Mumford-Cantor’s coordinates.

Once the above objects are know, they enable to compute the polynomial χ_{ℓ}; then the modular equation Ξ_{ℓ} is deduced just as in Subsection 4.1. The computation of χ_{ℓ} follows the same inspiration as in the previous subsection. Again, recall that the function t_{ℓ}(D) is defined as:

t_{ℓ}(D) = ∑_{1≤i≤ \frac{ℓ−1}{2}} u_{g−1}([i]D).

For simplicity, assume first that the polynomial Q is irreducible, so A := k[S]/(Q) is a field, and let s be the image of S in A. Since A is a field, for any i, we can apply Cantor’s algorithm [9] of multiplication by i in A[x], on the divisor

D(s) = ⟨x^{g} + U_{g−1}(s)x^{g−1} + ⋯ + U_{0}(s), V_{g−1}(s)x^{g−1} + ⋯ + V_{0}(s)⟩.

Let h_{i,ℓ} ∈ A be the u_{g−1}-coordinate of [i]D(s). If we consider h_{i,ℓ} in k[S], then u_{g−1}([i]D) = h_{i,ℓ}(q(D)) holds for all ℓ-torsion divisors D. This implies that

t_{ℓ}(D) = ∑_{1≤i≤ \frac{ℓ−1}{2}} h_{i,ℓ}(q(D))

also holds for all ℓ-torsion divisors D. Thus the polynomial χ_{ℓ} is the characteristic polynomial of ∑_{1≤i≤ \frac{ℓ−1}{2}} h_{i,ℓ} modulo Q.

In the general case, the polynomial Q is squarefree but not irreducible; then A is not a field, but a product of fields: A ≃ ∏ A_{j}. This might make it impossible to apply the multiplication by i algorithm on the divisor D(s), since this algorithm requires divisions in A. A first solution to obtain χ_{ℓ} consists in factorizing Q: applying the process described above in each field A_{j} yields a polynomial χ_{ℓ,j}, and the product of all χ_{ℓ,j} is χ_{ℓ}.

Of course, we want to avoid the factorization. Then a better solution is dynamic evaluation techniques [19]: the iterates of D(s) are computed as if A = k[S]/(Q) were a field. The divisions in A are performed using Extended GCD computations. When a division occurs where the dividend is not invertible in A, we have found a new factor of Q. Then we pursue the computations modulo each factor and finally multiply all results, as above. Thus the factorization of Q is not required; only the necessary factors come out the Extended GCD computations.

5 Factorization patterns of Ξ_{ℓ} over a finite field

Let C be a hyperelliptic curve of genus g over a finite field 𝔽_{q}. Let ℓ be a prime coprime to q and let us assume that the genericity assumption holds for the ℓ-torsion on C. The polynomial Ξ_{ℓ} can be factored over 𝔽_{q}. Due to the galoisian properties of the polynomial, the possible patterns of factorization are very specific. The general result is stated in the first subsection; then we give the explicit examples of genus 1 and genus 2, and the application to point-counting in the last subsection.

5.1 Link with the Frobenius action

Let π : x ↦ x^{q} denote the q-th power Frobenius action on \overline{𝔽_{q}}, extended to C and to Jac(C). The ℓ-torsion subgroup Jac[ℓ] can be viewed as an 𝔽_{ℓ}-vector space of dimension 2g on which π acts as an endomorphism. The following result is a general statement on the relation between π and the factorization patterns of the modular equations; the precise form is given in Lemma 2 below.

Theorem 3 Assume that Ξ_{ℓ} is squarefree. Then the endomorphism π of the 𝔽_{ℓ}-vector space Jac[ℓ] determines the factorization pattern of Ξ_{ℓ}.

The proof of Theorem 3 is derived from the following lemmata.

Lemma 1 Assume that Ξ_{ℓ} is squarefree and let D and E be non-zero ℓ-torsion divisors. Then

t_{ℓ}(D) = t_{ℓ}(E) ⟺ E ∈ ⟨D⟩.

Proof. The direction ⇐ follows from the definition of t_{ℓ}. For the converse implication, since Ξ_{ℓ} is squarefree, the number of values taken by t_{ℓ} is maximal, therefore two distinct subgroups cannot give the same value. □

We define the modified order of a polynomial P with coefficient in a finite field as

ord^{∗}(P) = min{k ∈ ℕ^{∗}, deg(X^{k} mod P (X)) = 0}.

This notation is used in this section and in the Appendix.

Lemma 2 Let D be a non-zero ℓ-torsion divisor of Jac[ℓ]. Let V_{D} be the 𝔽_{ℓ}-vector space generated by the galoisian conjugates of D:

V_{D} = Span_{𝔽_{ℓ}}{π^{n}(D), n ∈ ℕ}.

Let P be the characteristic polynomial of π restricted to V_{D}. If Ξ_{ℓ} is squarefree, then the degree of the extension of 𝔽_{q} where t_{ℓ}(D) is defined is ord^{∗}(P).

Proof. Let k be the smallest positive integer such that π^{k}(D) ∈ ⟨D⟩. Since π fixes 𝔽_{q}, we check as in Section 2 that π(t_{ℓ}(D)) = t_{ℓ}(π(D)), and so for all i ≥ 0, π^{i}(t_{ℓ}(D)) = t_{ℓ}(π^{i}(D)). By definition of k, for i < k, π^{i}(D) is not in ⟨D⟩, so t_{ℓ}((π^{i}(D)) ≠ t_{ℓ}(D) by the previous lemma, i.e. π^{i}(t_{ℓ}(D)) ≠ t_{ℓ}(D). Since t_{ℓ}(π^{k}(D)) = t_{ℓ}(D), we have proven that k is the degree of the extension of 𝔽_{q} where t_{ℓ}(D) is defined.

We now consider the characteristic polynomial P of π restricted to the space V_{D} generated by the conjugates of D. Due to the definition of V_{D}, P is the minimal polynomial of π restricted to V_{D}.

Denoting λ the element of 𝔽_{ℓ}^{∗} such that π^{k}(D) = λD, the endomorphism π^{k} − λId is trivial on D and on all its conjugates, therefore it is trivial on the whole of V_{D}. Hence we have

X^{k} − λ ≡ 0 mod P (X).

Conversely, let k′ and μ be such that X^{k′} − μ ≡ 0 mod P (X), then π^{k′} is equal to μId on V_{D} and in particular on D: therefore k′ must be larger than or equal to k. The integer k is then the minimal having this property, as announced. □

Proof of Theorem 3: Let M be the matrix of the action of π on a basis B of Jac[ℓ]. For all D in Jac[ℓ] expressed as a vector according to the same basis, finding V_{D} and the associated polynomial P (X) is a matter of elementary linear algebra. The extension where the root of Ξ_{ℓ} associated to D is defined follows easily. Hence knowing the matrix M gives all the extensions where the roots of Ξ_{ℓ} are defined, which gives the factorization pattern, because the field of definition is finite. □

5.2 Genus 1

The factorization patterns of the modular polynomial of an elliptic curve are well known [6, p. 119]. We restate them here for completeness; this gives a flavor of the genus 2 case that follows. Note that this result is usually given for the classical modular equations Φ_{ℓ} relating the j-invariants of ℓ-isogenous elliptic curves; they have the same factorization patterns as ours.

In the sequel, notations such as

(n_{1})^{α_{1}} ⋯ (n_{k})^{α_{k}} or ( \underbrace{n_{1}, …, n_{1}}_{β_{1}}, …, \underbrace{n_{k}, …, n_{k}}_{β_{k}})

stand for a squarefree polynomial having α_{i} irreducible factors of degree n_{i}, for i in 1, …, k; then β_{i} = n_{i}α_{i}.

Theorem 4 Let E be an elliptic curve over 𝔽_{q} and ℓ coprime to q. Let X^{2} − cX + q be the characteristic polynomial of the Frobenius endomorphism π. Assume that the modular polynomial Ξ_{ℓ} is squarefree, then the set of degrees of its irreducible factors is one of the following, where r is an integer greater than 1:

1. (1, ℓ) or (1, 1, …, 1) if c^{2} − 4q ≡ 0 mod ℓ.

2. (1, 1, r, r, … r) if c^{2} − 4q is a non-zero square modulo ℓ.

3. (r, r, …, r) if c^{2} − 4q is not a square modulo ℓ.

Case 1 corresponds to a Frobenius endomorphism having a double eigenvalue. According to the presence of one or two blocks in the Jordan decomposition we get one or the other subcase. Case 2 is the case where there are two distinct eigenvalues. Case 3 is the non-diagonalizable case.

5.3 Genus 2

In genus 2, we study all possible reductions of the matrix of the Frobenius endomorphism and get the corresponding factorization patterns for Ξ_{ℓ}. The classification is done according to the possible factorization patterns of the minimal and characteristic polynomials of the Frobenius endomorphism π, from which we deduce a block-reduction of the matrix of π; the factorization pattern of the modular equation is then deduced from Lemma 2. The two lemmata below reduce the number of cases to consider.

Lemma 3 If the characteristic polynomial of the Frobenius endomorphism has a triple root modulo ℓ then the multiplicity is actually 4.

Proof. Let (X − a)^{3}(X − b) be the characteristic polynomial of π modulo ℓ. By Weil’s theorem, all the roots have absolute value \sqrt{q}. Therefore we have a^{2} ≡ q mod ℓ and ab ≡ q mod ℓ. But q is non-zero modulo ℓ, so that a ≡ b mod ℓ. □

Lemma 4 Let D be such that V_{D} = Span_{𝔽_{ℓ}}{π^{n}(D), n ∈ ℕ} has dimension 3. Then V_{D} is a non-trivial direct sum of π-stable sub-spaces.

Proof. Let (D_{1} = D, D_{2} = π(D), D_{3} = π^{2}(D)) be a basis of V_{D} and D_{4} be a supplementary vector of π. We write π(D_{3}) = XD_{1} + Y D_{2} + ZD_{3}; then π being invertible implies X ≠ 0. Let e_{ℓ}(., .) denote the Weil pairing on Jac[ℓ]. Recall that this is an alternate non-degenerate bilinear form with values in the ℓ-th roots of unity in an algebraic closure of 𝔽_{q} and such that e_{ℓ}(π(Δ), π(Δ′)) = (e_{ℓ}(Δ, Δ′))^{q} for all ℓ-torsion divisors Δ, Δ′.

Let α be e_{ℓ}(D_{1}, D_{2}). Then iterated applications of the Frobenius endomorphism yield

e_{ℓ}(D_{2}, D_{3}) = α^{q}, e_{ℓ}(D_{1}, D_{3}) = α^{− \frac{q(q+Y )}{X}} ,

and impose that

α^{q^{3}+q^{2}Y −X^{2}+qZX} = 1.

If α were equal to 1, then e_{ℓ} would be trivial on a space of dimension 3, which contradicts its non-degeneracy. Consequently, we have α ≠ 1. Thus

q^{3} + q^{2}Y − X^{2} + qZX = 0 in 𝔽_{ℓ}.

Let A be such that π(D_{4}) = AD_{4} + E, with E in V_{D}. Weil’s theorem implies that A^{2} = q and det(π) = XA = q^{2}. We deduce that X, Y, q can be written

X = A^{3}, Y = −AZ, q = A^{2}.

Then the characteristic polynomial of the restriction of π to ⟨D_{1}, D_{2}, D_{3}⟩ is

(T − A)(T^{2} + (A − Z)T + A^{2}).

Suppose that A is a root of the right-hand factor. Then Z = 3A and the vector Δ = A^{2}D_{1} − 2AD_{2} + D_{3} is such that e_{ℓ}(Δ, Δ′) = 0 for all Δ′ in Jac[ℓ], a contradiction. Hence the characteristic polynomial is the product of two coprime non-trivial factors and V_{D} splits non-trivially in two π-stable sub-spaces. □

Using Lemmata 3 and 4, we now proceed to enumerate all admissible reduction patterns of π and apply Lemma 2 to get the corresponding factorization pattern of Ξ_{ℓ}. We give below all details for one case and leave the others to the reader. The results are collected in Appendix.

A complete example. Assume that the minimal (resp. characteristic) polynomial of π can be written P Q (resp. P Q^{2}), with P irreducible of degree 2 and Q of degree 1. Then there exists a basis (D_{1}, D_{2}, D_{3}, D_{4}) of Jac[ℓ] in which the matrix of π has the form

M = \begin{matrix}A_{2} & 0 \\ 0 & \begin{matrix}b & 0 \\ 0 & b \end{matrix} \end{matrix} ,

where A_{2} is a 2×2 matrix whose characteristic polynomial is irreducible modulo ℓ and b is a scalar.

For all 0 ≠ D ∈ ⟨D_{3}, D_{4}⟩, we have π(D) = bD, and by Lemma 2, the subgroups of order ℓ inside ⟨D_{3}, D_{4}⟩ correspond to roots of Ξ_{ℓ} defined over 𝔽_{ℓ}. There are as many roots as lines in ⟨D_{3}, D_{4}⟩, i.e. \frac{ℓ^{2}−1}{ℓ−1} = ℓ + 1.

For all 0 ≠ D ∈ ⟨D_{1}, D_{2}⟩, the vector space generated by the conjugates of D is V_{D} = ⟨D_{1}, D_{2}⟩ and the characteristic polynomial of π restricted to V_{D} is the characteristic polynomial of the matrix A_{2}. By Lemma 2, the root of Ξ_{ℓ} associated to the the subgroup generated by D is therefore in an extension of degree ord^{∗}(Characteristic polynomial of A_{2}), that we denote by ord(A_{2}). Again there are ℓ + 1 roots, thus ord(A_{2}) divides ℓ + 1. Finally, we have (ℓ + 1)/ord(A_{2}) factors of degree ord(A_{2}) in Ξ_{ℓ}.

For all D = E + F where 0 ≠ E ∈ ⟨D_{1}, D_{2}⟩ and 0 ≠ F ∈ ⟨D_{3}, D_{4}⟩, the vector space generated by the conjugates of D is V_{D} = ⟨D_{1}, D_{2}, F ⟩ and the characteristic polynomial of π on V_{D} is equal to the characteristic polynomial of A_{2} multiplied by (X − b). We denote by ord(A_{2}b) the value of ord^{∗} for this polynomial; this is the degree of the extension where we find the roots. The number of lines generated by such D’s is (ℓ − 1)(ℓ + 1)^{2}.

To summarize, Ξ_{ℓ} contains

• ℓ + 1 linear factors,

• (ℓ + 1)/ord(A_{2}) factors of degree ord(A_{2}),

• (ℓ − 1)(ℓ + 1)^{2}/ord(A_{2}b) factors of degree ord(A_{2}b).

5.4 Application to point-counting

Let C be a hyperelliptic curve of genus g over a finite field 𝔽_{q} for which we want to compute the cardinality of the Jacobian. The characteristic polynomial of the Frobenius endomorphism is denoted by F; then #Jac(C) = F(1).

The principle of the high genus variants of Schoof’s algorithm [25, 20, 18] is to compute F(1) modulo several small primes ℓ using the restriction of π to Jac[ℓ]. When this is done for sufficiently many primes ℓ, F(1) can be deduced using the Chinese Remainder Theorem.

In the 80’s, Atkin [5] proposed a modification of Schoof’s algorithm for elliptic curves: for each ℓ, he only computes the factorization pattern of the modular polynomial and reduces the number of candidates for F(1) modulo ℓ. It then requires more primes ℓ before having enough information to conclude. This method has exponential complexity but with further improvements by Elkies led to the so-called Schoof–Elkies–Atkin algorithm [27], which is the fastest method to date for large prime q.

Our modular equations can be used in the same manner for a curve C of genus g. Let ℓ be a small prime coprime to q. Assume that we have computed Ξ_{ℓ} for this curve and that it is squarefree. Then a partial factorization can be computed in order to find its factorization pattern. Following the method developed in the previous section, it is possible to find all characteristic polynomials F that could yield this pattern. Then computing the group order modulo ℓ for each of these cases gives a list of candidates among which the actual one lies.

This yields the following algorithm “à la Atkin”:

1. While we do not have enough information, do

(a) Choose a new small prime ℓ coprime to 2q;

(b) Compute the factorization pattern of Ξ_{ℓ};

(c) Compute the values of χ(1) mod ℓ compatible with this pattern;

2. Determine the only value of χ(1) compatible with all the modular informations.

To illustrate this approach, we give a table of the possible patterns for ℓ = 3 in genus 2 and the corresponding candidates for the cardinality of the Jacobian modulo 3. Recall that all genus 2 curves satisfy the genericity assumption for 3-torsion.

Theorem 5 Let C be a curve of genus 2 over a finite field 𝔽_{q} of characteristic different from 2 and 3. Assume that Ξ_{3}(C) is squarefree. Then the factorization pattern of Ξ_{3}(C) imply the values of #Jac(C) mod 3 according to the following table:

q ≡ 2 mod 3
pattern  #Jac(C) mod 3
(10)^{4}  2
(2)^{2}(6)^{6}  1
(4)(12)^{3}  1
(2)^{20}  1
(1)^{2}(2)(4)(8)^{4}  0
(1)^{2}(2)(3)^{2}(6)^{5}  0
(1)^{8}(2)^{16}  0
(1)^{5}(2)^{4}(3)(6)^{4}  0
(4)^{10}  1, 2

q ≡ 1 mod 3
pattern  #Jac(C) mod 3
(5)^{8}  1, 2
(1)(2)^{2}(3)(4)^{2}(12)^{2}  0, 2
(1)^{4}(2)^{2}(4)^{8}  0, 2
(1)(3)^{4}(9)^{3}  0, 1
(1)^{4}(3)^{12}  0, 1
(1)^{40}  0, 1
(4)^{10}  2
(2)^{2}(6)^{6}  1
(2)^{20}  1
(1)^{2}(2)(3)^{2}(6)^{5}  0
(1)^{5}(2)^{4}(3)(6)^{4}  0
(1)^{8}(2)^{16}  0

As an example, consider again the curve C defined in Section 4.1 over the field 𝔽_{q} with q = 101009 ≡ 2 mod 3. Then the factorization pattern of Ξ_{3}(C) is (1)^{2}(2)(4)(8)^{4} which implies that #Jac(C) ≡ 0 mod 3.

Similarly, the factorization pattern of Ξ_{5}(C) is (3)^{52}. Referring to the table given in the Appendix, we deduce that only the first four cases of that table are to be considered. An exhaustive enumeration of all possible characteristic polynomials in these four cases reveals that this polynomial is either (T^{2} + 2T + 4)^{2} or (T^{2} + 3T + 4)^{2}; they both give the same number of points #Jac(C) ≡ 4 mod 5.

Complexity considerations. In the usual implementations of elliptic curve point counting algorithms, the generic modular equations are precomputed and stored. However, for genus 2 and higher, the generic equations are too large to be stored, even if we manage to precompute them. Therefore we have to recompute them on the fly for each instance of a curve. Let q be the size of the base field, and ℓ be the prime under consideration. Computing Ξ_{ℓ} for a given curve involves a number of operations in the base field which is polynomial in ℓ. Then the factorization phase costs O(log q) operations with polynomials of degree O(ℓ^{3}). On the other hand, the plain Schoof-like algorithm would require to deal with the whole torsion whose degree is in O(ℓ^{4}). Computing the action of the Frobenius endomorphism will then require O(log q) operations with polynomials of degree O(ℓ^{4}). Therefore, for a fixed ℓ and when q tends to infinity, the cost of computing Ξ_{ℓ} and its factorization pattern is smaller than the cost of the plain Schoof algorithm. Still, in a complete point-counting algorithm, we need to take primes ℓ up to log q, and more efficient algorithms for computing Ξ_{ℓ} of a given curve together with more precise analysis will be needed to conclude about the feasibility of this kind of approach.

Appendix: Factorization patterns of Ξ_{ℓ} in genus 2

The lines in the following table are indexed by the possible decompositions of the Frobenius endomorphism π on Jac[ℓ]. These are given in the second column. The first column gives the corresponding factorization pattern of the characteristic polynomial of π, and the last gives the factorization pattern of the modular equation Ξ_{ℓ}.

The notation for the factorization patterns is defined in Section 5. Notations such as A_{i} or B_{i} denote i × i matrices with irreducible characteristic polynomials; the notation ∗ denotes any nonzero matrix. Lower case letters stand for scalars, which may be thought as 1 × 1 matrix.

The modified order ord^{∗}(P) of a polynomial P is defined in Section 5. Given two matrices A_{i}, B_{j}, the notation ord(A_{i}B_{j}) is defined as the modified order of the product of their characteristic polynomials. This notation extends to three or four blocks.

The characteristic polynomial of π is not necessarily squarefree, so we adopt another notation for its factorization pattern:

[n_{1}]^{α_{1}} ⋯ [n_{k}]^{α_{k}}

stands for a product P_{1}^{α_{1}} ⋯ P_{k}^{α_{k}} where the P_{i} are distinct irreducible polynomials of degree n_{i}, for i = 1, …, k.

Char. pol.

Matrix

Pattern of modular polynomial

One factor of degree 4

[4]  A_{4}  ( \underbrace{ord(A_{4}), …, ord(A_{4})}_{ℓ^{3}+ℓ^{2}+ℓ+1} )

Two factors of degree 2

[2]^{2}  \begin{matrix}A_{2} & 0 \\ 0 & A_{2} \end{matrix}  ( \underbrace{ord(A_{2}), …, ord(A_{2})}_{ℓ^{3}+ℓ^{2}+ℓ+1} )
[2]^{2}  \begin{matrix}A_{2} & ∗ \\ 0 & A_{2} \end{matrix}  ( \underbrace{ord(A_{2}), …, ord(A_{2})}_{ℓ+1}, \underbrace{ord(A_{2}^{2}), …, ord(A_{2}^{2})}_{ℓ^{2}(ℓ+1)} )
[2][2]  \begin{matrix}A_{2} & 0 \\ 0 & B_{2} \end{matrix}  ( \underbrace{ord(A_{2}), …, ord(A_{2})}_{ℓ+1}, \underbrace{ord(B_{2}), …, ord(B_{2})}_{ℓ+1}, \underbrace{ord(A_{2}B_{2}), …, ord(A_{2}B_{2})}_{(ℓ−1)(ℓ+1)^{2}} )

One factor of degree 2, two of degree 1

[2][1]^{2}  \begin{matrix}A_{2} & 0 \\ 0 & \begin{matrix}b & 0 \\ 0 & b \end{matrix} \end{matrix} ( \underbrace{1, …, 1}_{ℓ+1}, \underbrace{ord(A_{2}), …, ord(A_{2})}_{ℓ+1}, \underbrace{ord(A_{2}b), …, ord(A_{2}b)}_{(ℓ−1)(ℓ+1)^{2}} )

[2][1]^{2}  \begin{matrix}A_{2} & 0 \\ 0 & \begin{matrix}b & ∗ \\ 0 & b \end{matrix} \end{matrix} ( 1, ℓ, \underbrace{ord(A_{2}), …, ord(A_{2})}_{ℓ+1}, \underbrace{ord(A_{2}b), …, ord(A_{2}b)}_{(ℓ−1)(ℓ+1)}, \underbrace{ord(A_{2}b^{2}), …, ord(A_{2}b^{2})}_{ℓ(ℓ−1)(ℓ+1)} )

[2][1][1]

\begin{matrix}A_{2} & 0 \\ 0 & \begin{matrix}b & 0 \\ 0 & c \end{matrix} \end{matrix}

( 1, 1, \underbrace{ord(A_{2}), …, ord(A_{2})}_{ℓ+1}, \underbrace{ord(bc), …, ord(bc)}_{ℓ−1}, \underbrace{ord(A_{2}b), …, ord(A_{2}b)}_{(ℓ+1)(ℓ−1)},

\underbrace{ord(A_{2}c), …, ord(A_{2}c)}_{(ℓ+1)(ℓ−1)}, \underbrace{ord(A_{2}bc), …, ord(A_{2}bc)}_{(ℓ−1)^{2}(ℓ+1)} )

22

Char. pol.

Matrix

Pattern of modular polynomial

Four factors of degree 1

[1]^{4}  \begin{matrix}\begin{matrix}a & 0 \\ 0 & a \end{matrix} & 0 \\ 0 & \begin{matrix}a & 0 \\ 0 & a \end{matrix} \end{matrix} ( \underbrace{1, …, 1}_{ℓ^{3}+ℓ^{2}+ℓ+1} )

[1]^{4}  \begin{matrix}\begin{matrix}a & ∗ \\ 0 & a \end{matrix} & 0 \\ 0 & \begin{matrix}a & 0 \\ 0 & a \end{matrix} \end{matrix} ( \underbrace{1, …, 1}_{ℓ^{2}+ℓ+1}, \underbrace{ℓ, …, ℓ}_{ℓ^{2}} )

[1]^{4}  \begin{matrix}\begin{matrix}a & ∗ \\ 0 & a \end{matrix} & 0 \\ 0 & \begin{matrix}a & ∗ \\ 0 & a \end{matrix} \end{matrix} ( \underbrace{1, …, 1}_{ℓ+1}, \underbrace{ℓ, …, ℓ}_{ℓ^{2}+ℓ})

[1]^{4}  \begin{matrix}\begin{matrix}a & ∗ \\ 0 & a \end{matrix} & ∗ \\ 0 & \begin{matrix}a & ∗ \\ 0 & a \end{matrix} \end{matrix} ( 1, ℓ, \underbrace{ord(a^{3}), …, ord(a^{3})}_{ℓ^{2}} \underbrace{ord(a^{4}), …, ord(a^{4})}_{ℓ^{3}} )

[1]^{2}[1]^{2}  \begin{matrix}\begin{matrix}a & 0 \\ 0 & a \end{matrix} & 0 \\ 0 & \begin{matrix}b & 0 \\ 0 & b \end{matrix} \end{matrix} ( \underbrace{1, …, 1}_{2ℓ+2}, \underbrace{ord(ab), …, ord(ab)}_{(ℓ−1)(ℓ+1)^{2}} )

[1]^{2}[1]^{2}  \begin{matrix}\begin{matrix}a & ∗ \\ 0 & a \end{matrix} & 0 \\ 0 & \begin{matrix}b & 0 \\ 0 & b \end{matrix} \end{matrix} ( \underbrace{1, …, 1}_{ℓ+2}, ℓ, \underbrace{ord(ab), …, ord(ab)}_{(ℓ−1)(ℓ+1)}, \underbrace{ord(a^{2}b), …, ord(a^{2}b)}_{ℓ(ℓ−1)(ℓ+1)} )

[1]^{2}[1]^{2}

\begin{matrix}\begin{matrix}a & ∗ \\ 0 & a \end{matrix} & 0 \\ 0 & \begin{matrix}b & ∗ \\ 0 & b \end{matrix} \end{matrix} ( 1, 1, ℓ, ℓ, \underbrace{r, …, r}_{ℓ−1}, \underbrace{s_{1}, …, s_{1}}_{ℓ(ℓ−1)}, \underbrace{s_{2}, …, s_{2}}_{ℓ(ℓ−1)}, \underbrace{t, …, t}_{ℓ^{2}(ℓ−1)} )

where r = ord(ab), s_{1} = ord(ab^{2}), s_{2} = ord(a^{2}b), t = ord(a^{2}b^{2})

[1]^{2}[1][1]

\begin{matrix}\begin{matrix}a & 0 \\ 0 & a \end{matrix} & 0 \\ 0 & \begin{matrix}b & 0 \\ 0 & c \end{matrix} \end{matrix} ( \underbrace{1, …, 1}_{ℓ+3}, \underbrace{r, …, r}_{ℓ−1}, \underbrace{s_{1}, …, s_{1}}_{ℓ^{2}−1}, \underbrace{s_{2}, …, s_{2}}_{ℓ^{2}−1}, \underbrace{t, …, t}_{(ℓ^{2}−1)(ℓ−1)} )

where r = ord(bc), s_{1} = ord(ab), s_{2} = ord(ac), t = ord(abc)

[1]^{2}[1][1]

\begin{matrix}\begin{matrix}a & ∗ \\ 0 & a \end{matrix} & 0 \\ 0 & \begin{matrix}b & 0 \\ 0 & c \end{matrix} \end{matrix}

( 1, 1, 1, ℓ, \underbrace{r_{1}, …, r_{1}}_{ℓ−1}, …, \underbrace{r_{3}, …, r_{3}}_{ℓ−1}, \underbrace{s_{1}, …, s_{1}}_{ℓ(ℓ−1)}, \underbrace{s_{2}, …, s_{2}}_{ℓ(ℓ−1)},

\underbrace{t, …, t}_{(ℓ−1)^{2}} \underbrace{u, …, u}_{ℓ(ℓ−1)^{2}} )
where r_{1} = ord(bc), r_{2} = ord(ab), r_{3} = ord(ac),

s_{1} = ord(a^{2}b), s_{2} = ord(a^{2}c), t = ord(abc), u = ord(a^{2}bc)

[1][1][1][1]

\begin{matrix}\begin{matrix}a & 0 \\ 0 & b \end{matrix} & 0 \\ 0 & \begin{matrix}c & 0 \\ 0 & d \end{matrix} \end{matrix}

( 1, 1, 1, 1, \underbrace{r_{1}, …, r_{1}}_{ℓ−1}, …, \underbrace{r_{6}, …, r_{6}}_{ℓ−1}, \underbrace{s_{1}, …, s_{1}}_{(ℓ−1)^{2}}, …,

\underbrace{s_{4}, …, s_{4}}_{(ℓ−1)^{2}}, \underbrace{t, …, t}_{(ℓ−1)^{3}} )

where r_{1} = ord(ab), r_{2} = ord(ac), r_{3} = ord(ad), r_{4} = ord(bc),

r_{5} = ord(bd), r_{6} = ord(cd), s_{1} = ord(abc), s_{2} = ord(abd), s_{3} = ord(acd), s_{4} = ord(bcd), t = ord(abcd)

References

[1] Magma, http://www.maths.usyd.edu.au:8000/u/magma/.

[2] Medicis, http://www.medicis.polytechnique.fr/.

[3] Tera, http://tera.medicis.polytechnique.fr/.

[4] L. Adleman and M.-D. Huang, Counting points on curves and abelian varieties over finite fields, J. Symbolic Comput. 32 (2001), 171–189.

[5] A. O. L. Atkin, The number of points on an elliptic curve modulo a prime, Series of e-mails to the NMBRTHRY mailing list, 1992.

[6] I. Blake, G. Seroussi, and N. Smart, Elliptic curves in cryptography, London Math. Soc. Lecture Note Ser., vol. 265, Cambridge University Press, 1999.

[7] J. Boxall and D. Grant, Examples of torsion points on genus two curves, Trans. Amer. Math. Soc. 352 (2000), no. 10, 4533–4555.

[8] B. Buchberger, Gröbner bases: An algorithmic method in polynomial ideal theory, Multidimensional System Theory, Reidel, Dordrecht, 1985, pp. 374–383.

[9] D. G. Cantor, Computing in the Jacobian of an hyperelliptic curve, Math. Comp. 48 (1987), no. 177, 95–101.

[10] , On the analogue of the division polynomials for hyperelliptic curves, J. Reine Angew. Math. 447 (1994), 91–145.

[11] L. S. Charlap, R. Coley, and D. P. Robbins, Enumeration of rational points on elliptic curves over finite fields, Draft, 1991.

[12] N. Elkies, Elliptic and modular curves over finite fields and related computational issues, Computational Perspectives on Number Theory (D.A. Buell and J.T. Teitelbaum, eds.), AMS/International Press, 1998, Proceedings of a Conference in Honor of A.O.L. Atkin, pp. 21– 76.

[13] P. Gaudry and R. Harley, Counting points on hyperelliptic curves over finite fields, ANTS-IV (W. Bosma, ed.), Lecture Notes in Comput. Sci., vol. 1838, Springer–Verlag, 2000, pp. 313–332.

[14] M. Giusti, J. Heintz, J. E. Morais, J. Morgenstern, and L. M. Pardo, Straight-line programs in geometric elimination theory, J. of Pure and App. Algebra 124 (1998), 101–146.

[15] M. Giusti, G. Lecerf, and B. Salvy, A Gröbner free alternative for polynomial system solving, J. Complexity 17 (2001), no. 1, 154–211.

[16] J. Heintz, T. Krick, S. Puddu, J. Sabia, and A. Waissbein, Deformation techniques for efficient polynomial equation solving, J. Complexity 16 (2000), 70–109.

[17] M. Hindry and J. Silverman, Diophantine geometry: an introduction, Graduate Texts in Mathematics, vol. 201, Springer–Verlag, 2000.

[18] M.-D. Huang and D. Ierardi, Counting points on curves over finite fields, J. Symbolic Comput. 25 (1998), 1–21.

[19] C. Dicrescenzo J. Della Dora and D. Duval, About a new method for computing in algebraic number fields, Proceedings Eurocal ’85 Vol. 2, Lecture Notes in Comput. Sci., vol. 204, 1985, pp. 289–290.

[20] W. Kampkötter, Explizite Gleichungen für Jacobische Varietäten hyperelliptischer Kurven, Ph.D. thesis, Universität Gesamthochschule Essen, August 1991.

[21] J. S. Milne, Abelian varieties, Arithmetic Geometry (G. Cornell and J. H. Silverman, eds.), Springer–Verlag, 1986, pp. 103–150.

[22] , Jacobian varieties, Arithmetic Geometry (G. Cornell and J. H. Silverman, eds.), Springer–Verlag, 1986, pp. 167–212.

[23] F. Morain, Calcul du nombre de points sur une courbe elliptique dans un corps fini : aspects algorithmiques, J. Théor. Nombres Bordeaux 7 (1995), 255–282.

[24] D. Mumford, Tata lectures on theta I, Progr. Math., vol. 28, Birkhauser, 1983.

[25] J. Pila, Frobenius maps of abelian varieties and finding roots of unity in finite fields, Math. Comp. 55 (1990), no. 192, 745–763.

[26] R. Schoof, Elliptic curves over finite fields and the computation of square roots mod p, Math. Comp. 44 (1985), 483–494.

[27] , Counting points on elliptic curves over finite fields, J. Théor. Nombres Bordeaux 7 (1995), 219–254.

[28] É. Schost, Degree bounds and lifting techniques for triangular sets, Proceedings of the 2002 Symposium on Symbolic and Algebraic Computation, ACM Press, 2002.

[29] J. H. Silverman, The arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 106, Springer–Verlag, 1986.

[30] D. Y. Y. Yun, On square-free decompositions algorithms, Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation, ACM Press, 1976, pp. 26–35.