COMPUTING IGUSA CLASS POLYNOMIALS VIA THE

CHINESE REMAINDER THEOREM

¨KIRSTEN EISENTRAGER AND KRISTIN LAUTER

Abstract. We present a new method for computing the Igusa class

polynomials of a primitive quartic CM ﬁeld. For a primitive quartic

CM ﬁeld, K, we compute the Igusa class polynomials modulo p for

certain small primes p and then use the Chinese remainder theorem

and a bound on the denominators to construct the class polynomials.

We also provide an algorithm for determining endomorphism rings of

Jacobians of genus 2 curves. Our algorithm can be used to generate

genus 2 curves over a ﬁnite ﬁeld F with a given zeta function.n

1. Introduction

In this paper we present a new method for computing the Igusa class

polynomials of a primitive quartic CM ﬁeld. Our method generalizes the

algorithm for ﬁnding the Hilbert Class polynomial given in [ALV04] to the

genus 2 situation. Given a primitive quartic CM ﬁeld K, for each small

prime p in a certain set we determine the Igusa class polynomial modulo

p by ﬁnding all triples of invariants modulo p for which the corresponding

genus2curvehasCMbyK. The Igusaclass polynomialisthenfoundusing

the Chinese Remainder Theorem and a bound on the denominators of the

coeﬃcients.

Several diﬃculties arise in the genus 2 situation which are absent in the

elliptic curve case. In this paper we resolve the following issues: the ﬁeld of

deﬁnition of a CM abelian variety, necessary conditions on the small primes

for the algorithm to succeed, and the computation of the endomorphism

ring of the Jacobian of a genus 2 curve in the ordinary case.

The triple of Igusa invariants ([Igu60, Igu62]) of a genus 2 curve can be

calculated in two diﬀerent ways: from modular functions evaluated on a

period matrix or as invariants of the binary sextic deﬁning the curve. Igusa

showed how the invariants of a binary sextic could be expressed in terms of

Siegel modular forms ([Igu67, p. 848]) (see also [GL04, Section 5.2]). So the

absolute Igusa invariants can be computed as quotients of Siegel modular

Key words and phrases. genus 2 curves, endomorphism rings, Igusa class polynomials,

complex multiplication, Chinese Remainder Theorem.

The ﬁrst author was partially supported by the National Science Foundation under

agreement No. DMS-0111298. We thank E. Goren, E. Howe, K. Kedlaya, J-P. Serre, P.

Stevenhagen, and T. Yang for helpful discussions.

MSC 11G15, 11G10, 11R37, 14G50.

1¨2 KIRSTEN EISENTRAGER AND KRISTIN LAUTER

forms evaluated on the period matrix associated to an abelian surface with

principal polarization, but this approach requires an exponentially large

amount of precision.

GivenaprimitivequarticCMﬁeldK,letAbeasystemofrepresentatives

for the set of isomorphism classes of principally polarized abelian varieties

overC having complex multiplication byK. For each abelian varietyA∈A

let (j (A),j (A),j (A)) be the absolute Igusa invariants of A. Then the1 2 3

Igusa class polynomials H , for i= 1,2,3, are deﬁned to bei

Y

H := (X−j (A)).i i

A∈A

It is known ([Shi98]) that roots of these polynomials generate unramiﬁed

abelian extensions of the reﬂex ﬁeld of K. It is also known that Igusa class

polynomials can be used to generate genus 2 curves with CM by K, and

thus with a given zeta function over a suitable prime ﬁeld (cf. Section 3).

In this paper we prove the following theorem.

Theorem 1. Given a primitive quartic CM ﬁeldK, the following algorithm

ﬁnds the Igusa class polynomials of K :

(1) Produce a collection S of small rational primes p∈S satisfying:

a. p splits completely in K and splits completely into principal ideals in

∗K , the reﬂex of K.

b. Let B be the set of all primes of bad reduction for the genus 2 curves

with CM by K. Then S∩B =∅.Q

c. p>c, where c is a constant determined in Theorem 3.p∈S

(2) Form the class polynomialsH , H , H modulop for eachp∈S. Let1 2 3

H (X):=H (X) mod p. Theni,p i

Y

H (X) = (X−j (C)),i,p i

C∈Tp

where T is the collection of F -isomorphism classes of genus 2 curves overp p

F whose Jacobian has endomorphism ring isomorphic to O .p K

(3) Chinese Remainder Step. Form H (X) from {H } (i= 1,2,3).i i,p p∈S

Remark1. Condition 1(a) is enough to insure thatp solves a relative norm

equation in K/K , ππ =p, π a Weil number (cf. Proposition 4 below).0

Remark 2. By [GL04], the primes in the set B and in the denominators

of the class polynomials are bounded eﬀectively by a quantity related to the

discriminant ofK. Furthermore, it follows from [Gor97, Theorems 1 and 2]

and the discussion in [GL04, Section 4.1] that condition 1(b) is implied by

condition 1(a).

Remark 3. It follows from the Cebotarev density theorem that the density

of the primes in the setS is inversely proportional to the class number ofK

in the case that K is Galois cyclic. In the non-Galois case, the density is

inversely proportional to the degree of the normal closure of the composite

of K with the Hilbert class ﬁeld of the reﬂex of K.6

A CRT ALGORITHM FOR COMPUTING IGUSA CLASS POLYNOMIALS 3

Our algorithm has not been eﬃciently implemented yet, and we make no

claims about the running time. Our algorithm has the advantage that it

does not require exponentially large amounts of precision of computation.

It was recently brought to our attention that the paper [CMKT00] proposes

a similar algorithm, but they give no proof of the validity of the approach.

Indeed, they fail to impose the conditions necessary to make the algorithm

correct and include many unclear statements.

The proof of Theorem 1 is given in Section 4. Implementation details for

thealgorithmaregiveninSection5. InSection6we show how todetermine

theendomorphismringofanordinaryJacobianofagenus2curve. Section7

gives an example of the computation of a class polynomial modulo a small

prime.

2. Notation.

Throughout this paper, C denotes a smooth, projective, absolutely ir-

reducible curve, and J = J(C) will be its Jacobian variety with identity

element O. The ﬁeld, K, is always assumed to be a primitive quartic CM

ﬁeld, with ring of integers O . The real quadratic subﬁeld of K is denotedK

by K , and a generator for the Galois group Gal(K/K ) is denoted by a0 0

∗bar, ω 7→ ω¯. We will write K for the reﬂex of the quartic CM ﬁeld K.

For i = 1,2,3 we let H (X) be the Igusa class polynomials of K, and fori

a prime p ∈ S we let H := H mod p. For a ﬁeld F, F will denote ani,p i

algebraic closure of F. We say that C has CM by K if the endomorphism

ring of J(C) is isomorphic to O .K

3. Generating genus 2 curves with a given zeta function

Our algorithm solves the following problem under certain conditions.

Problem: Given (n,N ,N ), ﬁnd a genus 2 curve C over the prime ﬁeld1 2

F such that #C(F ) =N and #C(F ) =N . Given such a C, it follows2n n 1 2n

2that #J(C)(F )=N =(N +N )/2−n.n 21

Given (n, N , N ), it is straightforward to ﬁnd K, the quartic CM ﬁeld1 2

such that the curve C has CM by K, by ﬁnding the quartic polynomial

2 2satisﬁed by Frobenius. Write N =n+1−s , and N =n +1+2s −s ,1 1 2 2 1

and solve for s and s . Then K is generated over Q by the polynomial1 2

4 3 2 2t −s t +s t −ns t+n .1 2 1

If s is prime to n, then the Jacobian is ordinary ([How95, p. 2366]).2

Assume that (s ,n)=1. We also restrict to primitive CM ﬁelds K. If K is2

aquarticCMﬁeld,thenK isnotprimitiveiﬀK/QisGaloisandbiquadratic

(Gal(K/Q)=V )([Shi98, p.64]). In the example in Section 7,K is given in4p √

the formK =(i a+b d), witha,b,d∈Z andd and (a,b) square free. In

2 2 2this form the condition is easy to check: K is primitive iﬀa −b d =k for

some integer k ([KW89, p. 135]). Assume further that K does not contain

a cyclotomic ﬁeld.¨4 KIRSTEN EISENTRAGER AND KRISTIN LAUTER

Given the data, (n, N , N ), satisfying the assumptions, computeK and1 2

its Igusa class polynomials H , H , H using Theorem 1. From a triple1 2 3

of roots modulo p of H , H , H for a prime p ∈ S, we can construct a1 2 3

genus 2 curve over a ﬁnite ﬁeldF whose Jacobian has CM by K using thep

combined algorithms of Mestre ([Mes91]) and Cardona-Quer ([CQ02]). If

the curve does not have the required number of points on the Jacobian, a

twistofthecurvemaybeused. Inthecasewhere4groupordersarepossible

for the pair (n,K) (cf. Section 5.1), a diﬀerent triple of invariants may be

tried until the desired group order is obtained.

4. Proof of Theorem 1

GivenaprimitivequarticCMﬁeldK,letAbeasystemofrepresentatives

of the isomorphism classes of principally polarized abelian surfaces over C

withCMbyK. EachelementofAhasaﬁeldofdeﬁnitionk whichisaﬁnite

extension of Q ([Shi98, Prop. 26, p. 96]). For any prime p ∈ S satisfying

the conditions of Theorem 1, the setT was deﬁned in Step 2 of Theorem 1p

as the collection of F -isomorphism classes of genus 2 curves over F withp p

endomorphism ring isomorphic to O . We claim that we have a bijectiveK

correspondence between A and T . Moreover, we claim that reducing thep

Igusa invariants gives the Igusa invariants of the reduction. Taken together,

these can be stated in the form of the following theorem:

Theorem 2. Let K be a primitive quartic CM ﬁeld and let p ∈ S be a

rational prime that satisﬁes the conditions of Theorem 1. Then

Y

H (X) = (X−j (C)),i,p i

C∈Tp

where H (X) and T are deﬁned as in Theorem 1.i,p p

Proof. LetA∈A be a principally polarized abelian surface with CM byK,

deﬁnedoveranumberﬁeldk. Letk be its ﬁeldofmoduli(see[Shi98, p.27]0

for the deﬁnition). By class ﬁeld theory, p splits completely into principal

∗ ∗idealsinK ifandonlyifpsplitscompletelyinH , themaximalunramiﬁed

∗abelian extension ofK ([Cox89, Corollary 5.25]). The ﬁeld of modulik is0

∗contained in H (see [Shi98, Main Theorem 1, p. 112]), but in general it is

not true that k =k . By a theorem of Shimura ([Shi71, Ex 1, p. 525]) (see0

also [Gor97, Proposition 2.1]) ifK is a primitive quartic CM ﬁeld, thenk is

contained in k , so A is deﬁned over k .0 0

Proposition 2.1 of loc. cit. also shows that A has good reduction at any

∗prime β of O . Let A be the reduction of A modulo a prime aboveH p

p. Then because p splits completely in the Galois closure of K, A is or-p

dinary ([Gor97, Theorems 1 and 2]) and because p splits completely into

∗principal ideals in K , A is deﬁned over F . By condition 1(b) of Theo-p p

rem 1, A is the Jacobian of a genus 2 curve C over F ([OU73]). Then Cp p

is an element of T .pA CRT ALGORITHM FOR COMPUTING IGUSA CLASS POLYNOMIALS 5

We must show that this correspondence is one-to-one and onto. To show

that it is one-to-one, we can generalize the argument in [Lan73, Theorem

13, p. 183f.]: Let A,B ∈A, and for p∈S let A and B be the reductionsp p

of A and B as above. Assume that A and B are isomorphic overF , andp p p

let ε :B →A be an isomorphism. The varieties A and B both have CMp p

by K, hence there exists an isogeny λ : A → B ([Shi98, Corollary, p. 41])

givingrisetoareducedisogenyλ :A →B . Sincethe endomorphism ringp p p

of A is preserved under the reduction map, there exists α ∈ End(A) such

that the reduction α satisﬁes α =ε◦λ . Let C be the image of the mapp p p

λ×α : A×A → B×A. With a similar argument as in [Lan73, p. 184],

one can then show that C is the graph of an isomorphism between A and

B. Similarly, if there is an isomorphism of the principal polarizations onAp

and B then this isomorphism lifts to an isomorphism of the polarizationsp

on A and B. This shows that the correspondence is one-to-one.

Thecorrespondenceisontobecause, givenagenus2curveC overF withp

CM by K representing a class of T , its Jacobian J(C) is ordinary and sop

it can be lifted, along with its endomorphism ring and its polarization, to

its “Serre-Tate canonical lift” A deﬁned over the Witt vectors W(F ) =Zp p

([Mes72, Theorem 3.3, p.172]). Let L be the ﬁeld generated over Q by all

the coeﬃcients of the equations deﬁning A. Then A is deﬁned over L and

since L has ﬁnite transcendence degree overQ, we can embed it intoC. So

we can lift J(C) to an abelian variety with CM by K deﬁned overC.

By assumption, no prime above p ∈ S is a prime of bad reduction for a

genus 2 curve with CM by K, so by [GL04, Cor 5.1.2], p∈S is coprime to

the denominators of the class polynomials H (X). We claim that reducingi

the coeﬃcients of H modulo p gives the same result as taking the polyno-i

mialwhoserootsaretheabsoluteIgusainvariantsofthecurvesoverF withp

Jacobians equal to the reductions modulo a prime above p of the abelian

varietiesA representing the classes ofA. Since the absolute Igusa invariants

are rational functions in the coeﬃcients of the curve, the order of computa-

tion of the invariants and reduction modulo a prime can be reversed as long

as the primes in the denominator are avoided and an appropriate model for

the curve is chosen.

Theorem 3. Suppose the factorization of the denominators of the Igusa

class polynomials is known. Letν be the largest numerator of the coeﬃcients

of the H (in lowest terms), and let λ be the least common multiple of thei

denominators of the coeﬃcients of the H (i = 1,2,3). Let S be a set ofi Q

rational primes such that S ∩B = ∅ and p > c, where c = λ·ν.p∈S

Then the Chinese Remainder Theorem can be used to compute the class

polynomials H (X)∈Q[X] from the collection {H } , i= 1,2,3.i i,p p∈S

Proof. By assumption λ is prime to all p∈S. The polynomials

F (X) :=λ·H (X) i= 1,2,3i i¨6 KIRSTEN EISENTRAGER AND KRISTIN LAUTER

have integer coeﬃcients. For each p∈S let

F :=F (modp) =λ·H (modp).i,p i i,p

ApplytheChineseRemainderTheoremtothecollection{F } toobtaini,p p∈S Q

a polynomial which is congruent to F ∈Z[X] modulo the product p.i p∈S

Sincec was taken to beλ times the largest numerator of the coeﬃcients, we

−1have found F , and so H =λ ·F . i i i

Remark 4. It was proved in [GL04] that the primes dividing the denomi-

nators are bounded eﬀectively in terms of the ﬁeld K by a quantity related

to the discriminant. The power to which each prime in the denominator

appears has also been bounded in recent work of Eyal Goren, and so we can

conclude that we have a bound on the denominators of the class polynomials.

Proof of Theorem 1. The proof of Theorem 1 now follows immediately from

Theorem 2 and Theorem 3.

5. Implementation

5.1. The possible group orders for each p. Suppose that C is a genus

2 curve deﬁned over F with CM by K. To ﬁnd all possible group ordersp

for J(C)(F ), let π∈O correspond to the Frobenius endomorphism of C.p K

Since the Frobenius satisﬁes ππ = p, it follows that the relative norm of

2π is p, i.e. N (π) = p, and hence N(π) = N (π) = p . So if K isK/K K/Q0

ﬁxed, primes p for which there exist genus 2 curves modulo p with CM by

K are primes for which there are solutions to the relative norm equation:

N (π)=p.K/K0

Proposition 4. Fix a primitive quartic CM ﬁeld K, and a rational prime

p. Assume that there are no non-trivial roots of unity in K. Then

(A) There are either 0, 2 or 4 possibilities for the group order #J(C)(F )p

of curves C with CM by K.

(B)Undertheadditionalassumptionthatpsplitscompletelyintoprincipal

∗ideals in K and splits completely in K, there are always 2 possible group

orders in the cyclic case and 4 possible group orders in the non-Galois case.

Proof. We consider all possible decompositions of the prime p in K.

Case 1: There exists a prime ideal p of K above p that does not split in0

K. In this case there is no solution to the relative norm equation.

Case2: TherationalprimepisinertinK /Q, andtheprimepofK above0 0

p splits inK withP |p andP |p. We haveP =P . In this case there are1 2 1 2

2two ideals of norm p ,P andP . IfP is not principal, then there are no1 2 1

solutions to the norm equation. If P is principal with generator π, then1

P = (π), and ππ =p. The elements π and π are Galois conjugates, so by2

Honda-Tate π and −π give rise to all possible group orders. Let π := π,1Q4and let π ,...,π be its conjugates over Q. Then m = (1−π ) and2 4 1 ii=1Q4m = (1−(−π )) are the 2 possible group orders for the Jacobian.2 ii=1A CRT ALGORITHM FOR COMPUTING IGUSA CLASS POLYNOMIALS 7

Case 3: p splits completely in K/Q, with P ,...,P lying above p and1 4

with P =P , and P =P . Then P :=P P , Q :=P P , and P and1 2 3 4 1 3 1 4

Q are the only ideals with relative norm p.

Subcase (a) If K/Q is Galois, then the Galois group is cyclic, since

we assumed that K was a primitive CM ﬁeld ([Shi98, p. 65]). Let σ be a

2 3σ σ σgenerator of Gal(K/Q). Then w.l.o.g. P =P ,P =P , andP =P .2 3 41 1 1

3σ σ σ σThusP =P P = (P P ) =Q , so ifP is principal, so isQ, and their1 11 1

σgenerators, ω and ω give rise to isogenous curves. Hence ifP is principal,

then there are two possible group orders as before, and if it is not principal,

then the relative norm equation has no solution.

Subcase (b) IfK/Q is not Galois, then the Galois group of its splitting

ﬁeld is the dihedral group D ([Shi98, p. 65]). In this case P and Q are4

not Galois conjugates. So if both P and Q are principal, then there are

4 possible group orders, if only one of them is principal, then there are 2

possible group orders, and otherwise there are no solutions to the relative

norm equation.

Statement (A) follows from the 3 cases considered above. Statement

∗(B) concerns Case 3. If K is Galois, then K = K and the additional

assumptions imply thatP is principal, and then there are 2 possible group

orders. If K is not Galois, let L be the Galois closure with dihedral Galois

2 4group Gal(L/Q) = hτ,σ : τ ,σ ,τστσi such that K is the ﬁxed ﬁeld of τ

2and the CM type is {1,σ}. Then σ is complex conjugation. According

to [Gor97, Theorem 2], a rational prime p that splits completely in L with

∗P :=pO decomposes as follows in K and K :L

2 2 3 3τ σ τσ σ τσ σ τσpO =P P P P = (PP )(P P )(P P )(P P ),K 1 2 3 4

3 2 3 2∗ ∗ ∗ ∗ τσ σ τσ σ τ σ τσ

∗pO =P P P P = (PP )(P P )(P P )(P P ).K 1 2 3 4

∗ ∗ ∗ ∗By assumption, P , P , P , P are principal. Thus both P and Q are1 2 3 4

∗ ∗ σ ∗ ∗ τprincipal since P = P P = P (P ) , and Q = P P = P (P ) . Thus1 3 1 43 4 1 1

there are 4 possible group orders when K is not Galois.

5.2. Generating the collection of primes S. In practice to generate

a collection of primes belonging to S there are several alternatives. One

approachistorunthroughsmallprimescheckingthesplittingbehaviorinK

∗and K using a computational number theory software package like PARI.

A second approach is to generate solutions to the relative norm equation

∗directly, then check each solution for the splitting in K and K and check

fortheothersolutiontotherelativenormequationinthecasethatK isnot

Galois. One advantage to this approach is that it gives direct control over

the index of Z[π,π] in O in terms of the coeﬃcients c of π, the solutionK i

to the relative norm equation (cf. Proposition 5).

5.3. Computing Igusa class polynomials modulo p. Let p ∈ S. To

computetheIgusaclasspolynomialsmodpwemustﬁndallF -isomorphismp¨8 KIRSTEN EISENTRAGER AND KRISTIN LAUTER

classes of genus 2 curves over F whose Jacobian has CM by K. This canp

be done as follows:

(1) For each triple of Igusa invariants modulop, generate a genus 2 curve

withthoseIgusainvariantsusinganimplementationoftheMestre-Cardona-

Quer algorithm ([Mes91], [CQ02]).

(2) Let N := {(n ,m ),(n ,m ),...,(n ,m )} be the set of possiblep 1 1 2 2 r r

group orders (#C(F ),#J(C)(F )) of curves C which have CM by K asp p

computed above in Section 5.1.

(3) Collect all curvesC such that (#C(F ),#J(C)(F ))∈N as follows:p p p

for each triple of invariants and a corresponding curve C, take a random

pointQonJ(C). MultiplyQbym ,...,m andcheckiftheidentityelement1 r

isobtainedforsomer. Ifnot,thenC doesnotbelongtoT . Ifacurvepassesp

this test, then count the number of points on the curve and its Jacobian

over F to check whether the Jacobian has the right isogeny type. Thisp

procedure obtains all curves in the desired isogeny class. For each curve in

the desired isogeny class, the endomorphism ring of the Jacobian contains

the ring Z[π,π] and is contained in the ring O . The curve is included inK

the setT only if End (J(C)) =O . In the next section, we will show howp KFp

to test this property by computing the endomorphism ring End (J(C)).Fp

6. Computing endomorphism rings of genus 2 curves

6.1. The index of Z[π,π] in O . For a prime p and a Frobenius elementK

π ∈ O , the smaller the index of Z[π,π] in O , the less work it takes toK K

computetheendomorphismring. Forexample, iftheindexis1, thenwecan

determine whetherC ∈T just from counting points onC and its Jacobian.p

Proposition 5 gives a bound for the index ofZ[π,π] in O .K

p √

Proposition5. LetK :=Q(η) be a quartic CM ﬁeld, whereη =i a+b d

with a,b,d∈Z and d and (a,b) square free. Let O be its ring of integers.K

Assume for simplicity that the Frobenius endomorphism of C is of the form√ √

2 2π :=c +c d+(c +c d)η withc ,...,c ∈Z, thata −b d is square free1 2 3 4 1 4

and that the real quadratic subﬁeldK has class number 1. Ifd≡2,3mod4,0

2 2then [O : Z[π,π]] ≤ 8c (c −c d). If d ≡ 1mod4, then [O : Z[π,π]] ≤K 2 K3 4

2 216c (c −c d).2 3 4

Proof. We have

√

(1) π+π−2c = 2c d,1 2

2 2(2) [2c c −c (π+π−2c )](π−π) =4c (c −c d)η,2 3 4 1 2 3 4

√

2 2(3) (c −c d)(π−π) =2(c −c d)η.3 4 3 4

√

2 2SoZ[2c d,4c (c −c d)η]⊆Z[π,π]. SinceK has class number 1, we have2 2 03 4

a relative integral basis of O over O . We can choose a relative basis ofK K0

the form {1,κ}, and by [SW96], in the case that d≡2,3mod4, κ is either

√ √

1.η/2 2.(1+η)/2 3.( d+η)/2 4.(1+ d+η)/2.A CRT ALGORITHM FOR COMPUTING IGUSA CLASS POLYNOMIALS 9

√

In each case the index ofZ[ d,η] in O is 2. For d≡1mod4, κ is eitherK

√ √ √

5.(1+ d+2η)/4 6.(−1+ d+η)/4 7.(−b+ d+2η)/4.

√

Here, in each case the index ofZ[ d,η] in O is 4. We haveK

√ √

Z[π,π]⊆Z[π,π, d]⊆Z[ d,η]⊆O ,K

√ √ √

2 2with [Z[π,π, d] :Z[π,π]] ≤ 2c and [Z[ d,η] :Z[π,π, d]] ≤ 2(c −c d).2 3 4√

If d≡2,3mod4, then [O :Z[ d,η]]= 2, and henceK

2 2[O :Z[π,π]]≤8c (c −c d).K 2 3 4

√

If d≡1mod4, then [O :Z[ d,η]]= 4, and henceK

2 2[O :Z[π,π]]≤16c (c −c d).K 2 3 4

So if we want to minimize the index [O : Z[π,π]] then we have toK

2 2 2 2minimizec (c −c d). Whena −b disnotsquarefreetherepresentationof2 3 4

theringofintegerscanbecomemorecomplicated([SW96]),butthetermwe

2 2needtominimizeisstillc (c −c d). UsingtherelativebasisofO overO2 K K3 4 0

we can also determine which denominators can occur in the coeﬃcients ci

of the Frobenius endomorphism and generalize our argument to the general

case.

6.2. Determining the index of End(J) in O . We can summarize theK

necessary conditions to ensure that [O : End(J)]= 1 as follows:K

Lemma 6. Under the conditions of Section 6.1, to show that the endomor-

phism ring of a curve is the full ring of integers O , it is necessary to testK

whether:

√ √

(1) d is an endomorphism, where 2c d =π+π−2c .2 1

(2) η is an endomorphism, where

2 2(4c (c −c d))η = (2c c −c (π+π−2c ))(π−π).2 2 3 4 13 4

Here the c ’s are the coeﬃcients of π written in the relative basis.i

(3) κ is an endomorphism, where κ is one of the 7 possible elements

2 2listed in Section 6.1 in the case that a −b d is square free.

If any one of these conditions fails, we conclude that the endomorphism

2 2ring of the curve is not the full ring of integers O . When a −b d is notK

square free then the relative integral basis is listed in the table in [SW96,

p. 186]. This algorithm can also be modiﬁed to test whether the endomor-

phism ring of the curve is some other subring of O or to compute theK

endomorphism ring exactly.√

To test whether d, η, and κ are endomorphisms, we express them as

above as polynomials inπ andπ with integral denominators determined by

the c . It will be proved in Section 6.3 below that in each case it suﬃces toi

check whether the numerator acts as zero on the s-torsion, where s is the

denominator.¨10 KIRSTEN EISENTRAGER AND KRISTIN LAUTER

6.3. Action on s-torsion.

Proposition 7. Assume that k is an algebraically closed ﬁeld and that

A,B,C are abelian varieties over k. Let β : A → B, γ : A → C be two

isogenies with β separable and Ker(β)⊆Ker(γ). Then there is a homomor-

phism δ :B →C such that δ·β =γ.

Proof. This proof follows the argument of Remark 7.12 in [Mil98, p. 37].

Since β is separable, we can form the quotient abelian variety A/Ker(β).

FromtheuniversalpropertyofA/Ker(β)wehavearegularmapA/Kerβ →

B, which is again separable and bijective. Since B is nonsingular, this

∼implies that it is an isomorphism. Thus B = A/Ker(β). After identifying

B with A/Ker(β) and using the universal properties of quotients again we

ﬁnd that there is a unique regular mapδ such thatδ·β =γ. Moreover,δ is

automatically a homomorphism because it maps O to O.

Proposition8. Letk be an algebraically closed ﬁeld and letA be an abelian

variety over k. Let R := End A. Let s ∈ R be separable and let A[s] =k

{P ∈A(k):sP =O}=Ker(s). Then A[s] is a faithful R/Rs-module.

Proof. Clearly, A[s] is an R/Rs-module. We have to show that A[s] is a

faithful R/Rs-module; that is, any r ∈ R with r·A[s] = 0 belongs to Rs.

Suppose r is such that r·A[s] = 0. Since s is separable, this implies that

r =ts for some endomorphism t of A by Proposition 7 above applied with

A =B =C, β =s and γ =r. This implies that r ∈Rs, which proves the

claim.

We will frequently use the following

Corollary 9. Let A,k be as in Proposition 8. Let n be a positive integer

coprime to the characteristic of k. Suppose that α : A → A is an endo-

morphism, with A[n]⊆Ker(α), i.e. α acts as zero on the n-torsion. Then

α = β ·n = n·β, for some endomorphism β, i.e. α is divisible by n in

R =End (A).k

6.4. Computing the index using division polynomials. In [Can94],

Cantor ﬁnds recursive formulae for division polynomials for hyperelliptic

curves with one point at inﬁnity, P . The rth division polynomials he∞

x−X x−Xdeﬁnes are (δ (X), (X)) such that (δ ( ), ( )) representsr·(x,y),r r r 2 r 24y 4y

where (x,y) is a point on the curve thought of as the point (x,y)−P∞

on the Jacobian. For a general point on the Jacobian represented as D =

P +P −P , we see that rD = 0 iﬀ rP = −rP . If P = (x ,y ) and1 2 ∞ 1 2 1 1 1

P =(x ,y ),thenwecanwritedownasystemofequationsandanideal,I ,2 2 2 r

deﬁning the solutions to the system, whereI is an ideal inF [x ,x ,y ,y ].r p 1 2 1 2

Various ways of ﬁnding the ideal I have been investigated, from Gr¨obnerr

bases to resultant computations (see [GH00] and [GS03]).

The ideal I can be used to test the action of endomorphisms on the r-r

ktorsion. For example, to check that π (or any other polynomial in π) acts