. 2
( 2)

© 2008 by Taylor & Francis Group, LLC

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
„= .
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

of discriminant ’171 = a2 ’ 4p. The characteristic polynomial of the Frobe-
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, √
φp = 1 + 2 4 + (mod 2R).
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 =
Z[ ’171] so that φp would not be congruent to 1 mod 2 or mod 3. We would

© 2008 by Taylor & Francis Group, LLC

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
curve with group isomorphic to Z6 • Z42 , since φp ≡ 1 (mod 6R ) in this
This technique has many uses. For example, in [100], the curve E de¬ned
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

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
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].

√ √
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

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


. 2
( 2)