335

SECTION 10.4 NUMERICAL EXAMPLES

The above technique can be used to produce an elliptic curve E and a prime

p such that E(Fp ) is a desired group (when such a curve exists). For example,

suppose we want

E(Fp ) Z2 • Z2 • Z63 .

We take

N = 252, p = 271, ap = 20,

so N = p + 1 ’ ap . We choose

√

’1 + ’171

„= .

2

As we™ll see below, this choice imposes certain congruence conditions on the

Frobenius map that force E(Fp ) to have the desired form. We computed the

polynomial satis¬ed by j(„ ) above. This polynomial has the root 5 mod 271.

Putting this value into the formula (10.4) yields the elliptic curve E given by

y 2 = x3 + 70x + 137 (mod 271).

It has 252 points and has complex multiplication by the order

√

1 + ’171

R=Z

2

of discriminant ’171 = a2 ’ 4p. The characteristic polynomial of the Frobe-

p

nius endomorphism φp is

X 2 ’ 20X + 271,

√

so φp corresponds to a root 10 ± ’171. The choice of sign is irrelevant

for our purposes (it corresponds to how we choose to identify R with the

endomorphism ring), so we assume

√

φp = 10 + ’171.

Therefore, √

’171

1+

≡1

φp = 1 + 2 4 + (mod 2R).

2

It follows that φp acts as the identity on points of order 2, so E(Fp ) has a

subgroup isomorphic to Z2 • Z2 . In fact,

E[2] = {∞, (40, 0), (56, 0), (175, 0)} ‚ E(Fp ).

Since 252 = 4 — 63,

Z2 • Z2 • Z63 .

E(Fp )

√ we instead want the group to be cyclic of order 252, we could use R =

If

Z[ ’171] so that φp would not be congruent to 1 mod 2 or mod 3. We would

© 2008 by Taylor & Francis Group, LLC

336 CHAPTER 10 COMPLEX MULTIPLICATION

then ¬nd a new set of „k corresponding to the discriminant ’4 · 171, a new

j-invariant mod p, and a new√E.

1+ ’19

If we had used R = Z , then we would have obtained an elliptic

2

curve with group isomorphic to Z6 • Z42 , since φp ≡ 1 (mod 6R ) in this

case.

This technique has many uses. For example, in [100], the curve E de¬ned

by

y 2 = x3 + 3x ’ 31846 (mod 158209)

was dedicated to Arjen Lenstra on the occasion of his thesis defense on May

16, 1984. The curve satis¬es

Z5 • Z16 • Z1984 .

E(F158209 )

(If the defense had been one month later, such a dedication would have been

impossible.) Finding elliptic curves with groups that are cyclic of large prime

order is very useful in cryptography (see Chapter 6). Finding elliptic curves of

a given order is also useful in primality proving (see Section 7.2). A detailed

discussion of the problem, with improvements on the method presented here,

is given in [73]. See also [7], [8].

10.5 Kronecker™s Jugendtraum

The Kronecker-Weber theorem says that if K/Q is a ¬nite Galois extension

with abelian Galois group, then

K ⊆ Q(e2πi/n )

for some integer n. This can be viewed as saying that the abelian extensions of

Q are generated by the values of an analytic function, namely e2πiz , at rational

numbers. Kronecker™s Jugendtraum (youthful dream) is that the abelian

extensions of an arbitrary number ¬eld might similarly be generated by special

values of a naturally occurring function. This has been accomplished for

imaginary quadratic ¬elds. Some progress has also been made for certain other

¬elds by Shimura using complex multiplication of abelian varieties (higher

dimensional analogues of elliptic curves).

If E is an elliptic curve given by y 2 = x3 + Ax + B, then its j-invariant is

given by j = 6912A3 /(4A3 + 27B 2 ). Therefore, if E is de¬ned over a ¬eld L,

then the j-invariant of E is contained in L. Conversely, if j = 0, 1728 lies in

some ¬eld L, then the elliptic curve

3j 2j

y 2 = x3 + x+

1728 ’ j 1728 ’ j

© 2008 by Taylor & Francis Group, LLC

337

EXERCISES

is de¬ned over L and has j-invariant equal to j ∈ L. Therefore, for any j there

is an elliptic curve with j-invariant equal to j de¬ned over the ¬eld generated

by j.

THEOREM √ 10.16

Let K = Q( ’D) be an imaginary quadratic ¬eld, let OK be the ring of

algebraic integers in K, and let j = j(OK ), where OK is regarded as a lattice

in C. Let E be an elliptic curve de¬ned over K(j) with j-invariant equal to

j.

1. Assume K = Q(i), Q(e2πi/3 ). Let F be the ¬eld generated over K(j) by

the x-coordinates of the torsion points in E(Q). Then F/K has abelian

Galois group, and every extension of K with abelian Galois group is

contained in F .

2. If K = Q(i), the result of (1) holds when F is the extension generated

by the squares of the x-coordinates of the torsion points.

3. If K = Q(e2πi/3 ), the result of (1) holds when F is the extension gen-

erated by the cubes of the x-coordinates of the torsion points.

For a proof, see, for example, [111, p. 135] or [103]. Note that j(OK )

is algebraic, by Proposition 10.4. The j-invariant determines the lattice for

the elliptic curve up to homothety (Corollary 9.20), so an elliptic curve with

invariant j(OK ) automatically has complex multiplication by OK .

The x-coordinates of the torsion points are of the form

r1 , r2 ∈ Q,

„˜(r1 ω1 + r2 ω2 ),

where „˜ is the Weierstrass „˜-function for the lattice for E. Therefore, the

abelian extensions of K are generated by j(OK ) and special values of the

function „˜. This is very much the analogue of the Kronecker-Weber theorem.

There is much more that can be said on this subject. See, for example,

[111] and [70].

Exercises

√ √

10.1 Let K = Q( d) and K = Q( d ) be quadratic ¬elds. Let β ∈ K

and β ∈ K and assume β, β ∈ Q. Suppose that β + β lies in a

quadratic ¬eld. Show that K = K . (Hint: It su¬ces to consider the

√ √

case β = a d and β = b d . Let ± = β + β . Show that if ± is a root

of a quadratic polynomial with coe¬cients in Q, then we can solve for

√ √ √

d, say, in terms of d and obtain d ∈ K .)

© 2008 by Taylor & Francis Group, LLC

338 CHAPTER 10 COMPLEX MULTIPLICATION

10.2 Let R be an order in an imaginary quadratic ¬eld. Regard R as a subset

of C. Show that if r ∈ R, then its complex conjugate r is also in R.

This means that if L is a lattice with complex multiplication by R, then

there are two ways to embed R into the endomorphisms of L, namely

via the assumed inclusion of R in C and also via the complex conjugate

embedding (that is, if r ∈ R and ∈ L, de¬ne r — = r ). This means

that when we say that R is contained in the endomorphism ring of a

lattice or of an elliptic curve, we should specify which embedding we

are using. For elliptic curves over C, this is not a problem, since we

can implicitly regard R as a subset of C and take the action of R on L

as being the usual multiplication. But for elliptic curves over ¬elds of

positive characteristic, we cannot use this complex embedding.

√

1+ ’43

is a principal ideal domain to show that

10.3 Use the fact that Z 2

√

π 43

e is very close to an integer.

10.4 Let x = a + bi + cj + dk lie in the Hamiltonian quaternions.

(a) Show that

(a + bi + cj + dk)(a ’ bi ’ cj ’ dk) = a2 + b2 + c2 + d2 .

(b) Show that if x = 0, then there exists a quaternion y such that

xy = 1.

(c) Show that if we allow a, b, c, d ∈ Q2 (= the 2-adics), then a2 + b2 +

c2 + d2 = 0 if and only if a = b = c = d = 0. (Hint: Clearing

denominators reduces this to showing that a2 + b2 + c2 + d2 ≡ 0

(mod 8) implies that a, b, c, ≡ 0 (mod 8).)

(d) Show that if x, y are nonzero Hamiltonian quaternions with 2-adic

coe¬cients, then xy = 0.

(e) Let p be an odd prime. Show that the number of squares a2 mod p,

including 0, is (p + 1)/2 and that the number of elements of Fp of

the form 1 ’ b2 (mod p) is also (p + 1)/2.

(f) Show that if p is a prime, then a2 + b2 + 1 ≡ 0 (mod p) has a

solution a, b.

(g) Use Hensel™s lemma (see Appendix A) to show that if p is an odd

prime, then there exist a, b ∈ Qp such that a2 + b2 + 1 = 0. (The

hypotheses of Hensel™s lemma are not satis¬ed when p = 2.)

(h) Let p be an odd prime. Show that there are nonzero Hamiltonian

quaternions x, y with p-adic coe¬cients such that xy = 0.

10.5 Show that a nonzero element in a de¬nite quaternion algebra has a

multiplicative inverse. (Hint: Use the ideas of parts (1) and (2) of

Exercise 10.4.)

© 2008 by Taylor & Francis Group, LLC