Math K-6 WS

Published by

  • expression écrite
Early Stage 1 Sample Units of Work
  • red blocks beside the line
  • students with blue shirts
  • many counters
  • wm sample units
  • students role-play buying items at the shop
  • dot cards
  • play
  • numbers
  • objects
  • students
Published : Monday, March 26, 2012
Reading/s : 24
Origin : research.microsoft.com
Number of pages: 14
See more See less

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 field. For a primitive quartic
CM field, 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 finite field 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 field. Our method generalizes the
algorithm for finding the Hilbert Class polynomial given in [ALV04] to the
genus 2 situation. Given a primitive quartic CM field K, for each small
prime p in a certain set we determine the Igusa class polynomial modulo
p by finding 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
coefficients.
Several difficulties arise in the genus 2 situation which are absent in the
elliptic curve case. In this paper we resolve the following issues: the field of
definition 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 different ways: from modular functions evaluated on a
period matrix or as invariants of the binary sextic defining 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 first 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.
GivenaprimitivequarticCMfieldK,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 defined to bei
Y
H := (X−j (A)).i i
A∈A
It is known ([Shi98]) that roots of these polynomials generate unramified
abelian extensions of the reflex field 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 field (cf. Section 3).
In this paper we prove the following theorem.
Theorem 1. Given a primitive quartic CM fieldK, the following algorithm
finds 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 reflex 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 effectively 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 field of the reflex of K.6
A CRT ALGORITHM FOR COMPUTING IGUSA CLASS POLYNOMIALS 3
Our algorithm has not been efficiently 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 field, K, is always assumed to be a primitive quartic CM
field, with ring of integers O . The real quadratic subfield 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 reflex of the quartic CM field 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 field 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 ), find a genus 2 curve C over the prime field1 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 find K, the quartic CM field1 2
such that the curve C has CM by K, by finding the quartic polynomial
2 2satisfied 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 fields K. If K is2
aquarticCMfield,thenK isnotprimitiveiffK/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 iffa −b d =k for
some integer k ([KW89, p. 135]). Assume further that K does not contain
a cyclotomic field.¨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 finite fieldF 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 different triple of invariants may be
tried until the desired group order is obtained.
4. Proof of Theorem 1
GivenaprimitivequarticCMfieldK,letAbeasystemofrepresentatives
of the isomorphism classes of principally polarized abelian surfaces over C
withCMbyK. EachelementofAhasafieldofdefinitionk whichisafinite
extension of Q ([Shi98, Prop. 26, p. 96]). For any prime p ∈ S satisfying
the conditions of Theorem 1, the setT was defined 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 field and let p ∈ S be a
rational prime that satisfies the conditions of Theorem 1. Then
Y
H (X) = (X−j (C)),i,p i
C∈Tp
where H (X) and T are defined as in Theorem 1.i,p p
Proof. LetA∈A be a principally polarized abelian surface with CM byK,
definedoveranumberfieldk. Letk be its fieldofmoduli(see[Shi98, p.27]0
for the definition). By class field theory, p splits completely into principal
∗ ∗idealsinK ifandonlyifpsplitscompletelyinH , themaximalunramified
∗abelian extension ofK ([Cox89, Corollary 5.25]). The field 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 field, thenk is
contained in k , so A is defined 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 defined 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 α satisfies α =ε◦λ . 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 defined over the Witt vectors W(F ) =Zp p
([Mes72, Theorem 3.3, p.172]). Let L be the field generated over Q by all
the coefficients of the equations defining A. Then A is defined over L and
since L has finite transcendence degree overQ, we can embed it intoC. So
we can lift J(C) to an abelian variety with CM by K defined 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 coefficients 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 coefficients 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 coefficients
of the H (in lowest terms), and let λ be the least common multiple of thei
denominators of the coefficients 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 coefficients. 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 coefficients, 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 effectively in terms of the field 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 defined over F with CM by K. To find all possible group ordersp
for J(C)(F ), let π∈O correspond to the Frobenius endomorphism of C.p K
Since the Frobenius satisfies ππ = 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
fixed, 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 field 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 field ([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
field 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 fixed field 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 coefficients 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
computetheIgusaclasspolynomialsmodpwemustfindallF -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 field, 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 subfieldK 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 coefficients 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 coefficients 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 modified 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 suffices 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 field 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
find 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 field 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 finds recursive formulae for division polynomials for hyperelliptic
curves with one point at infinity, P . The rth division polynomials he∞
x−X x−Xdefines 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 iff rP = −rP . If P = (x ,y ) and1 2 ∞ 1 2 1 1 1
P =(x ,y ),thenwecanwritedownasystemofequationsandanideal,I ,2 2 2 r
defining the solutions to the system, whereI is an ideal inF [x ,x ,y ,y ].r p 1 2 1 2
Various ways of finding 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

Be the first to leave a comment!!

12/1000 maximum characters.