стр. 1(всего 2)СОДЕРЖАНИЕ >>
Chapter 10
Complex Multiplication

The endomorphisms of an elliptic curve E always include multiplication by
arbitrary integers. When the endomorphism ring of E is strictly larger than Z,
we say that E has complex multiplication. As weвЂ™ll see, elliptic curves over
C with complex multiplication correspond to lattices with extra symmetry.
Over п¬Ѓnite п¬Ѓelds, all elliptic curves have complex multiplication, and often the
Frobenius provides one of the additional endomorphisms. In general, elliptic
curves with complex multiplication form an interesting and important class
of elliptic curves, partly because of their extra structure and partly because
of their frequent occurrence.

10.1 Elliptic Curves over C
Consider the elliptic curve E given by y 2 = 4x3 в€’ 4x over C. As we saw
in Section 9.4, E corresponds to the torus C/L, where L = ZП‰ + ZiП‰, for
a certain П‰ в€€ R. Since L is a square lattice, it has extra symmetries. For
example, rotation by 90в—¦ sends L into itself. This can be expressed by saying
that iL = L. Using the deп¬Ѓnition of the Weierstrass в„˜-function, we easily see
that
1 1 1
в€’2
в„˜(iz) = +
(iz)2 (iz в€’ П‰)2 П‰
П‰=0

1 1 1
в€’
= +
(iz)2 (iz в€’ iП‰)2 (iП‰)2
iП‰=0
= в€’в„˜(z).
Diп¬Ђerentiation yields
в„˜ (iz) = iв„˜ (z).
On the elliptic curve E, we obtain the endomorphism given by
i(x, y) = (в€’x, iy).

311

В© 2008 by Taylor & Francis Group, LLC
312 CHAPTER 10 COMPLEX MULTIPLICATION

Therefore, the map
z в†’ iz
gives a map

(x, y) = (в„˜(z), в„˜ (z)) в†’ (в„˜(iz), в„˜ (iz)) = (в€’x, iy).

This is a homomorphism from E(C) to E(C) and it is clearly given by rational
functions. Therefore, it is an endomorphism of E, as in Section 2.9. Let

Z[i] = {a + bi | a, b в€€ Z}.

Then Z[i] is a ring, and multiplication by elements of Z[i] sends L into it-
self. Correspondingly, if a + bi в€€ Z[i] and (x, y) в€€ E(C), then we obtain an
endomorphism of E deп¬Ѓned by

(x, y) в†’ (a + bi)(x, y) = a(x, y) + b(в€’x, iy).

Since multiplication by a and b can be expressed by rational functions, mul-
tiplication of points by a + bi is an endomorphism of E, as in Section 2.9.
Therefore,
Z[i] вЉ† End(E),
where End(E) denotes the ring of endomorphisms of E. (WeвЂ™ll show later
that this is an equality.) Therefore, End(E) is strictly larger than Z, so E
has complex multiplication. Just as Z[i] is the motivating example for a lot
of ring theory, so is E the prototypical example for complex multiplication.
We now consider endomorphism rings of arbitrary elliptic curves over C.
Let E be an elliptic curve over C, corresponding to the lattice

L = ZП‰1 + ZП‰2 .

Let О± be an endomorphism of E. Recall that this means that О± is a homo-
morphism from E(C) to E(C), and that О± is given by rational functions:

О±(x, y) = (R(x), yS(x))

for rational functions R, S. The map

О¦ : C/L в†’ E(C), О¦(z) = (в„˜(z), в„˜ (z))

(see Theorem 9.10) is an isomorphism of groups. The map

О±(z) = О¦в€’1 (О±(О¦(z)))
Лњ

is therefore a homomorphism from C/L to C/L. If we restrict to a suп¬ѓciently
small neighborhood U of z = 0, we obtain an analytic map from U to C such
that
О±(z1 + z2 ) в‰Ў О±(z1 ) + О±(z2 ) (mod L)
Лњ Лњ Лњ

В© 2008 by Taylor & Francis Group, LLC
313
SECTION 10.1 ELLIPTIC CURVES OVER C

for all z1 , z2 в€€ U . By subtracting an appropriate element of L, we may
assume that О±(0) = 0. By continuity, О±(z) is near 0 when z is near 0. If U is
Лњ Лњ
suп¬ѓciently small, we may therefore assume that

О±(z1 + z2 ) = О±(z1 ) + О±(z2 )
Лњ Лњ Лњ

for all z1 , z2 в€€ U (since both sides are near 0, they can diп¬Ђer only by the
element 0 в€€ L). Therefore, for z в€€ U , we have
О±(z + h) в€’ О±(z)
Лњ Лњ
О± (z) = lim
Лњ
h
hв†’0
О±(z) + О±(h) в€’ О±(z)
Лњ Лњ Лњ
= lim
h
hв†’0
О±(h) в€’ О±(0)
Лњ Лњ
= lim = О± (0).
Лњ
h
hв†’0

Let ОІ = О± (0). Since О± (z) = ОІ for all z в€€ U , we must have
Лњ Лњ

О±(z) = ОІz
Лњ

for all z в€€ U .
Now let z в€€ C be arbitrary. There exists an integer n such that z/n в€€ U .
Therefore,
О±(z) в‰Ў nЛњ (z/n) = n(ОІz/n) = ОІz (mod L),
Лњ О±
so the endomorphism О± is given by multiplication by ОІ. Since О±(L) вЉ† L, it
Лњ Лњ
follows that
ОІL вЉ† L.
We have proved half of the following.

THEOREM 10.1
Let E be an elliptic curve over C corresponding to the lattice L. Then

{ОІ в€€ C | ОІL вЉ† L}.
End(E)

PROOF We have shown that all endomorphisms are given by numbers
ОІ. We need to show that all such ОІвЂ™s give endomorphisms. Suppose ОІ в€€ C
satisп¬Ѓes ОІL вЉ† L. Then multiplication by ОІ gives a homomorphism

ОІ : C/L в†’ C/L.

We need to show that the corresponding map on E is given by rational func-
tions in x, y.
The functions в„˜(ОІz) and в„˜ (ОІz) are doubly periodic with respect to L, since
ОІL вЉ† L. By Theorem 9.3, there are rational functions R and S such that

в„˜(ОІz) = R(в„˜(z)), в„˜ (ОІz) = в„˜ (z)S(в„˜(z)).

В© 2008 by Taylor & Francis Group, LLC
314 CHAPTER 10 COMPLEX MULTIPLICATION

Therefore, multiplication by ОІ on C/L corresponds to the map
(x, y) в†’ (R(x), yS(x))
on E. This is precisely the statement that ОІ induces an endomorphism of E.

Theorem 10.1 imposes rather severe restrictions on the endomorphism ring
of E. WeвЂ™ll show below that End(E) is either Z or an order in an imaginary
quadratic п¬Ѓeld. First, we need to say what this means. WeвЂ™ll omit the proofs
of the following facts, which can be found in many books on algebraic number
theory. Let d > 0 be a squarefree integer and let
в€љ
в€љ
K = Q( в€’d) = {a + b в€’d | a, b в€€ Q}.
Then K is called an imaginary quadratic п¬Ѓeld. The largest subring of K
that is also a п¬Ѓnitely generated abelian group is
вЋ§ в€љ
вЋЄ Z 1+ в€’d if d в‰Ў 3 (mod 4)
вЋЁ 2
OK =
вЋЄв€љ
Z в€’d if d в‰Ў 1, 2 (mod 4),
where, in these two cases, Z[Оґ] = {a+bОґ | a, b в€€ Z}. An order in an imaginary
quadratic п¬Ѓeld is a ring R such that Z вЉ‚ R вЉ† OK and Z = R. Such an order
is a п¬Ѓnitely generated abelian group and has the form
R = Z + Zf Оґ,
в€љ в€љ
where f > 0 and where Оґ = (1 + в€’d)/2 or в€’d, corresponding respectively
to the two cases given above. The integer f is called the conductor of R and
is the index of R in OK . The discriminant of R is
в€’f 2 d if d в‰Ў 3 (mod 4)
DR =
в€’4f 2 d if d в‰Ў 1, 2 (mod 4).
It is the discriminant of the quadratic polynomial satisп¬Ѓed by f Оґ.
A complex number ОІ is an algebraic integer if it is a root of a monic
polynomial with integer coeп¬ѓcients. The only algebraic integers in Q are the
elements of Z. If ОІ is an algebraic integer in a quadratic п¬Ѓeld, then there are
integers b, c such that ОІ 2 + bОІ + c = 0. The set of algebraic integers in an
imaginary quadratic п¬Ѓeld K is precisely the ring OK deп¬Ѓned above. An order
is therefore a subring (not equal to Z) of the ring of algebraic integers in K.
If ОІ в€€ C is an algebraic number (that is, a root of a polynomial with rational
coeп¬ѓcients), then there is an integer u = 0 such that uОІ is an algebraic integer.

THEOREM 10.2
Let E be an elliptic curve over C. Then End(E) is isomorphic either to Z
or to an order in an imaginary quadratic п¬Ѓeld.

В© 2008 by Taylor & Francis Group, LLC
315
SECTION 10.1 ELLIPTIC CURVES OVER C

PROOF Let L = ZП‰1 + ZП‰2 be the lattice corresponding to E, and let

R = {ОІ в€€ C | ОІL вЉ† L}.

It is easy to see that Z вЉ† R and that R is closed under addition, subtraction,
and multiplication. Therefore, R is a ring. Suppose ОІ в€€ R. There exist
integers j, k, m, n such that

ОІП‰1 = jП‰1 + kП‰2 , ОІП‰2 = mП‰1 + nП‰2 .

Then
ОІ в€’ j в€’k П‰1
= 0,
в€’m ОІ в€’ n П‰2
so the determinant of the matrix is 0. This implies that

ОІ 2 в€’ (j + n)ОІ + (jn в€’ km) = 0.

Since j, k, m, n are integers, this means that ОІ is an algebraic integer, and
that ОІ lies in some quadratic п¬Ѓeld K.
Suppose ОІ в€€ R. Then (ОІ в€’ j)П‰1 в€’ kП‰2 = 0 gives a dependence relation
between П‰1 and П‰2 with real coeп¬ѓcients. Since П‰1 and П‰2 are linearly inde-
pendent over R, we have ОІ = j в€€ Z. Therefore, R в€© R = Z.
Suppose now that R = Z. Let ОІ в€€ R with ОІ в€€ Z. Then ОІ is an algebraic
integer in a quadratic п¬Ѓeld K. Since ОІ в€€ R, the п¬Ѓeld K must be imaginary
в€љ
quadratic, say в€љ = Q( в€’d). Let ОІ в€€ Z be another element of R. Then
K
ОІ в€€ K = Q( в€’d ) for some d . Since ОІ + ОІ also must lie in a quadratic
п¬Ѓeld, it follows (see Exercise 10.1) that K = K . Therefore, R вЉ‚ K, and since
all elements of R are algebraic integers, we have

R вЉ† OK .

Therefore, if R = Z, then R is an order in an imaginary quadratic п¬Ѓeld.

Example 10.1
Let E be y 2 = 4x3 в€’ 4x. We showed at the beginning of this section that
Z[i] вЉ† End(E). Since End(E) is an order in Q(i) and every such order is
contained in the ring Z[i] of algebraic integers in Q(i), we must have

End(E) = Z[i].

Suppose from now on that E has complex multiplication, which means that
R = End(E) is an order in an imaginary quadratic п¬Ѓeld K. Rescaling L does
not change R, so we may consider
в€’1
П‰2 L = Z + ZП„,

В© 2008 by Taylor & Francis Group, LLC
316 CHAPTER 10 COMPLEX MULTIPLICATION

в€’1
with П„ в€€ H = {z в€€ C | (z) > 0}. Let ОІ в€€ R with ОІ в€€ Z. Since 1 в€€ П‰2 L, we
have ОІ В· 1 = m В· 1 + nП„ with m, n в€€ Z and n = 0. Therefore,

П„ = (ОІ в€’ m)/n в€€ K. (10.1)

Let u be an integer such that uП„ в€€ R. Such an integer exists since П„ multiplied
by n is in OK , and R is of п¬Ѓnite index in OK . Then
в€’1
L = uП‰2 L = Zu + ZuП„ вЉ† R.

Then L is a nonempty subset of R that is closed under addition and sub-
traction, and is closed under multiplication by elements of R (since L is a
rescaling of L). This is exactly what it means for L to be an ideal of R. We
have proved the п¬Ѓrst half of the following.

PROPOSITION 10.3
Let R be an order in an imaginary quadratic п¬Ѓeld. Let L be a lattice such
that R = End(C/L). Then there exists Оі в€€ CГ— such that ОіL is an ideal of
R. Conversely, if L is a subset of C and Оі в€€ CГ— is such that ОіL is an ideal
of R, then L is a lattice and R вЉ† End(C/L).

PROOF By End(C/L), we mean End(E), where E is the elliptic curve
corresponding to L under Theorem 9.10.
We proved the п¬Ѓrst half of the proposition above. For the converse, assume
that ОіL is an ideal of R. Let 0 = x в€€ ОіL. Then

Rx вЉ† ОіL вЉ† R.

Since R and therefore also Rx are abelian groups of rank 2 (that is, isomorphic
to ZвЉ•Z), the same must be true for ОіL. This means that there exist П‰1 , П‰2 в€€ L
such that
ОіL = ОіZП‰1 + ОіZП‰2 .
Since R contains two elements linearly independent over R, so does Rx, and
therefore so does L. It follows that П‰1 and П‰2 are linearly independent over
R. Therefore, L = ZП‰1 + ZП‰2 is a lattice. Since ОіL is an ideal of R, we have
RОіL вЉ† ОіL, and therefore RL вЉ† L. Therefore R вЉ† End(C/L).

Note that sometimes R is not all of End(C/L). For example, suppose
R = Z[2i] = {a + 2bi | a, b в€€ Z} and let L = Z[i]. Then R is an order in Q(i)
and RL вЉ† L, but End(C/L) = Z[i] = R.
We say that two lattices L1 , L2 are homothetic if there exists Оі в€€ CГ—
such that ОіL1 = L2 . We say that two ideals I1 , I2 of R are equivalent if there
exists О» в€€ K Г— such that О»I1 = I2 . Regard I1 and I2 as lattices, and suppose
I1 and I2 are homothetic. Then ОіI1 = I2 for some Оі. Choose any x = 0 in I1 .

В© 2008 by Taylor & Francis Group, LLC
317
SECTION 10.1 ELLIPTIC CURVES OVER C

Then Оіx в€€ I2 вЉ‚ K, so Оі в€€ K. It follows that I1 and I2 are equivalent ideals.
Therefore, we have a bijection

Homothety classes of lattices L Equivalence classes of
в†ђв†’
with RL вЉ† L nonzero ideals of R

It can be shown that the set of equivalence classes of ideals is п¬Ѓnite (when
R = OK , this is just the п¬Ѓniteness of the class number). Therefore, the set of
homothety classes is п¬Ѓnite. This observation has the following consequence.

PROPOSITION 10.4
Let R be an order in an imaginary quadratic п¬Ѓeld and let L be a lattice such
that RL вЉ† L. Then j(L) is algebraic over Q.

PROOF Let E be the elliptic curve corresponding to L. We may assume
that E is given by an equation y 2 = 4x3 в€’g2 xв€’g3 . Let Пѓ be an automorphism
of C. Let E Пѓ be the curve y 2 = 4x3 в€’Пѓ(g2 )xв€’Пѓ(g3 ). If О± is an endomorphism
of E, then О±Пѓ is an endomorphism of E Пѓ , where О±Пѓ means applying Пѓ to all
of the coeп¬ѓcients of the rational functions describing О±. This implies that

End(E Пѓ ).
End(E)

Therefore, the lattice corresponding to E Пѓ belongs to one of the п¬Ѓnitely many
homothety classes of lattices containing R in their endomorphism rings (there
is a technicality here; see Exercise 10.2). Since Пѓ(j(L)) is the j-invariant
of E Пѓ , we conclude that j(L) has only п¬Ѓnitely many possible images under
automorphisms of C. This implies (see Appendix C) that j(L) is algebraic
over Q.

In Section 10.3, weвЂ™ll prove the stronger result that j(L) is an algebraic
integer.

COROLLARY 10.5
Let K be an imaginary quadratic п¬Ѓeld.

1. Let П„ в€€ H. Then C/(ZП„ + Z) has complex multiplication by some order
in K if and only if П„ в€€ K.

2. If П„ в€€ H is contained in K, then j(П„ ) is algebraic.

PROOF We have already shown (see (10.1)) that if there is complex mul-
tiplication by an order in K then П„ в€€ K. Conversely, suppose П„ в€€ K. Then
П„ satisп¬Ѓes a relation
aП„ 2 + bП„ + c,

В© 2008 by Taylor & Francis Group, LLC
318 CHAPTER 10 COMPLEX MULTIPLICATION

where a, b, c are integers and a = 0. It follows that multiplication by aП„ maps
the lattice LП„ = ZП„ + Z into itself (for example, aП„ В· П„ = в€’bП„ в€’ c в€€ LП„ ).
Therefore, C/LП„ has complex multiplication. This proves (1).
Suppose П„ в€€ K. Let R be the endomorphism ring of C/LП„ . By (1), R = Z,
so R is an order in K. By Proposition 10.4, j(П„ ) is algebraic. This proves (2).

10.2 Elliptic Curves over Finite Fields
An elliptic curve E over a п¬Ѓnite п¬Ѓeld Fq always has complex multiplication.
In most cases, this is easy to see. The Frobenius endomorphism П†q is a root
of
X 2 в€’ aX + q = 0,
в€љ в€љ
where |a| в‰¤ 2 q. If |a| < 2 q, then this polynomial has only complex roots,
so П†q в€€ Z. Therefore,
Z = Z[П†q ] вЉ† End(E).
в€љ
When a = В±2 q, the ring of endomorphisms is still larger than Z, so there
is complex multiplication in this case, too. In fact, as weвЂ™ll discuss below, the
endomorphism ring is an order in a quaternion algebra, hence is larger than
an order in a quadratic п¬Ѓeld.
Recall the Hamiltonian quaternions
H = {a + bi + cj + dk | a, b, c, d в€€ Q},
where i2 = j2 = k2 = в€’1 and ij = k = в€’ji. This is a noncommutative
ring in which every nonzero element has a multiplicative inverse. If we allow
the coeп¬ѓcients a, b, c, d to be real numbers or 2-adic numbers, then we still
obtain a ring where every nonzero element has an inverse. However, if a, b, c, d
are allowed to be p-adic numbers (see Appendix A), where p is an odd prime,
then the ring contains nonzero elements whose product is 0 (see Exercise 10.4).
Such elements cannot have inverses. Corresponding to whether there are zero
divisors or not, we say that H is split at all odd primes and is ramiп¬Ѓed at
2 and в€ћ (this use of в€ћ is the common way to speak about the real numbers
when simultaneously discussing p-adic numbers; see Section 8.8).
In general, a deп¬Ѓnite quaternion algebra is a ring of the form
Q = {a + bО± + cОІ + dО±ОІ | a, b, c, d в€€ Q},
where
О±2 , ОІ 2 в€€ Q, О±2 < 0, ОІ 2 < 0, ОІО± = в€’О±ОІ
(вЂњdeп¬ЃniteвЂќ refers to the requirement that О±2 < 0 and ОІ 2 < 0). In such a ring,
every nonzero element has a multiplicative inverse (see Exercise 10.5). If this

В© 2008 by Taylor & Francis Group, LLC
319
SECTION 10.2 ELLIPTIC CURVES OVER FINITE FIELDS

is still the case when we allow p-adic coeп¬ѓcients for some p в‰¤ в€ћ, then we say
that the quaternion algebra is ramiп¬Ѓed at p. Otherwise, it is split at p.
A maximal order O in a quaternion algebra Q is a subring of Q that is
п¬Ѓnitely generated as an additive abelian group, and such that if R is a ring
with O вЉ† R вЉ† Q and such that R is п¬Ѓnitely generated as an additive abelian
group, then O = R. For example, consider the Hamiltonian quaternions H.
The subring Z + Zi + Zj + Zk is п¬Ѓnitely generated as an additive abelian
group, but it is not a maximal order since it is contained in

1+i+j+k
O = Z + Zi + Zj + Z . (10.2)
2
It is not hard to show that O is a ring, and it can be shown that it is a
maximal order of H.
The main theorem on endomorphism rings is the following. For a proof, see
.

THEOREM 10.6
Let E be an elliptic curve over a п¬Ѓnite п¬Ѓeld of characteristic p.

1. If E is ordinary (that is, #E[p] = p), then End(E) is an order in an

2. If E is supersingular (that is, #E[p] = 1), then End(E) is a maximal
order in a deп¬Ѓnite quaternion algebra that is ramiп¬Ѓed at p and в€ћ and
is split at the other primes.

If E is an elliptic curve deп¬Ѓned over Q and p is a prime where E has good
reduction, then it can be shown that End(E) injects into End(E mod p).
Therefore, if E has complex multiplication by an order R in an imaginary
quadratic п¬Ѓeld, then the endomorphism ring of E mod p contains R. If E
mod p is ordinary, then R is of п¬Ѓnite index in the endomorphism ring of
E mod p. However, if E mod p is supersingular, then there are many more
endomorphisms, since the endomorphism ring is noncommutative in this case.
The following result shows how to decide when E mod p is ordinary and when
it is supersingular.

THEOREM 10.7
Let E be an elliptic curve deп¬Ѓned over Q with в€љ reduction at p. Suppose
good
E has complex multiplication by an order in Q( в€’D). If в€’D is divisible by
p, or if в€’D is not a square mod p, then E mod p is supersingular. If в€’D is
a nonzero square mod p, then E mod p is ordinary.

For a proof, see [70, p. 182].

В© 2008 by Taylor & Francis Group, LLC
320 CHAPTER 10 COMPLEX MULTIPLICATION

Example 10.2
Let E be the elliptic curve y 2 = x3 в€’ x. It has good reduction for all primes
p = 2. The endomorphism ring R of E is Z[i], where

i(x, y) = (в€’x, iy)
в€љ
(see Section 10.1). This endomorphism ring is contained in Q( в€’4), where
we use в€’D = в€’4 since it is the discriminant of R. We know that в€’4 is a
square mod an odd prime p if and only if p в‰Ў 1 (mod 4). Therefore, E mod
p is ordinary if and only if p в‰Ў 1 (mod 4). This is exactly what we obtained
in Proposition 4.37.
When p в‰Ў 3 (mod 4), it is easy to see that the endomorphism ring of E
mod p is noncommutative. Since ip = в€’i, we have

П†p (i(x, y)) = П†p (в€’x, iy) = (в€’xp , в€’iy p ),

and
i(П†p (x, y)) = i(xp , y p ) = (в€’xp , iy p ).
Therefore,
iП†p = в€’П†p i,
so i and П†p do not commute.

The following result, known as DeuringвЂ™s Lifting Theorem, shows that
the method given in Theorem 10.7 for obtaining ordinary elliptic curves mod
p with complex multiplication is essentially the only way. Namely, it implies
that an elliptic curve with complex multiplication over a п¬Ѓnite п¬Ѓeld can be
obtained by reducing an elliptic curve with complex multiplication in charac-
teristic zero.

THEOREM 10.8
Let E be an elliptic curve deп¬Ѓned over a п¬Ѓnite п¬Ѓeld and let О± be an endo-
Лњ
morphism of E. Then there exists an elliptic curve E deп¬Ѓned over a п¬Ѓnite
Лњ
extension K of Q and an endomorphism О± of E such that E is the reduction
Лњ
Лњ
of E mod some prime ideal of the ring of algebraic integers of K and the
reduction of О± is О±.
Лњ

For a proof in the ordinary case, see [70, p. 184].
It is not possible to extend the theorem to lifting two arbitrary endomor-
phisms simultaneously. For example, the endomorphisms i and П†p in the
above example cannot be simultaneously lifted to characteristic 0 since they
do not commute. All endomorphism rings in characteristic 0 are commutative.
Finally, we give an example of a supersingular curve in characteristic 2. In
particular, weвЂ™ll show how to identify the maximal order of H in the endo-
morphism ring.

В© 2008 by Taylor & Francis Group, LLC
321
SECTION 10.2 ELLIPTIC CURVES OVER FINITE FIELDS

Example 10.3
Let E be the elliptic curve deп¬Ѓned over F2 by
y 2 + y = x3 .
An easy calculation shows that E(F2 ) consists of 3 points, so
a = 2 + 1 в€’ #E(F2 ) = 2 + 1 в€’ 3 = 0.
Therefore, E is supersingular and the Frobenius endomorphism П†2 satisп¬Ѓes
П†2 + 2 = 0.
2

If (x, y) в€€ E(F2 ), then
2(x, y) = в€’П†2 (x, y) = в€’(x4 , y 4 ) = (x4 , y 4 + 1),
2

since negation on E is given by
в€’(x, y) = (x, y + 1).
By Theorem 10.6, the endomorphism ring is a maximal order in a quaternion
algebra ramiп¬Ѓed at only 2 and в€ћ. We gave such a maximal order in (10.2)
above. LetвЂ™s start by п¬Ѓnding endomorphisms corresponding to i, j, k. Let
П‰ в€€ F4 satisfy
П‰ 2 + П‰ + 1 = 0.
Deп¬Ѓne endomorphisms i, j, k by
i(x, y) = (x + 1, y + x + П‰)
j(x, y) = (x + П‰, y + П‰ 2 x + П‰)
k(x, y) = (x + П‰ 2 , y + П‰x + П‰).
An easy calculation shows that
j(i(x, y)) = в€’k(x, y)
i(j(x, y)) = k(x, y),
and that
i2 = k2 = k2 = в€’1.
A straightforward calculation yields
(1 + i + j + k)(x, y) = (П‰x4 , y 4 ) = П†2 (П‰x, y) = в€’2(П‰(x, y)),
2

where П‰ is used to denote the endomorphism (x, y) в†’ (П‰x, y). Therefore,
1+i+j+k
= в€’П‰ в€€ End(E).
2
It follows that
1+i+j+k
вЉ† End(E).
Z + Zi + Zj + Z
2
In fact, by Theorem 10.6, this is the whole endomorphism ring.

В© 2008 by Taylor & Francis Group, LLC
322 CHAPTER 10 COMPLEX MULTIPLICATION

10.3 Integrality of j-invariants
At the end of Section 10.1, we showed that the j-invariant of a lattice,
or of a complex elliptic curve, with complex multiplication by an order in an
imaginary quadratic п¬Ѓeld is algebraic over Q. This means that the j-invariant
is a root of a polynomial with rational coeп¬ѓcients. In the present section, we
show that this j-invariant is an algebraic integer, so it is a root of a monic
polynomial with integer coeп¬ѓcients.

THEOREM 10.9
Let R be an order in an imaginary quadratic п¬Ѓeld and let L be a lattice with
RL вЉ† L. Then j(L) is an algebraic integer. Equivalently, let E be an elliptic
curve over C with complex multiplication. Then j(E) is an algebraic integer.

The proof of the theorem will occupy the remainder of this section. The
в€љ
theorem has an amusing consequence. The ring R = Z 1+ 2 в€’163
is a prin-
cipal ideal domain (see ), so there is only one equivalence class of ideals
of R, namely the one represented by R. The proof of Proposition 10.4 shows
that all automorphisms of C must п¬Ѓx j(R), where R is regarded as a lattice.
Therefore, j(R) в€€ Q. The only algebraic integers in Q are the elements of Z,
so j(R) в€€ Z. Recall that j(П„ ) is the j-invariant of the lattice ZП„ + Z, and that

1
+ 744 + 196884q + 21493760q 2 + В· В· В· ,
j(П„ ) =
q
в€љ
1+ в€’163
2ПЂiП„
where q = e . When П„ = , we have R = ZП„ + Z and
2
в€љ
в€’ПЂ 163
q = в€’e .

Therefore,
в€љ в€љ в€љ
ПЂ 163 в€’ПЂ 163 в€’2ПЂ 163
в€’e + 744 в€’ 196884e + В· В· В· в€€ Z.
+ 21493760e

Since в€љ в€љ
в€’ПЂ 163 в€’2ПЂ 163
+ В· В· В· < 10в€’12 ,
в€’ 21493760e
196884e
в€љ
ПЂ 163
diп¬Ђers from an integer by less than 10в€’12 . In fact,
we п¬Ѓnd that e
в€љ
ПЂ 163
e = 262537412640768743.999999999999250 . . . ,

as predicted. In the days when high precision calculation was not widely
в€љ
available, it was often claimed as a joke that eПЂ 163 was an integer. Any
calculation with up to 30 places of accuracy seemed to indicate that this was

В© 2008 by Taylor & Francis Group, LLC
323
SECTION 10.3 INTEGRALITY OF j-INVARIANTS

the case. This was in contradiction to the Gelfond-Schneider theorem, which
implies that such a number must be transcendental.
We now start the proof of the theorem. If L = ZП‰1 + ZП‰2 is a lattice, we
may divide by П‰2 and thus assume that

L = ZП„ + Z,

with П„ в€€ H. If ОІ в€€ R, then ОІL вЉ† L implies that there exist integers j, k, m, n
with
П„ jk П„
ОІ = .
1 mn 1
Let N = jnв€’km be the determinant of the matrix. Rather than concentrating
only on ОІ, it is convenient to consider all 2 Г— 2 matrices with determinant N
simultaneously.

LEMMA 10.10
Let N be a positive integer and let SN be the set of matrices of the form

ab
0d

with a, b, d в€€ Z, ad = N , and 0 в‰¤ b < d. If M is a 2 Г— 2 matrix with integer
entries and determinant N , then there is a unique matrix S в€€ SN such that

M S в€’1 в€€ SL2 (Z).

In other words, if we say that two matrices M1 , M2 are left SL2 (Z)-equivalent
when there exists a matrix X в€€ SL2 (Z) with XM1 = M2 , then SN contains
exactly one element in each equivalence class of the set of integer matrices of
determinant N .

pq
PROOF Let be an integer matrix with determinant N . Write
rs
x
p
в€’ =
r y

with gcd(x, y) = 1. There exist w, z в€€ Z such that xz в€’ wy = 1. Then

zw
в€€ SL2 (Z)
yx

and
в€—в€—
zw pq
= .
0в€—
yx rs

В© 2008 by Taylor & Francis Group, LLC
324 CHAPTER 10 COMPLEX MULTIPLICATION

Therefore, we may assume at the start that r = 0, and hence ps = N . By
в€’1 0
multiplying by if necessary, we may also assume that s > 0. Choose
0 в€’1
t в€€ Z such that
0 в‰¤ q + ts < s.
Then
1t pq p q + ts
в€€ SN .
=
01 0s 0 s
Therefore, the elements of SN represent all SL2 (Z)-equivalence classes for
matrices of determinant N .
ai b i
в€€ SN for i = 1, 2 are left
For the uniqueness, suppose that Mi =
0 di
SL2 (Z)-equivalent. Then,
в€’1
a1 /a2 (b1 a2 в€’ a1 b2 )/N a1 b1 a2 b2
в€€ SL2 (Z).
=
0 d1 /d2 0 d1 0 d2

Therefore, a1 /a2 and d1 /d2 are positive integers with product equal to 1, so
they are both equal to 1. Consequently, a1 = a2 and d1 = d2 . This implies
that
b1 a2 в€’ a1 b2 b1 a1 в€’ a1 b2 b 1 в€’ b2
= = .
N a1 d1 d1
Since this must be an integer (because the matrix is in SL2 (Z)), we have

b1 в‰Ў b2 (mod d1 ).

Since 0 в‰¤ b1 , b2 < d1 = d2 , we have b1 = b2 . Therefore, M1 = M2 . This
proves the uniqueness.

ab
в€€ SN , the function
For S =
0d

aП„ + b
(j в—¦ S)(П„ ) = j
d

is analytic in H. Deп¬Ѓne

(X в€’ (j в—¦ S)(П„ )) = ak (П„ )X k ,
FN (X, П„ ) =
Sв€€SN k

so FN is a polynomial in the variable X with coeп¬ѓcients ak (П„ ) that are ana-
lytic functions for П„ в€€ H.

LEMMA 10.11
ak (M П„ ) = ak (П„ ) for all M в€€ SL2 (Z).

В© 2008 by Taylor & Francis Group, LLC
325
SECTION 10.3 INTEGRALITY OF j-INVARIANTS

PROOF If S в€€ SN , then SM has determinant N , so there exists AS в€€
SL2 (Z) and a uniquely determined MS в€€ SN such that AS MS = SM . If
S1 , S2 в€€ SN and MS1 = MS2 , then

Aв€’1 S1 M = MS1 = MS2 = Aв€’1 S2 M,
S1 S2

which implies that AS2 Aв€’1 S1 = S2 . By the uniqueness part of Lemma 10.10,
S1
S1 = S2 . Therefore, the map S в†’ MS is an injection on the п¬Ѓnite set SN ,
hence is a permutation of the set. Since j в—¦ A = j for A в€€ SL2 (Z), we have

(X в€’ j(SM П„ ))
FN (X, M П„ ) =
Sв€€SN

(X в€’ j(AS MS П„ ))
=
Sв€€SN

(X в€’ j(MS П„ ))
=
Sв€€SN

(X в€’ j(SП„ ))
=
Sв€€SN
= FN (X, П„ ).

The next to last equality expresses the fact that S в†’ MS is a permutation of
SN , hence does not change the product over all of SN .
Since FN is invariant under П„ в†’ M П„ , the same must hold for its coeп¬ѓcients
ak (П„ ).

LEMMA 10.12
For each k, there exists an integer n such that

ak (П„ ) в€€ q в€’n Z[[q]],

where Z[[q]] denotes power series in q with integer coeп¬ѓcients. In other words,
ak (П„ ) can be expressed as a Laurent series with only п¬Ѓnitely many negative
terms, and the coeп¬ѓcients are integers.

PROOF The j-function has the expansion
в€ћ
1
j(П„ ) = + 744 + 196884q + В· В· В· = ck q k = P (q),
q
k=в€’1

where the coeп¬ѓcients ck are integers (see Exercise 9.1). Therefore,
в€ћ
ck (О¶ b e2ПЂiaП„ /d )k = P (О¶ b e2ПЂiaП„ /d ),
j((aП„ + b)/d) =
k=в€’1

В© 2008 by Taylor & Francis Group, LLC
326 CHAPTER 10 COMPLEX MULTIPLICATION

where О¶ = e2ПЂi/d . Fix a and d with ad = N .

CLAIM 10.13
dв€’1 d
b 2ПЂiaП„ /d
pk (e2ПЂiaП„ /d )X k
(X в€’ P (О¶ e )) =
b=0 k=0

is a polynomial in X whose coeп¬ѓcients pk are Laurent series in e2ПЂiaП„ /d with
integer coeп¬ѓcients.

In the statement of the claim and in the following, a Laurent series will
always be one with only п¬Ѓnitely many negative terms (in other words, a power
series plus п¬Ѓnitely many terms with negative exponents). Everything in the
claim is obvious except the fact that the coeп¬ѓcients of the Laurent series pk
are integers. One proof of this is as follows. The coeп¬ѓcients of each pk lie in
Z[О¶]. The Galois group of Q(О¶)/Q permutes the factors of the product, hence
leaves the coeп¬ѓcients of pk unchanged. Therefore, they are in Q. But the
elements of Z[О¶] в€© Q are algebraic integers in Q, hence are in Z. This proves
the claim.
For a proof of the claim that does not use Galois theory, consider the matrix
вЋ› вЋћ
0 1 0 В·В·В· 0
вЋњ0 0 1 В·В·В· 0вЋџ
вЋњ вЋџ
Z = вЋњ . . . . . вЋџ.
вЋќ . . . .. . вЋ
... .
1 0 0 В·В·В· 0

Let 0 в‰¤ b < d and let вЋ› вЋћ
1
вЋњ вЋџ
О¶b
вЋњ вЋџ
вЋњ вЋџ
О¶ 2b
vb = вЋњ вЋџ.
вЋњ вЋџ
.
вЋќ вЋ
.
.
О¶ b(dв€’1)
Then Zvb = О¶ b vb . It follows that

P (e2ПЂiaП„ /d Z)vb = P (О¶ b e2ПЂiaП„ /d )vb .

Therefore, the numbers P (О¶ b e2ПЂiaП„ /d ), for 0 в‰¤ b < d, are a complete set of
eigenvalues for the dГ—d matrix P (e2ПЂiaП„ /d Z), so the characteristic polynomial
is
dв€’1
(X в€’ P (О¶ b e2ПЂiaП„ /d )).
b=0

But the entries of the matrix P (e2ПЂiaП„ /d Z) are Laurent series in e2ПЂiaП„ /d with
integer coeп¬ѓcients. Therefore, the coeп¬ѓcients of the characteristic polynomial
are power series in e2ПЂiaП„ /d with integer coeп¬ѓcients. This proves the claim.

В© 2008 by Taylor & Francis Group, LLC
327
SECTION 10.3 INTEGRALITY OF j-INVARIANTS

Since ad = N for each matrix in SN ,
2
e2ПЂiaП„ /d = e2ПЂia П„ /N
.

Therefore, the pk (П„ ) in the claim can be regarded as a Laurent series in
e2ПЂiП„ /N . The claim implies that the coeп¬ѓcients ak (П„ ) of FN (X, П„ ) are Laurent
series in e2ПЂiП„ /N with integer coeп¬ѓcients. To prove the lemma, we need to
remove the N . The matrix
11
в€€ SL2 (Z)
01

acts on H by П„ в†’ П„ + 1. Lemma 10.11 implies that ak (П„ ) is invariant under
П„ в†’ П„ + 1. Since (e2ПЂiП„ /N ) is invariant under П„ в†’ П„ + 1 only when N | , the
Laurent series for ak must be a Laurent series in (e2ПЂiП„ /N )N = e2ПЂiП„ . This
proves Lemma 10.12.

PROPOSITION 10.14
Let f (П„ ) be analytic for П„ в€€ H, and suppose

aП„ + b
= f (П„ )
f
cП„ + d

ab
в€€ SL2 (Z) and all П„ в€€ H. Also, assume
for all
cd

f (П„ ) в€€ q в€’n Z[[q]]

for some integer n. Then f (П„ ) is a polynomial in j with integer coeп¬ѓcients:

f (П„ ) в€€ Z[j].

PROOF Recall that
1
j(П„ ) в€’ в€€ Z[[q]].
q
Write
bn
+ В·В·В· ,
f (П„ ) =
qn
with bn в€€ Z. Then
bnв€’1
f (П„ ) в€’ bn j n = + В·В·В· ,
q nв€’1
with bnв€’1 в€€ Z. Therefore,

bnв€’2
f (П„ ) в€’ bn j n в€’ bnв€’1 j nв€’1 = + В·В·В· .
q nв€’2

В© 2008 by Taylor & Francis Group, LLC
328 CHAPTER 10 COMPLEX MULTIPLICATION

Continuing in this way, we obtain

g(П„ ) = f (П„ ) в€’ bn j n в€’ В· В· В· b0 в€€ qZ[[q]]

for integers bn , . . . , b0 . The function g(П„ ) is analytic in H and vanishes at iв€ћ.
Also, g(П„ ) is invariant under the action of SL2 (Z). Proposition 9.16 says that
if g is not identically zero then a sum of the orders of g at various points is 0.
But these orders are all nonnegative since g is analytic. Moreover, the order
of g at iв€ћ is positive. Therefore the sum of the orders must be positive, hence
cannot be zero. The only possibility is that g is identically zero. This means
that
g(П„ ) = f (П„ ) в€’ bn j n в€’ В· В· В· b0 = 0,
so f (П„ ) в€€ Z[j].

Combining Lemma 10.12 and Proposition 10.14, we obtain the п¬Ѓrst part of
the following.

THEOREM 10.15
Let N be a positive integer.
1. There is a polynomial with integer coeп¬ѓcients

О¦N (X, Y ) в€€ Z[X, Y ]

such that the coeп¬ѓcient of the highest power of X is 1 and such that

FN (X, П„ ) = О¦N (X, j(П„ )).

2. If N is not a perfect square, then

HN (X) = О¦N (X, X) в€€ Z[X]

is nonconstant and the coeп¬ѓcient of its highest power of X is В±1.

PROOF We have already proved the п¬Ѓrst part. For the second part, we
know that

(j в€’ j в—¦ S)
HN (j) = О¦N (j, j) = FN (j, П„ ) =
Sв€€SN

is a polynomial in j with integer coeп¬ѓcients. We need to look at the coeп¬ѓcient
ab
в€€ SN . If we expand the factor
of the highest power of j. Let S =
0d
j в€’ j в—¦ S as a Laurent series in e2ПЂiП„ /N , the п¬Ѓrst term for j is

eв€’2ПЂiП„ = (eв€’2ПЂiП„ /N )N

В© 2008 by Taylor & Francis Group, LLC
329
SECTION 10.3 INTEGRALITY OF j-INVARIANTS

and the п¬Ѓrst term for j в—¦ S is
2
О¶ в€’b eв€’2ПЂiaП„ /d = О¶ в€’b (eв€’2ПЂiП„ /N )a .
Since N is not a perfect square, N = a2 . Therefore, these terms represent
diп¬Ђerent powers of e2ПЂiП„ /N , so they cannot cancel each other. One of them
must be the п¬Ѓrst term of the expansion of j в€’ j в—¦ S, which therefore has
coeп¬ѓcient 1 or в€’О¶ b . In particular, for each factor j в€’ j в—¦ S, the coeп¬ѓcient of
the п¬Ѓrst term of the expansion is a root of unity. The coeп¬ѓcient of the п¬Ѓrst
term of the expansion of HN (j) is the product of these roots of unity, hence
a root of unity. Also, since the terms donвЂ™t cancel each other, the п¬Ѓrst term
of each factor contains a negative power of e2ПЂiП„ /N . Therefore, the п¬Ѓrst term
of the expansion HN (j) is a negative power of q, so HN (X) is nonconstant.
Suppose HN (X) = uX + lower terms. We know that u в€€ Z. Since the
Laurent series for j starts with 1/q,
HN (j) = uq в€’ + higher terms.
We have shown that u is a root of unity. Since it is an integer, u = В±1. This
completes the proof of (2).

The modular polynomial О¦N (X, Y ) has rather large coeп¬ѓcients. For
example,
О¦2 (X, Y ) = в€’X 2 Y 2 + X 3 + Y 3 + 24 В· 3 В· 31 XY (X + Y )
+34 В· 53 В· 4027 XY в€’ 24 В· 34 В· 53 (X 2 + Y 2 )
+28 В· 37 В· 56 (X + Y ) в€’ 212 В· 39 В· 59 ,
and
= X 4 в€’ X 3 Y 3 + 2232X 3 Y 2 в€’ 1069956X 3 Y + 36864000X 3
О¦3 (X, Y )
+2232X 2 Y 3 + 2587918086X 2 Y 2 + 8900222976000X 2 Y
+452984832000000X 2 в€’ 1069956XY 3 + 8900222976000XY 2
в€’770845966336000000XY + 1855425871872000000000X + Y 4
+36864000Y 3 + 452984832000000Y 2 + 1855425871872000000000Y
For О¦N for higher N , see , , .
We can now prove Theorem 10.9. Let R be an order in an imaginary
quadratic п¬Ѓeld and let L be a lattice with RL вЉ† L. By multiplying L by a
suitable factor, we may assume that
L = Z + ZП„
with П„ в€€ H. The order R isв€љ п¬Ѓnite index in OK for some imaginary quadratic
of
в€љ
п¬Ѓeld K = Q( в€’d). Since в€’d в€€ OK , there is a nonzero integer n such that
в€љ в€љ
n в€’d в€€ R. Therefore, n в€’dL вЉ† L, so
в€љ в€љ
n в€’d В· П„ = tП„ + u, n в€’d В· 1 = vП„ + w (10.3)

В© 2008 by Taylor & Francis Group, LLC
330 CHAPTER 10 COMPLEX MULTIPLICATION

for some integers t, u, v, w. Dividing the two equations yields
tП„ + u
П„= .
vП„ + w
As in the proof of Theorem 10.2, the two equations in (10.3) yield
в€љ в€љ
(n в€’d)2 в€’ (t + w)(n в€’d) + (tw в€’ uv) = 0.
в€љ
Therefore, n в€’d is a root of X 2 в€’ (t + w)X + (tw в€’ uv) and is also a root of
X 2 + n2 d. в€љ these are not the same polynomial, we can subtract them and
If
п¬Ѓnd that n в€’d is a root of a polynomial of degree at most 1 with integer
coeп¬ѓcients, which is impossible. Therefore the two polynomials are the same,
so
tu
= tw в€’ uv = n2 d.
det
vw
By Lemma 10.10, there exist M в€€ SL2 (Z) and S1 в€€ Sn2 d such that
tu
= M S1 .
vw
Then
tП„ + u
j(П„ ) = j = j(M S1 П„ ) = j(S1 П„ ),
vП„ + w
since j в—¦ M = j. Therefore,

(j(П„ ) в€’ j(SП„ )) = 0,
Hn2 d (j(П„ )) =
Sв€€Sn2 d

since j(П„ ) в€’ j(S1 П„ ) = 0 is one of the factors.
Assume now that d = 1. Since n2 d is not a square, Theorem 10.15 implies
that the highest coeп¬ѓcient of Hn2 d (X) is В±1. Changing the sign of HN if
necessary, we п¬Ѓnd that j(П„ ) is a root of a monic polynomial with integer
coeп¬ѓcients. This means that j(L) = в€љ ) is an algebraic integer.
j(П„
If d = 1, then K = Q(i). Replace в€’d in the above argument with 1 + i.
The argument works with a minor modiп¬Ѓcation; namely, n(1 + i) is a root of
X 2 в€’ 2nX + 2n2 . This yields tw в€’ uv = 2n2 , which is not a square. Therefore,
we can apply Theorem 10.15 to conclude that j(П„ ) is an algebraic integer.
This completes the proof of Theorem 10.9.

10.4 Numerical Examples
Suppose we want to evaluate
в€љ
в€’171
1+
x=j .
2

В© 2008 by Taylor & Francis Group, LLC
331
SECTION 10.4 NUMERICAL EXAMPLES

This is the j-invariant of an elliptic curve that has complex multiplication
в€љ
1+ в€’171
by Z . The others are j(П„2 ), j(П„3 ), j(П„4 ), which are given below,
2
в€љ
along with j 1+ 2в€’19 , which corresponds to an elliptic curve with a larger
endomorphism ring. We can evaluate x numerically using Proposition 9.12.
This yields
в€љ
1 + в€’171
=
j
2
в€’694282057876536664.01228868670830742604436745364124466 . . . .

This number is an algebraic integer by Theorem 10.9. Suppose we want a
polynomial that has x as its root. One way to do this is to п¬Ѓnd the Galois
conjugates of x, namely, the other roots of a polynomial satisп¬Ѓed by x. WeвЂ™ll
show how to proceed for this particular x, then describe the general method.
в€љ
Let П„0 = (1 + в€’171)/2. Then
в€љ в€љ
K = Q(П„0 ) = Q( в€’171) = Q( в€’19).

в€љ
в€љ
Let
в€’171 1 + в€’19
1+
вЉ‚Z = OK .
R=Z
2 2
The endomorphism ring of the lattice R вЉ‚ C is R. As we showed in the
proof of Proposition 10.4, the Galois conjugates of j(R) are j-invariants of
lattices with the same endomorphism ring, namely R. These have the form
j(I), where I is an ideal of R. However, I cannot be an ideal for any order
larger than R since then I has an endomorphism ring larger than R.
If I is an ideal of R, it has the form

I = Оі(ZП„ + Z)

for some Оі в€€ CГ— and some П„ в€€ H. By an appropriate change of basis, we can
assume П„ в€€ F, the fundamental domain for SL2 (Z) acting on the upper half
plane. See Proposition 9.15. As we saw in Equation 10.1, П„ в€€ K. Let

aП„ 2 + bП„ + c = 0,

with a, b, c в€€ Z. We may assume that gcd(a, b, c) = 1 and that a > 0. The
fact that I is an ideal for R but not for any larger order can be shown to
imply that the discriminant is exactly в€’171:

b2 в€’ 4ac = в€’171.
в€љ
(On the other hand, the polynomial X 2 + X + 5 has a root П„ = (1 + в€’19)/2,
which corresponds to the ideal 3OK вЉ‚ R. This is an ideal not only of R, but
also of OK .) The fact that П„ в€€ F means that

В© 2008 by Taylor & Francis Group, LLC
332 CHAPTER 10 COMPLEX MULTIPLICATION

1. в€’a < b в‰¤ a

2. a в‰¤ c,

3. if a = c then b в‰Ґ 0.

The п¬Ѓrst of these expresses the condition that в€’1/2 в‰¤ (П„ ) < 1/2, while the
second says that |П„ | в‰Ґ 1. The case where a = c corresponds to П„ lying on the
unit circle, and b > 0 says that it lies on the left half. It can be shown (see
) that there is a one-to-one correspondence between the ideals I that we
are considering (endomorphism ring exactly R) and those triples satisfying
a > 0, gcd(a, b, c) = 1, b2 в€’ 4ac = в€’171, and conditions (1), (2), and (3).
LetвЂ™s count these triples. The strategy is to consider (b2 + 171)/4 and try to
factor it as ac with a, b, c satisfying (1), (2), and (3):

b (b2 + 171)/4 a c
1 43 1 43
В±3 45 5 9
5 49 7 7

The triple (a, b, c) = (3, 3, 15), which arose in the above calculations, is not
listed since gcd(a, b, c) = 1 (and it corresponds to the ideal 3OK , which is an
ideal for the larger ring OK , as mentioned above). There are no values for
a, c when b = В±7. When |b| в‰Ґ 9, the condition |b| в‰¤ a в‰¤ c can no longer be
satisп¬Ѓed. We have therefore found all triples. They correspond to values of П„ ,
call them П„1 , П„2 , П„3 , П„4 :
в€љ
в€’1 + в€’171
(a, b, c) = (1, 1, 43) в†ђв†’ П„1 =
2
в€љ
в€’3 + в€’171
(a, b, c) = (5, 3, 9) в†ђв†’ П„2 =
10
в€љ
3 + в€’171
(a, b, c) = (5, в€’3, 9) в†ђв†’ П„3 =
10
в€љ
в€’5 + в€’171
(a, b, c) = (7, 5, 7) в†ђв†’ П„4 = .
14

Note that j(П„0 ) = j(П„1 ) since П„0 = П„1 + 1. Compute the values

j(П„2 ) = в€’417.33569403605596400916623167906655644314607149466 . . .
+i3470.100833725097578092463768970644185234184993550 . . .
j(П„3 ) = в€’417.33569403605596400916623167906655644314607149466 . . .
в€’i3470.100833725097578092463768970644185234184993550 . . .
j(П„4 ) = 154.683676758820235444376830811774357548921993728906 . . . .

В© 2008 by Taylor & Francis Group, LLC
333
SECTION 10.4 NUMERICAL EXAMPLES

We can now form the polynomial

(X в€’ j(П„1 ))(X в€’ j(П„2 ))(X в€’ j(П„3 ))(X в€’ j(П„4 ))
= X 4 + 694282057876537344 X 3 + 472103267541360574464 X 2
+8391550371275812148084736 X в€’ 1311901521779155773721411584.

Since we are working with decimals, the numerical coeп¬ѓcients we obtain are
not exact integers. But, since the roots j(П„k ) are a complete set of Galois
conjugate algebraic integers, it follows that the coeп¬ѓcients are true integers.
Therefore, if the computations are done with enough accuracy, we can round
oп¬Ђ to obtain the above polynomial. в€љ
We now describe the general situation. If we start with П„0 = x+yz в€’d ,
then we can use a matrix in SL2 (Z) to move П„0 to П„1 в€€ F, and we have
j(П„0 ) = j(П„1 ). Therefore, letвЂ™s assume П„0 в€€ F. Find integers a, b, c such that
2
aП„0 + bП„0 + c = 0

and a > 0, gcd(a, b, c) = 1. Let b2 в€’4ac = в€’D. Now repeat the procedure used
above, with D in place of 171, and obtain values П„1 , . . . , П„h . The polynomial
satisп¬Ѓed by j(П„0 ) = j(П„1 ) is
r
(X в€’ j(П„k )) в€€ Z[X].
k=1

The above techniques can be used to п¬Ѓnd elliptic curves over п¬Ѓnite п¬Ѓelds
with given orders. For example, suppose we want an elliptic curve E over Fp ,
for some prime p, such that

N = #E(Fp ) = 54323

(N is a prime). Because of HasseвЂ™s theorem, we must have p fairly close to N .
The strategy is to choose a prime p, then let ap = p+1в€’N and в€’D = a2 в€’4p.p
We then п¬Ѓnd the polynomial P (X) whose roots are the j-invariants of elliptic
curves with complex multiplication by the order R of discriminant в€’D. Find
a root of P (X) mod p. Such a root will be the j-invariant of an elliptic curve
E mod p that has complex multiplication by R.
The roots of
X 2 в€’ ap X + p = 0
lie in R (since a2 в€’ 4p = в€’D) and therefore correspond to endomorphisms of
p
E. It can be shown that one of these endomorphisms is the Frobenius map (up
to sign; see below). Therefore, we have found the characteristic polynomial
of the Frobenius map. It follows that

#E(Fp ) = p + 1 в€’ ap = N,

В© 2008 by Taylor & Francis Group, LLC
334 CHAPTER 10 COMPLEX MULTIPLICATION

as desired. There is a slight complication caused by the fact that we might
end up with в€’ap in place of ap . WeвЂ™ll discuss this below.
In order to keep the number of П„k вЂ™s small, we want D, in the above notation,
в€љ
to be small. This means that we should have ap near В±2 p. A choice that
works well for us is

p = 54787, ap = 465, D = 2923.

There are six values П„k , corresponding to the polynomials aX 2 + bX + c with

(a, b, c) = (1, 1, 731), (17, В±1, 43), (11, В±5, 67), (29, 21, 29).

We obtain a polynomial P (X) of degree 6 with integer coeп¬ѓcients, as above.
One of the roots of P (X) mod p is j = 46514. Recall (see Section 2.7) that
3j 2j
y 2 = x3 + x+ (10.4)
1728 в€’ j 1728 в€’ j
is an elliptic curve E1 with j-invariant equal to j. In our case, we obtain

y 2 = x3 + 10784x + 43714 (mod 54787).

The point Q = (1, 36185) lies on E1 . However, we п¬Ѓnd that

54323Q = в€ћ, 55253Q = в€ћ.

Since
55253 = p + 1 + 465,
we discover that we have obtained a curve E1 with ap = в€’465 instead of ap =
465. This curve has complex multiplication by the order R of discriminant
в€’D (note that в€’D = a2 в€’ 4p, so the sign of ap is irrelevant for D), so it is
p
natural for it to appear. To obtain the desired curve, we twist by a quadratic
nonresidue mod p (see Exercise 4.10). A quick computation shows that 2 is
not a square mod p, so we look at the curve E deп¬Ѓned by

y 2 = x3 + 4 В· 10784x + 8 В· 43714 (mod 54787).

This has N points mod p. Just to be sure, we can compute

54323 (3, 38039) = в€ћ.

Since 54323 is prime, we п¬Ѓnd that 54323 divides the number of points in
E(Fp ). But
в€љ
2 В· 54323 > p + 1 + 2 p,
so HasseвЂ™s theorem implies that

#E(Fp ) = 54323.

 стр. 1(всего 2)СОДЕРЖАНИЕ >>