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

[33].

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

imaginary quadratic ¬eld.

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 [16]), 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 [50], [53], [54].

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

[16]) 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.