Algorithmic Number Theory

MSRI Publications
Volume 44, 2008

Computational class field theory

HENRI COHEN AND PETER STEVENHAGEN

A BSTRACT. Class field theory furnishes an intrinsic description of the abelian

extensions of a number field which is in many cases not of an immediate algo-
rithmic nature. We outline the algorithms available for the explicit computation
of such extensions.

C ONTENTS
1. Introduction 497
2. Class field theory 499
3. Local aspects: ideles 503
4. Computing class fields: preparations 508
5. Class fields as Kummer extensions 509
6. Class fields arising from complex multiplication 515
7. Class fields from modular functions 522
8. Class invariants 529
Acknowledgements 532
References 533

1. Introduction
Class field theory is a twentieth century theory describing the set of finite
abelian extensions L of certain base fields K of arithmetic type. It provides a
canonical description of the Galois groups Gal.L=K/ in terms of objects defined
‘inside K’, and gives rise to an explicit determination of the maximal abelian
ab
quotient GK of the absolute Galois group GK of K. In the classical examples,
K is either a global field, that is, a number field or a function field in one variable
over a finite field, or a local field obtained by completing a global field at one
of its primes. In this paper, which takes an algorithmic approach, we restrict to
the fundamental case in which the base field K is a number field. By doing so,
we avoid the complications arising for p-extensions in characteristic p > 0.

497
498 HENRI COHEN AND PETER STEVENHAGEN

ab
Class field theory describes GK for a number field K in a way that can be
seen as a first step towards a complete description of the full group GK  GQ .
At the moment, such a description is still far away, and it is not even clear what
kind of description one might hope to achieve. Grothendieck’s anabelian Galois
theory and his theory of dessins d’enfant [Schneps 1994] constitute one direction
of progress, and the largely conjectural Langlands program [Bump et al. 2003]
provides an other approach. Despite all efforts and partial results [Völklein
1996], a concrete question such as the inverse problem of Galois theory — which
asks whether, for a number field K, all finite groups G occur as the Galois group
of some finite extension L=K — remains unanswered for all K.
A standard method for gaining insight into the structure of GK , and for re-
alizing certain types of Galois groups over K as quotients of GK , consists of
studying the action of GK on ‘arithmetical objects’ related to K, such as the di-
vision points in Q of various algebraic groups defined over K. A good example
is the Galois representation arising from the group EŒm.Q / of m-torsion points
of an elliptic curve E that is defined over K. The action of GK on EŒm.Q /
factors via a finite quotient Tm  GL2 .Z =mZ / of GK , and much is known
[Serre 1989] about the groups Tm . Elliptic curves with complex multiplication
by an order in an imaginary quadratic field K give rise to abelian extensions of
K and yield a particularly explicit instance of class field theory.
For the much simpler example of the multiplicative group Gm , the division
points of Gm .Q / are the roots of unity in Q . The extensions of K they generate
are the cyclotomic extensions of K. Because the Galois group of the extension
K  K.m / obtained by adjoining a primitive m-th root of unity m to K natu-
rally embeds into .Z =mZ / , all cyclotomic extensions are abelian. For K D Q ,
Kronecker discovered in 1853 that all abelian extensions are accounted for in
this way.
T HEOREM 1.1 (K RONECKER –W EBER ). Every finite abelian extension Q  L
is contained in some cyclotomic extension Q  Q .m /.
Over number fields K ¤ Q , there are more abelian extensions than just cyclo-
tomic ones, and the analogue of Theorem 1.1 is what class field theory provides:
every abelian extension K  L is contained in some ray class field extension
K  Hm . Unfortunately, the theory does not provide a ‘natural’ system of
generators for the fields Hm that plays the role of the roots of unity in Theorem
1.1. Finding such a system for all K is one of the Hilbert problems from 1900
that is still open. Notwithstanding this problem, class field theory is in princi-
ple constructive, and, once one finds in some way a possible generator of Hm
over K, it is not difficult to verify that it does generate Hm . The information
we have on Hm is essentially an intrinsic description, in terms of the splitting
and ramification of the primes in the extension K  Hm , of the Galois group
 COMPUTATIONAL CLASS FIELD THEORY 499

Gal.Hm =K/ as a ray class group Clm . This group replaces the group .Z =mZ /
that occurs implicitly in Theorem 1.1 as the underlying Galois group:
.Z =mZ / Ž Gal.Q . /=Q /; .a mod m/ ’ . W  ‘  a /: (1-2)
m a m m

We can in principle find generators for any specific class field by combining our
knowledge of its ramification data with a classical method to generate arbitrary
solvable field extensions, namely, the adjunction of radicals. More formally, we
call an extension L of an arbitrary field K a radical extension if L is contained
in the splitting field over K of a finite collection of polynomials of the form
X n a, with n 2 Z 1 not divisible by char.K/ and a 2 K. If the collection of
polynomials can be chosen so that K contains a primitive n-th root of unity for
each polynomial X n a in the collection, then the radical extension K  L is
said to be a Kummer extension. Galois theory tells us that every Kummer ex-
tension is abelian and, conversely, that an abelian extension K  L of exponent
n is Kummer if K contains a primitive n-th root of unity. Here the exponent of
an abelian extension K  L is the smallest positive integer n that annihilates
Gal.L=K/. Thus, for every finite abelian extension K  L of a number field
K, there exists a cyclotomic extension K  K./ such that the ‘base-changed’
extension K./  L./ is Kummer.
In Section 5, we compute the class fields of K as subfields of Kummer ex-
tensions of K./ for suitable cyclotomic extensions K./ of K. The practical
problem of the method is that the auxiliary fields K./ may be much larger than
the base field K, and this limits its use to not-too-large examples.
If K is imaginary quadratic, elliptic curves with complex multiplication solve
the Hilbert problem for K, and this yields methods that are much faster than the
Kummer extension constructions for general K. We describe these complex
multiplication methods in some detail in our Sections 6 to 8. We do not discuss
their extension to abelian varieties with complex multiplication [Shimura 1998];
nor do we discuss the analytic generation of class fields of totally real number
fields K using Stark units [Cohen 2000, Chapter 6].

2. Class field theory

Class field theory generalizes Theorem 1.1 by focusing on the Galois group
.Z =mZ / of the cyclotomic extension Q  Q .m / rather than on the specific
generator m . The extension Q  Q .m / is unramified at all primes p - m, and
the splitting behavior of such p only depends on the residue class .p mod m/ 2
.Z =mZ / . More precisely, the residue class degree fp D ŒFp .m / W Fp  of the
primes over p - m equals the order of the Frobenius automorphism .p W m ‘
p
m / 2 Gal.Q .m /=Q /, and this is the order of .p mod m/ 2 .Z =mZ / under the
standard identification .1-2/.
500 HENRI COHEN AND PETER STEVENHAGEN

Now let K  L be any abelian extension of number fields. Then for each
prime p of K that is unramified in L, by [Stevenhagen 2008, Section 15] there is
a unique element Frobp 2 Gal.L=K/ that induces the Frobenius automorphism
x ‘ x #kp on the residue class field extensions kp  kq for the primes q in L
extending p. The order of this Frobenius automorphism Frobp of p in Gal.L=K/
equals the residue class degree Œkq W kp , and the subgroup hFrobp i  Gal.L=K/
is the decomposition group of p.
We define the Artin map for L=K as the homomorphism

L=K W IK .
L=K / Ž Gal.L=K/; p ’ Frobp (2-1)

on the group IK .
L=K / of fractional ZK -ideals generated by the primes p of K

that do not divide the discriminant
L=K of the extension K  L. Such primes
p are known to be unramified in L by [Stevenhagen 2008, Theorem 8.5]. For
an ideal a 2 IK .
L=K /, we call L=K .a/ the Artin symbol of a in Gal.L=K/.
For K D Q , we can rephrase Theorem 1.1 as follows.
T HEOREM 2.2 (K RONECKER –W EBER ). If Q  L is an abelian extension,
there exists an integer m 2 Z >0 such that the kernel of the Artin map L=Q
contains all Z -ideals x Z with x > 0 and x  1 mod m.
The equivalence of Theorems 1.1 and 2.2 follows from the analytic fact that an
extension of number fields is trivial if all primes outside a density zero subset
split completely in it. Thus, if all primes p  1 mod m split completely in
Q  L, then all primes of degree one are split in Q .m /  L.m / and L is
contained in the cyclotomic field Q .m /.
The positivity condition on x in Theorem 2.2 can be omitted if the primes p 
1 mod m also split completely in L, that is, if L is totally real and contained
in the maximal real subfield Q .m Cm1 / of Q .m /. The allowed values of m in
Theorem 2.2 are the multiples of some minimal positive integer, the conductor
of Q  L. It is the smallest integer m for which Q .m / contains L. The prime
divisors of the conductor are exactly the primes that ramify in L, and p 2 divides
the conductor if and only if p is wildly ramified in L.
For a quadratic field L of discriminant d,

the conductor equals jdj, and Theo-
d
rem 2.2 says that the Legendre symbol x only depends on x modulo jdj. This
is Euler’s version of the quadratic reciprocity law. The main statement of class
field theory is the analogue of Theorem 2.2 over arbitrary number fields K.
T HEOREM 2.3 (A RTIN ’ S RECIPROCITY LAW ). If K  L is an abelian exten-
sion, there exists a nonzero ideal m0  ZK such that the kernel of the Artin map
L=K in .2-1/ contains all principal ZK -ideals x ZK with x totally positive and
x  1 mod m0 .
 COMPUTATIONAL CLASS FIELD THEORY 501

This innocuous-looking statement is highly nontrivial. It shows there is a pow-

erful global connection relating the splitting behavior in L of different primes of
K. Just as Theorem 2.2 implies the quadratic reciprocity law, Artin’s reciprocity
law implies the general power reciprocity laws from algebraic number theory;
see [Artin and Tate 1990, Chapter 12, ~ 4; Cassels and Fröhlich 1967, p. 353].
It is customary to treat the positivity conditions at the real primes of K and
the congruence modulo m0 in Theorem 2.3 on equal footing. To this end, one
formally defines a modulus m of K to be a nonzero ZK -ideal m0 times a subset
m1 of the real primes of K. For a modulus m D m0 m1 , we write

x  1 mod m

if x satisfies ordp .x 1/  ordp .m0 / at the primes p dividing the finite part m0
and if x is positive at the real primes in the infinite part m1 of m.
In the language of moduli, Theorem 2.3 asserts that there exists a modulus
m such that the kernel ker L=K of the Artin map contains the ray group Rm
of principal ZK -ideals x ZK generated by elements x  1 mod m. As in the
case of Theorem 2.2, the set of these admissible moduli for K  L consists
of the multiples m of some minimal modulus fL=K , the conductor of K  L.
The primes occurring in fL=K are the primes of K, both finite and infinite, that
ramify in L. An infinite prime of K is said to ramify in L if it is real but has
complex extensions to L. As for K D Q , a finite prime p occurs with higher
multiplicity in the conductor if and only if it is wildly ramified in L.
If m D m0 m1 is an admissible modulus for K  L and Im denotes the group
of fractional ZK -ideals generated by the primes p coprime to m0 , then the Artin
map induces a homomorphism

L=K W Clm D Im =Rm Ž Gal.L=K/; Œp ’ Frobp (2-4)

on the ray class group Clm D Im =Rm modulo m. Our earlier remark on the
triviality of extensions in which almost all primes split completely implies that
it is surjective. By the Chebotarev density theorem [Stevenhagen and Lenstra
1996], even more is true: the Frobenius automorphisms Frobp for p 2 Im are
equidistributed over the Galois group Gal.L=K/. In particular, a modulus m is
admissible for an abelian extension K  L if and only if (almost) all primes
p 2 Rm of K split completely in L.
Since the order of the Frobenius automorphism Frobp 2 Gal.L=K/ equals the
residue class degree fp of the primes q in L lying over p, the norm NL=K .q/ D
pfp of every prime ideal q in ZL coprime to m is contained in the kernel of the
Artin map. A nontrivial index calculation shows that the norms of the ZL -ideals
coprime to m actually generate the kernel in .2-4/. In other words, the ideal
group Am  Im that corresponds to L, in the sense that we have ker L=K D
502 HENRI COHEN AND PETER STEVENHAGEN

Am =Rm , is equal to
Am D NL=K .ImZL /
Rm : (2-5)
The existence theorem from class field theory states that for every modulus m
of K, there exists an extension K  L D Hm for which the map L=K in .2-4/
is an isomorphism. Inside some fixed algebraic closure K of K, the extension
Hm is uniquely determined as the maximal abelian extension L of K in which
all primes in the ray group Rm split completely. It is the ray class field Hm
modulo m mentioned in the introduction, for which the analogue of Theorem
1.1 holds over K. If K  L is abelian, we have L  Hm whenever m is an
admissible modulus for L. For L D Hm , we have Am D Rm in .2-5/ and an
Artin isomorphism Clm Ž  Gal.H =K/.
m

E XAMPLE 2.6.1. It will not come as a surprise that for K D Q , the ray class field
modulo .m/
1 is the cyclotomic field Q .m /, and the ray class group Cl.m/
1
is the familiar group .Z =mZ / acting on the m-th roots of unity. Leaving out
the real prime 1 of Q , we find the ray class field modulo .m/ to be the maximal
real subfield Q .m C m1 / of Q .m /. This is the maximal subfield in which the
real prime 1 is unramified.
E XAMPLE 2.6.2. The ray class field of conductor m D .1/ is the Hilbert class
field H D H1 of K. It is the largest abelian extension of K that is unramified at
all primes of K, both finite and infinite. Since I1 and R1 are the groups of all
fractional and all principal fractional ZK -ideals, respectively, the Galois group
Gal.H =K/ is isomorphic to the ordinary class group ClK of K, and the primes
of K that split completely in H are precisely the principal prime ideals of K.
This peculiar fact makes it possible to derive information about the class group
of K from the existence of unramified extensions of K, and conversely.
The ray group Rm is contained in the subgroup Pm  Im of principal ideals
in Im , and the quotient Im =Pm is the class group ClK of K for all m. Thus, the
ray class group Clm D Im =Rm is an extension of ClK by a finite abelian group
Pm =Rm that generalizes the groups .Z =mZ / from .1-2/. More precisely, we
have a natural exact sequence

ZK Ž .ZK =m/ Ž Clm Ž ClK Ž 0 (2-7)
in which the residue class of x 2 ZK coprime to m0 in the finite group
.ZK =m/ D .ZK =m0 /  pjm1 h 1i
Q

consists of its ordinary residue class modulo m0 and the signs of its images
under the real primes pjm1 . This group naturally maps onto Pm =Rm  Clm ,
with a kernel reflecting the fact that generators of principal ZK -ideals are only
unique up to multiplication by units in ZK .
 COMPUTATIONAL CLASS FIELD THEORY 503

Interpreting both class groups in .2-7/ as Galois groups, we see that all ray
class fields contain the Hilbert class field H D H1 from Example 2.6.2, and that
we have an Artin isomorphism
.ZK =m/ =imŒZK
  Gal.H =H /
Ž (2-8)
m

for their Galois groups over H . By Example 2.6.1, this is a generalization of

the isomorphism .1-2/.
In class field theoretic terms, we may specify an abelian extension K  L by
giving an admissible modulus m for the extension together with the correspond-
ing ideal group
Am D kerŒIm ! Gal.L=K/ (2-9)
arising as the kernel of the Artin map .2-4/. In this way, we obtain a canonical
bijection between abelian extensions of K inside K and ideal groups Rm 
Am  Im of K, provided that one allows for the fact that the ‘same’ ideal group
Am can be defined modulo different multiples m of its conductor, that is, the
conductor of the corresponding extension. More precisely, we call the ideal
groups Am1 and Am2 equivalent if they satisfy Am1 \ Im D Am2 \ Im for some
common multiple m of m1 and m2 .
Both from a theoretical and an algorithmic point of view, .2-5/ provides an
immediate description of the ideal group corresponding to L as the norm group
Am D NL=K .Im ZL /
Rm as soon as we are able to find an admissible modulus
m for L. In the reverse direction, finding the class field L corresponding to an
ideal group Am is much harder. Exhibiting practical algorithms to do so is the
principal task of computational class field theory, and the topic of this paper.
Already in the case of the Hilbert class field H of K from Example 2.6.2, we
know no ‘canonical’ generator of H , and the problem is nontrivial.

3. Local aspects: ideles

Over K D Q , all abelian Galois groups are described as quotients of the
groups .Z =mZ / for some modulus m 2 Z 1 . One may avoid the ubiquitous
choice of moduli that arises when dealing with abelian fields by combining the
Artin isomorphisms .1-2/ at all ‘finite levels’ m into a single profinite Artin
isomorphism
lim.Z =mZ / D Z b Ž Gal.Q =Q /
ab (3-1)
m

between the unit group Z
b of the profinite completion Z
b of Z and the absolute

abelian Galois group of Q . The group Z splits as a product p Zp by the
b
Q
Chinese remainder theorem, and Q ab is obtained correspondingly as a com-
positum of the fields Q .p1 / generated by the p-power roots of unity. The
504 HENRI COHEN AND PETER STEVENHAGEN


automorphism corresponding to u D .up /p 2 Z b acts as  ‘  up on p-power
b maps to the inertia group
roots of unity. Note that the component group Zp  Z
at p in any finite quotient Gal.L=Q / of Gal.Q ab =Q /.
For arbitrary number fields K, one can take the projective limit in .2-7/ over
all moduli and describe Gal.Kab =K/ by an exact sequence
 b  K
p real h 1i Ž Gal.Kab =K/ Ž ClK Ž 1;
Q
1 Ž ZK ŽZ K (3-2)
b D 
which
Q treats somewhat asymmetrically the finite primes occurring in Z K
p finite U p and the infinite primes. Here K maps the element 1 at a real
prime p to the complex conjugation at the extensions of p. The image of K is
the Galois group Gal.Kab =H / over the Hilbert class field H , which is of finite
index hK D # ClK in Gal.Kab =K/. For an abelian extension L of K containing
H , the image of the component group Up  Z b in Gal.L=H / is again the inertia
K
group at p in Gal.L=K/. As H is totally unramified over K, the same is true if
L does not contain H : the inertia groups for p in Gal.LH =K/ and Gal.L=K/
are isomorphic under the restriction map.
A more elegant description of Gal.Kab =K/ than that provided by the se-
quence .3-2/ is obtained if one treats all primes of K in a uniform way and
redefines the Artin map K — as we will do in .3-7/ — using the idele group

D 0p Kp D f.xp /p W xp 2 Up for almost all pg
Q
AK

of K. This group [Stevenhagen 2008, Section 14], consists of those elements in

the Cartesian product of the multiplicative groups Kp at all completions Kp of
K that have their p-component in the local unit group Up for almost all p. Here
Up is, as before, the unit group of the valuation ring at p if p is a finite prime of K;
for infinite primes p, the choice of Up is irrelevant as there
Q are only finitely many
such p. We take Up D Kp , and write U1 to denote p infinite Kp D K ˝Q R .
Note that we have p finite Up D Z b .
Q
K

The topology on AK is the restricted product topology: elements are close
if they are p-adically close at finitely many p and have a quotient in Up for

all other p. With this topology, K  embeds diagonally into AK as a discrete

subgroup. As the notation suggests, AK is the unit group of the adele ring
AK D 0p Kp , the subring of p Kp consisting of elements having integral
Q Q
components for almost all p.
To any idele x D .xp /p , we can associate an ideal x ZK D p finite pordp .xp / ,
Q

and this makes the group IK of fractional ZK -ideals into a quotient of AK .
 
For a global element x 2 K  AK , the ideal x ZK is the principal ZK -ideal
generated by x, and so we have an exact sequence
 
b  U1 Ž A =K  Ž ClK Ž 1
1 Ž ZK ŽZK K (3-3)
 COMPUTATIONAL CLASS FIELD THEORY 505

that describes the idele class group AK 

=K  of K in a way reminiscent of .3-2/.
To obtain Gal.Kab =K/ as a quotient of AK 
=K  , we show that the ray class
groups Clm defined in the previous section are natural quotients of AK 
=K  . To

modulus m D m0 m1 of K an open subgroup Wm  AK
do so, we associate to a Q ,
as follows. Write m D p p n.p/ as a formal product, with n.p/ D ordp .m0 / for
finite p, and n.p/ 2 f0; 1g to indicate the infinite p in m1 . Now put
Q .n.p//
Wm D p U p
.k/
for subgroups Up  Kp that are defined by

U
8
< p
ˆ if k D 0;
.k/
Up D 1 C p k if p is finite and k > 0;
ˆ
: C  if p is real and k D 1.
Up  Up D R

Here we write UpC for real p to denote the subgroup of positive elements in Up .
Because C  and R >0 have no proper open subgroups, one sees from the defini-
 
tion of the restricted product topology on AK that a subgroup H  AK is open
if and only if it contains Wm for some modulus m.
L EMMA 3.4. For every modulus m D p pn.p/ of K, there is an isomorphism
Q


AK =K  Wm Ž  Cl
m

that maps .xp /p to the class of p finite pordp .yxp / . Here y 2 K  is a global
Q
n.p/
element satisfying yxp 2 Up for all pjm.
P ROOF. Note first that the global element y required in the definition exists by
the approximation theorem. The precise choice of y is irrelevant, since for any
two elements y and y 0 satisfying the requirement, we have y=y 0  1 mod m.

We obtain a homomorphism AK ! Clm that is surjective since it maps a prime
element p at a finite prime p - m to the class of p. Its kernel consists of the
ideles that can be multiplied into Wm by a global element y 2 K  . 
If m is an admissible modulus for the finite abelian extension K  L, we can
compose the isomorphism in Lemma 3.4 with the Artin map .2-4/ for K  L
to obtain an idelic Artin map

b
L=K W AK =K  Ž Gal.L=K/ (3-5)
that no longer refers to the choice of a modulus m. This map, which exists
as a corollary of Theorem 2.3, is a continuous surjection that maps the class
of a prime element p 2 Kp  AK 
to the Frobenius automorphism Frobp 2
Gal.L=K/ whenever p is finite and unramified in K  L.
506 HENRI COHEN AND PETER STEVENHAGEN

For a finite extension L of K, the adele ring AL is obtained from AK by a


base change K  L, so we have a norm map NL=K W AL ! AK that maps AL
  
to AK and restricts to the field norm on L  AL . Since it induces the ideal
norm IL ! IK on the quotient IL of AK 
, one deduces that the kernel of .3-5/
equals .K
NL=K ŒAL / mod K , and that we have isomorphisms
  


AK =K  NL=K ŒAL
  Gal.L=K/;
 Š Im =Am Ž (3-6)

with Am the ideal group modulo m that corresponds to L in the sense of .2-9/.
Taking the limit in .3-5/ over all finite abelian extensions K  L inside K, one
obtains the idelic Artin map

K W AK =K  Ž GK
ab
D Gal.Kab =K/: (3-7)

This is a continuous surjection that is uniquely determined by the property that

the K -image of the class of a prime element p 2 Kp  AK 
maps to the
Frobenius automorphism Frobp 2 Gal.L=K/ for every finite abelian extension
K  L in which p is unramified. It exhibits all abelian Galois groups over K as
a quotient of the idele class group AK 
=K  of K.
The kernel of the Artin map .3-7/ is the connected component of the unit
element in AK 
=K  . In the idelic formulation, the finite abelian extensions of
K inside K correspond bijectively to the open subgroups of AK 
=K  under the
map
1
L’ K ŒGal.Kab =L/ D .K 
NL=K ŒAL

/ mod K  :

In this formulation, computational class field theory amounts to generating, for

any given open subgroup of AK 
=K  , the abelian extension K  L correspond-
ing to it.
E XAMPLE 3.8. Before continuing, let us see what the idelic reformulation of
.3-1/ comes down to for K D Q . Every idele x D ..xp /p ; x1 / 2 AQ can
uniquely be written as the product of the rational number

sign.x1 / p ordp .xp / 2 Q 

Q
p

b  R >0 . In this way, the Artin map

and a ‘unit idele’ ux 2 p Zp  R >0 D Z
Q
.3-7/ becomes a continuous surjection

Q W AQ =Q  Š Z
b  R >0 Ž Gal.Q ab =Q /:

Its kernel is the connected component f1g R >0 of the unit element in AQ =Q  .
Comparison with .3-1/ leads to a commutative diagram of isomorphisms
 COMPUTATIONAL CLASS FIELD THEORY 507

b
Z
1 /Z
b

can  .3-1/  (3-8)

 
 / Gal.Q ab =Q /
AQ =.Q 
R >0 /

in which the upper horizontal map is not the identity. To see this, note that the
class of the prime element ` 2 Q `  AQ in AQ =.Q 
R >0 / is represented by the
idele x D .xp /p 2 Zb having components xp D ` 1 for p ¤ ` and x` D 1. This
idele maps to the Frobenius of `, which raises roots of unity of order coprime
to ` to their `-th power. Since x is in all Wm for all conductors m D `k , it fixes
`-power roots of unity. Thus, the upper isomorphism 1 is inversion on Z b.

Even though the idelic and the ideal group quotients on the left hand side of the
arrow in .3-6/ are the ‘same’ finite group, it is the idelic quotient that neatly
encodes information at the ramifying primes pjm, which seem ‘absent’ in the
other group. More precisely, we have for all primes p an injective map Kp !
AK
=K  that can be composed with .3-7/ to obtain a local Artin map Kp W
Kp ! Gal.L=K/ at every prime p of K. If p is finite and unramified in K  L,
we have Up  ker Kp and an induced isomorphism of finite cyclic groups
f  hFrob i D Gal.L =K /;
Kp =hp p iUp D Kp =NLq =Kp ŒLq  Ž p q p

since Frobp generates the decomposition group of p in Gal.L=K/, which may

be identified with the Galois group of the local extension Kp  Lq at a prime
qjp in L. It is a nontrivial fact that .3-5/ induces for all primes p of K, including
the ramifying and the infinite primes, a local Artin isomorphism
 Gal.L =K /:
W Kp =NLq =Kp ŒLq  Ž (3-10)
Lq =Kp q p

In view of our observation after .3-2/, it maps Up =NLq =Kp ŒUq  for finite p iso-
morphically onto the inertia group of p.
We can use .3-10/ to locally compute the exponent n.p/ to which p occurs
in the conductor of K  L: it is the smallest nonnegative integer k for which
.k/
we have Up  NLq =Kp ŒLq . For unramified primes p we obtain n.p/ D 0, as
the local norm is then surjective on the unit groups. For tamely ramified primes
we have n.p/ D 1, and for wildly ramified primes p, the exponent n.p/ may
be found by a local computation. In many cases it is sufficient to use an upper
bound coming from the fact that every d-th power in Kp is a norm from Lq ,
with d the degree of Kp  Lq (or even K  L). Using Hensel’s Lemma [Buhler
and Wagon 2008], one then finds
1
 
n.p/  e.p=p/ C ordp .ep / C 1; (3-11)
p 1
508 HENRI COHEN AND PETER STEVENHAGEN

where e.p=p/ is the absolute ramification index of p over the underlying ratio-
nal prime p and ep is the ramification index of p in K  L. Note that ep is
independent of the choice of an extension prime as K  L is Galois.

4. Computing class fields: preparations

Our fundamental problem is the computation of the class field L that cor-
responds to a given ideal group Am of K in the sense of .2-5/. One may
‘give’ Am by specifying m and a list of ideals for which the classes in the ray
class group Clm generate Am . The first step in computing L is the computa-
tion of the group Im =Am that will give us control of the Artin isomorphism
Im =Am Ž  Gal.L=K/. Because linear algebra over Z provides us with good
algorithms [Cohen 2000, Section 4.1] to deal with finite or even finitely gener-
ated abelian groups, this step essentially reduces to computing the finite group
Clm of which Im =Am is quotient.
For the computation of the ray class group Clm modulo m D m0
m1 , one
computes, in line with [Schoof 2008], the three other groups in the exact se-
quence .2-7/ in which it occurs, and the maps between them. The class group

ClK and the unit group ZK in .2-7/ can be computed using the algorithm de-
scribed in [Stevenhagen 2008, Section 12], which factors smooth elements of
ZK over a factor base. As this takes exponential time as a function of the base
field K, it can only be done for moderately sized K. For the group .ZK =m0 / ,
one uses the Chinese remainder theorem to decompose it into a product of local
multiplicative groups the form .ZK =pk / . Here we need to assume that we are
able to factor m0 , but this is a safe assumption as we are unlikely to deal with
extensions for which we cannot even factor the conductor. The group .ZK =pk /
is a product of the cyclic group kp D .ZK =p/ and the subgroup .1Cp/=.1Cpk /,
the structure of which can be found inductively using the standard isomorphisms
.1 C pa /=.1 C paC1 / Š kp and, more efficiently,
 pa =p2a
.1 C pa /=.1 C p2a / Ž
between multiplicative and additive quotients. In many cases, the result can be
obtained in one stroke using the p-adic logarithm [Cohen 2000, Section 4.2.2].
Finding Clm from the other groups in .2-7/ is now a standard application of
linear algebra over Z . The quotient Im =Am gives us an explicit description of
the Galois group Gal.L=K/ in terms of Artin symbols of ZK -ideals.
For the ideal group Am , we next compute its conductor f, which may be a
proper divisor of m. This comes down to checking whether we have Am 
Im \ Rn for some modulus njm. Even in the case Am D Rm , the conductor
 .Z =3Z / of ray
can be smaller than m, as the trivial isomorphism .Z =6Z / Ž
class groups over K D Q shows. The conductor f obtained, which is the same as
 COMPUTATIONAL CLASS FIELD THEORY 509

the conductor fL=K of the corresponding extension, is exactly divisible by the

primes that ramify in K  L. In particular, we know the signature of L from
the real primes dividing f. With some extra effort, one can even compute the
discriminant
L=K using Hasse’s Führerdiskriminantenproduktformel
Y

L=K D f./0 : (4-1)
WIm =Am !C 

Here  ranges over the characters of the finite group Im =Am Š Gal.L=K/,
and f./0 denotes the finite part of the conductor f./ of the ideal group A
modulo m satisfying A =Am D ker . All these quantities can be computed by
the standard algorithms for finite abelian groups.

E XAMPLE 4.2. If K  L is cyclic of prime degree `, we have a trivial character

of conductor .1/ and ` 1 characters of conductor fL=K , so .4-1/ reduces to

L=K D .fL=K /`0 1

:

In particular, we see that the discriminant of a quadratic extension K  L is not

only for K D Q , but generally equal to the finite part of the conductor of the
extension.
Having at our disposal the Galois group Gal.L=K/, the discriminant
L=K , and
the Artin isomorphism Im =Am Ž  Gal.L=K/ describing the splitting behavior
of the primes in K  L, we proceed with the computation of a generator for
L over K, that is, an irreducible polynomial in KŒX  with the property that its
roots in K generate L.
Because the computation of class fields is notQan easy computation, it is often
desirable to decompose Gal.L=K/ as a product i Gal.Li =K/ of Galois groups
Gal.Li =K/ and to realize L as a compositum of extensions Li that are computed
separately. This way one can work with extensions L=K that are cyclic of prime
power order, or at least of prime power exponent. The necessary reduction of
the global class field theoretic data for L=K to those for each of the Li is only
a short computation involving finite abelian groups.

5. Class fields as Kummer extensions

Let K be any field containing a primitive n-th root of unity n , and let K  L
be an abelian extension of exponent dividing n. In this situation, Kummer theory
[Lang 2002, Chapter VIII, ~ 6–8] tells us that L can be obtained by adjoining to
K the n-th roots of certain elements of K. More precisely, let WL D K  \ L n
be the subgroup of K  of elements that have an n-th root in L. Then we have
510 HENRI COHEN AND PETER STEVENHAGEN
p
L D K. n WL /, and there is the canonical Kummer pairing
n
Gal.L=K/  WL =K  Ž hn i p
1=n  1 . n w/ (5-1)
.; w/ ’ h; wi D .w / D p :
n
w
By canonical, we mean that the natural action of an automorphism  2 Aut.K/
on the pairing for K  L yields the Kummer pairing for K  L, that is,
h 1
; wi D h; wi : (5-2)
The Kummer pairing is perfect, that is, it induces an isomorphism
n 
W =K  Ž
L Hom.Gal.L=K/; C  /: (5-3)
p
In the case where Gal.L=K/ is cyclic of order n, this means that L D K. n
˛/
n n
and WL D K \ L D h˛i
K for some ˛ 2 K. If ˇ also generates L
  
p
n

over K, then ˛ and ˇ are powers of each other modulo n-th powers.
We will apply Kummer theory to generate the class fields of a number field K.
Thus, let L be the class field of K from Section 4 that is to be computed. Suppose
that we have computed a ‘small’ modulus f for L that is only divisible by the
ramifying primes, such as the conductor fL=K , and an ideal group Af for L by
the methods of Section 4. With this information, we control the Galois group
of our extension via the Artin isomorphism If =Af Ž  Gal.L=K/. Let n be
the exponent of Gal.L=K/. Then we can directly apply Kummer theory if K
contains the required n-th roots of unity; if not, we need to pass to a cyclotomic
extension of K first. This leads to a natural case distinction.
Case 1: K contains a primitive n-th root of unity n . Under the restrictive
p n , the class field L is a Kummer extension of K,
assumption that K contains
and generating L D K. n WL / comes down to finding generators for WL =K  n .
We first compute a finite group containing WL =K  n . This reduction is a familiar
ingredient from the proofs of class field theory [Artin and Tate 1990; Cassels
and Fröhlich 1967].
L EMMA 5.4. Let K  L be finite abelian of exponent n, and assume n 2 K.
Suppose S is a finite set of primes of K containing the infinite primes such that
(1) K  L is unramified outside S ;
n
(2) ClK =ClK is generated by the classes of the finite primes in S .
Then the image of the group US of S -units in K  =K  n is finite of order n#S ,
and it contains the group WL =K  n from .5-1/.
The first condition in Lemma 5.4 means that S contains all the primes that divide
our small modulus f. The second condition is automatic if the class number of K
is prime to n, and it is implied by the first if the classes of the ramifying primes
 COMPUTATIONAL CLASS FIELD THEORY 511

n n
generate ClK =ClK . Any set of elements of ClK generating ClK =ClK actually
generates the full ‘n-part’ of the class group, that is, the product of the p-Sylow
subgroups of ClK at the primes pjn. In general, there is a lot of freedom in the
choice of primes in S outside f. One tries to have S ‘small’ in order to minimize
the size n#S of the group .US
K  n /=K  n containing WL =K  n .
P ROOF OF L EMMA 5.4. By the Dirichlet unit theorem [Stevenhagen 2008,
Theorem 10.9], the group US of S-units of K is isomorphic to K  Z #S 1 .
As K contains n , the image .US
K  n /=K  n Š US =USn of US in K  =K  n
is finite of order n#S .
To show that .US
K  n /=K  n contains WL =K  n , pick any ˛ 2 WL . Since
p
K  K. n ˛/ is unramified outside S, we have .˛/ D aS bn for some product
aS of prime ideals in S and b coprime to all finite primes in S . As the primes
in S generate the n-part of ClK , we can write b D bS c with bS a product of
prime ideals in S and c an ideal of which the class in ClK is of order u coprime
to n. Now ˛ u generates an ideal of the form .˛ u / D a0S . n / with a0S a product
of prime ideals in S and 2 K  . It follows that ˛ u n 2 K  is an S -unit, and
so ˛ u and therefore ˛ is contained in US
K  n . 

p we see that K  L is a subextension of the Kum-

In the situation of Lemma 5.4,
mer extension K  N D K. n US / of degree n#S . We have to find the subgroup
of US =USn corresponding to L. This amounts to a computation in linear algebra
using the Artin map and the Kummer pairing. For ease of exposition, we assume
that the set S we choose to satisfy Lemma 5.4 contains all primes dividing n.
This implies that N is the maximal abelian extension of exponent n of K that
is unramified outside S.
As we compute L as a subfield of the abelian extension K  N , we replace
the modulus f of K  L by some multiple m that is an admissible modulus for
K  N . Clearly m only needs to be divisible by the ramified primes in K  N ,
which are all in S. Wild ramification only occurs at primes p dividing n, and
for these primes we can take ordp .m/ equal to the bound given by .3-11/. The
ideal group modulo m corresponding to N is Imn
Pm because N is the maximal
exponent-n extension of K of conductor m; hence the Artin map for K  N is
 Gal.N=K/:
Im Ž Im =.Imn
Pm / D Clm =Clnm Ž (5-5)

The induced map Im ! Gal.L=K/ is the Artin map for K  L, which has
the ideal group Am corresponding to L as its kernel. Let ˙L  Im be a finite
set of ideals of which the classes generate the Z =nZ -module Am =.Imn
Pm / Š
Gal.N=L/. We then have to determine the subgroup VL  US consisting of
p
those S-units v 2 US that have the property that n v is left invariant by thepArtin
symbols of all ideals in ˙L , since the class field we are after is L D K. n VL /.
512 HENRI COHEN AND PETER STEVENHAGEN

We are here in a situation to apply linear algebra over Z =nZ , because the
Kummer pairing .5-1/ tells us that the action of the Artin symbols N=K .a/ of
the ideals a 2 Im on the n-th roots of the S-units is described by the pairing of
Z =nZ -modules given by

Im =Imn  US =USn Ž hn i

(5-6)
N=K .a/
.a; u/ ’ h N=K .a/; ui D .u1=n / 1
:

Making this computationally explicit amounts to computing the pairing for some
choice of basis elements of the three modules involved.
For hn i we have the obvious Z =nZ -generator n , and Im =Imn is a free Z =nZ -
module generated by the primes p 62 S . If K is of moderate degree, the gen-
eral algorithm [Stevenhagen 2008, Section 12] for computing units and class
groups can be used to compute generators for US , which then form a Z =nZ -
basis for US =USn . In fact, finding s 1 D #S 1 independent units in US
that generate a subgroup of index coprime to n is enough: together with a
root of unity generating K , these will generate US =USn . This is somewhat
easier than finding actual generators for US , because maximality modulo n-th
powers is not difficult to establish for a subgroup U  US having the right rank
s D #S. Indeed, each reduction modulo a small prime p 62 S provides a character
U  US ! kp =.kp /n Š hn i, the n-th power residue symbol at p. By finding
s independent characters, one shows that the intersection of their kernels equals
U n D U \ USn .
For a prime p 62 S and u 2 US , the definitions of the Kummer pairing and the
Frobenius automorphism yield

hFrobp ; ui D .u1=n /Frobp 1

 u.N p 1/=n
2 kp ;

where N p D # kp is the absolute norm of p. Thus hFrobp ; ui is simply the power

of n that is congruent to u.N p 1/=n 2 kp . Even when p is large, this is not
an expensive discrete logarithm problem in kp , since in practice the exponent
n  ŒL W K is small: one can simply check all powers of  n 2 kp . Since hn i
reduces injectively modulo primes p - n, the n-root of unity hFrobp ; ui can be
recovered from its value in kp .
From the values hFrobp ; ui, we compute all symbols h N=K .a/; ui by lin-
earity. It is now a standard computation in linear algebra to find generators for
the subgroup VL =USn  US =USn that is annihilated by the ideals a 2 ˙L under
the pairing
p .5-6/. This yields explicit generators for the Kummer extension
L D K. VL /, and concludes the computation of L in the case where K contains
n

n , with n the exponent of Gal.L=K/.

 COMPUTATIONAL CLASS FIELD THEORY 513

Case 2: K does not contain n . In this case L is not a Kummer extension of K,

but L0 D L.n / is a Kummer extension of K 0 D K.n /.

L0 D L.n /
PPP
ss PPP
L NNN PPP
NNN PP
NNN K 0 D K.n /
NN pp (5-7)
L \ K0

K
To find generators of L0 over K 0 by the method of Case 1, we need to ‘lift’ the
class field theoretic data from K to K 0 to describe L0 as a class field of K 0 .
Lifting the modulus f D f0 f1 for K  L is easy: as K 0 is totally complex,
f0 D f0 ZK 0 is admissible for K 0  L0 . From the definition of the Frobenius
automorphism, it is immediate that we have a commutative diagram

IK 0 ;f0
Artin / Gal.L0 =K 0 /

NK 0 =K res
 
IK ;f
Artin / Gal.L=K/

As the restriction map on the Galois groups is injective, we see that the inverse
norm image NK 01=K Af  IK 0 ;f0 is the ideal group of K 0 corresponding to the
extension K 0  L0 . Because NK 01=K Af contains PK 0 ;f0 , computing this inverse
image takes place inside the finite group ClK 0 ;f0 , a ray class group for K 0 .
We perform the algorithm from Case 1 for the extension K 0  L0 to find
generators of L0 over K 0 . We are then working with (ray) class groups and S-
units in K 0 rather than in K, and S has to satisfy Lemma 5.4 condition (2) for
ClK 0 . All this is only feasible if K 0 is of moderate degree, and this seriously
restricts the values of n one can handle in practice. Our earlier observation
that we may decompose If =Af Š Gal.L=K/ into a product of cyclic groups
of prime power order and generate L accordingly as a compositum of cyclic
extensions of K is particularly relevant in this context, as it reduces our problem
to a number of instances where K  L is cyclic of prime power degree. Current
implementations [Fieker 2001] deal with prime power values up to 20.
We further assume for simplicity that we are indeed in the case where K  L
is cyclic of prime power degree n, with K 0 D K.n / ¤ K. Suppose that, using
the algorithm from Case 1, we have computed a Kummer generator  2 L0 for
which we have L0 D K 0 . / D K.n ; / and  n D ˛ 2 K 0 . We then need to
‘descend’  efficiently to a generator  of L over K. If n is prime, one has
514 HENRI COHEN AND PETER STEVENHAGEN

L D K./ for the trace

 D TrL0 =L ./: (5-8)
For prime powers this does not work in all cases. One can however replace 
by  C kn for some small integer k 2 Z to ensure that  generates L0 over
K, and then general field theory tells us that the coefficients of the irreducible
polynomial
fL D
Y
.X .// 2 LŒX  (5-9)
 2Gal.L0 =L/

of  over L generate L over K. As we took K  L to be cyclic of prime power

degree, one of the coefficients is actually a generator, and in practice the trace
works. In all cases, one needs an explicit description of the action of the Galois
group Gal.L0 =L/ on  and n in order to compute the trace .5-8/, and possibly
other coefficients of fL in .5-9/. Finally, if we have L D K./, we need the
action of Gal.L=K/ on  in order to write down the generating polynomial

Y
fK D .X .// 2 KŒX 
2Gal.L=K /

for K  L that we are after.

As before, the Artin map gives us complete control over the action of the
abelian Galois group Gal.L0 =K/ on L0 D K.n ; /, provided that we describe
the elements of Gal.L0 =K/ as Artin symbols. We let m be an admissible mod-
ulus for K  L0 ; the least common multiple of fL=K and n
p real p is an
Q
obvious choice for m. All we need to know is the explicit action of the Frobenius
automorphism Frobp 2 Gal.L0 =K/ of a prime p - m of K on the generators n
and  of L0 over K. Note that p does not divide n, and that we may assume that
˛ D  n is a unit at p.
Np
The cyclotomic action of Frobp 2 Gal.L0 =K/ is given by Frobp .n / D n ,
with N p D #kp the absolute norm of p. This provides us with the Galois action
on K 0 and yields canonical isomorphisms
Gal.K 0 =K/ Š imŒNK =Q W Im Ž .Z =nZ / ;
Gal.K 0 =.L \ K 0 // Š imŒNK =Q W Am Ž .Z =nZ / :
p
In order to understand the action of Frobp on  D n ˛, we first observe that
K  L0 D K 0 . / can only be abelian if ˛ is in the cyclotomic eigenspace of
.K 0 / modulo n-th powers under the action of Gal.K 0 =K/. More precisely,
applying .5-2/ for K 0  L0 with  D Frobp , we have Frobp

Frobp 1 D  since
Gal.L0 =K/ is abelian, and therefore

h; Frobp .˛/i D h; ˛iFrobp D h; ˛iN p D h; ˛ N p i

 COMPUTATIONAL CLASS FIELD THEORY 515

for all  2 Gal.L0 =K 0 /. By .5-3/, we conclude that

Frobp .˛/ D ˛ N p
pn (5-10)
for some element p 2 K 0 . Knowing how Frobp acts on ˛ 2 K 0 D K.n /, we can
compute p by extracting some n-th root of Frobp .˛/˛ N p in K 0 . The element
p is only determined up to multiplication by n-th roots of unity by .5-10/.
Because we took ˛ to be a unit at p, we have pn  1 mod p by definition of
the Frobenius automorphism, and so there is a unique element p  1 mod p
satisfying .5-10/. With this choice of p , we have

Frobp ./ D  N p
p
because the n-th powers of both quantities are the same by .5-10/, and they are
congruent modulo p. This provides us with the explicit Galois action of Frobp
on  for unramified primes p.
The description of the Galois action on  and n in terms of Frobenius sym-
bols is all we need. The Galois group Gal.L0 =L/ Š Gal.K 0 =.L \ K 0 //, which
we may identify with the subgroup NK =Q .Am / of .Z =nZ / , is either cyclic or,
if n is a power of 2, generated by 2 elements. Picking one or two primes p
in Am with norms in suitable residue classes modulo n is all it takes to gener-
ate Gal.L0 =L/ by Frobenius automorphisms, and we can use these elements to
descend  to a generator  for L over K. We also control the Galois action of
Gal.L=K/ D Im =Am on , and this makes it possible to compute the irreducible

polynomial fK for the generator  of L over K.

6. Class fields arising from complex multiplication

As we observed in Example 2.6.1, the ray class fields over the rational number
field Q are the cyclotomic fields. For these fields, we have explicit generators
over Q that arise ‘naturally’ as the values of the analytic function q W x ‘ e 2 ix
on the unique archimedean completion R of Q . The function q is periodic
modulo the ring of integers Z  R of Q , and it induces an isomorphism
 T D fz 2 C W zz D 1g  C
R =Z Ž
(6-1)
x ’ q.x/ D e 2 ix
between the quotient group R =Z and the ‘circle group’ T of complex numbers
of absolute value 1. The Kronecker–Weber theorem 1.1 states that the values
of the analytic function q at the points of the torsion subgroup Q =Z  R =Z
generate the maximal abelian extension Q ab of Q . More precisely, the q-values
1
at the m-torsion subgroup m Z =Z of R =Z generate the m-th cyclotomic field
Q .m /. Under this parametrization of roots of unity by Q =Z , the Galois action
516 HENRI COHEN AND PETER STEVENHAGEN

1
on the m-torsion values comes from multiplications on m Z =Z by integers a 2 Z
coprime to m, giving rise to the Galois group
1
Gal.Q .m /=Q / D Aut. m Z =Z / D .Z =mZ / (6-2)

from .1-2/. Taking the projective limit over all m, one obtains the identifica-
b from .3-1/, and we saw in Example
tion of Gal.Q ab =Q / with Aut.Q =Z / D Z
3.8 that the relation with the Artin isomorphism is given by the commutative
diagram .3-8/. To stress the analogy with the complex multiplication case, we
rewrite .3-8/ as
b
Z
1 /Z
b D A =.Q 
R >0 /
Q

can  Artin  (6-3)

 
 / Gal.Q ab =Q /
Aut.Q =Z /

where 1 denotes inversion on Z b .
From now on, we take K to be an imaginary quadratic field. Then K has a sin-
gle archimedean completion K ! C , and much of what we said for the analytic
function q on R =Z has an analogue for the quotient group C =ZK . In complete
analogy, we will define an analytic function fK W C =ZK ! P1 .C / in .6-14/
1
with the property that its finite values at the m-torsion subgroup m ZK =ZK of
C =ZK generate the ray class field Hm of K of conductor mZK . However, to
define this elliptic function fK on the complex elliptic curve C =ZK , we need
an algebraic description of C =ZK , which exists over an extension of K that is
usually larger than K itself. The Hilbert class field H D H1 of K from Example
2.6.2 is the smallest extension of K that one can use, and the torsion values of
fK generate class fields over H . This makes the construction of H itself into an
important preliminary step that does not occur over Q , as Q is its own Hilbert
class field.
In this section, we give the classical algorithms for constructing the extensions
K  H and H  Hm . The next section provides some theoretical background
and different views on complex multiplication. Our final Section 8 shows how
such views lead to algorithmic improvements.
Complex multiplication starts with the fundamental observation [Silverman
1986, Chapter VI] that for every lattice   C , the complex torus C = admits
a meromorphic function, the Weierstrass }-function

} W z ‘ z 2 C !2nf0g Œ.z !/ 2 ! 2 ;
P

that has period lattice  and is holomorphic except for double poles at the points
of . The corresponding Weierstrass map
 COMPUTATIONAL CLASS FIELD THEORY 517

W W C = Ž E  P2 .C /; 0
z ’ Œ} .z/ W } .z/ W 1
is a complex analytic isomorphism between the torus C = and the complex
elliptic curve E  P2 .C / defined by the affine Weierstrass equation
y 2 D 4x 3 g2 ./x g3 ./:
The Weierstrass coefficients
g2 ./ D 60 ! 4 g3 ./ D 140 ! 6
P P
and (6-4)
!2nf0g !2nf0g

of E are the Eisenstein series of weight 4 and 6 for the lattice . The natural
addition on C = translates into an algebraic group structure on E .C / some-
times referred to as ‘chord and tangent addition’. On the Weierstrass model E ,
the point O D Œ0 W 1 W 0 D W .0 mod / at infinity is the zero point, and any line
in P2 .C / intersects the curve E in 3 points, counting multiplicities, that have
sum O.
All complex analytic maps C =1 ! C =2 fixing the zero point are multi-
plications z ‘ z with  2 C satisfying 1  2 . These are clearly group
homomorphisms, and in the commutative diagram
 / C =2
C =1

W1  W1  (6-5)
  
E1 / E
2

the corresponding maps  W E1 Ž E2 between algebraic curves are known
as isogenies. For  ¤ 0, the isogeny  is a finite algebraic map of degree
Œ2 W 1 , and E1 and E2 are isomorphic as complex algebraic curves if
and only if we have 1 D 2 for some  2 C . The isogenies E ! E form
the endomorphism ring
End.E / D f 2 C W   g (6-6)
of the curve E , which we can view as a discrete subring of C . The -value
of the analytically defined endomorphism ‘multiplication by  2 C ’ is reflected
algebraically as a true multiplication by  of the invariant differential dx=y on
E coming from dz D d.} /=} 0
. If End.E / is strictly larger than Z , it is a
complex quadratic order O and E is said to have complex multiplication (CM)
by O.
To generate the class fields of our imaginary quadratic field K, we employ an
elliptic curve E having CM by ZK . Such a curve can be obtained by taking 
equal to ZK or to a fractional ZK -ideal a, but the Weierstrass coefficients .6-4/
for  D a will not in general be algebraic.
518 HENRI COHEN AND PETER STEVENHAGEN

In order to find an algebraic model for the complex curve E , we scale 

to a homothetic lattice  to obtain a C -isomorphic model
E W y 2 D 4x 3  4
g2 ./x  6
g3 ./
under the Weierstrass map. The discriminant
D g23 27g32 of the Weierstrass
polynomial 4x 3 g2 x g3 does not vanish, and the lattice function

./ D g2 ./3 27g3 ./2
is of weight 12: it satisfies
./ D  12
./. Thus, the j -invariant
g2 ./3 g2 ./3
j ./ D 1728 D 1728 (6-7)

./ g2 ./3 27g3 ./2
is of weight zero and is an invariant of the homothety class of  or, equiva-
lently, the isomorphism class of the complex elliptic curve C =. It generates
the minimal field of definition over which C = admits a Weierstrass model.
If E has CM by ZK , then  is homothetic to some ZK -ideal a. It follows
that, up to isomorphism, there are only finitely many complex elliptic curves E
having CM by ZK , one for each ideal class in ClK . Because any automorphism
of C maps the algebraic curve E to an elliptic curve with the same endomor-
phism ring, we find that the j -invariants of the ideal classes of ZK form a set of
hK D # ClK distinct algebraic numbers permuted by the absolute Galois group
GQ of Q . This allows us to define the Hilbert class polynomial of K as
Y
HilK .X / D .X j .a// 2 Q ŒX : (6-8)
Œa2ClK

Its importance stems from the following theorem, traditionally referred to as the
first main theorem of complex multiplication.
T HEOREM 6.9. The Hilbert class field H of K is the splitting field of the
polynomial HilK .X / over K. This polynomial is irreducible in KŒX , and the
Galois action of the Artin symbol c D H =K .c/ of the ideal class Œc 2 ClK Š
Gal.H =K/ on the roots j .a/ of HilK .X / is given by j .a/c D j .ac 1 /.
To compute HilK .X / from its definition .6-8/, one compiles a list of ZK -ideal
classes in the style of Gauss, who did this in terms of binary quadratic forms.
Every ZK -ideal class Œa has a representative of the form Z  C Z , with  2 K
a root of some irreducible polynomial aX 2 C bX C c 2 Z ŒX  of discriminant
b 2 4ac D
K =Q . If we take for  the root in the complex upper half plane H,
the orbit of  under the natural action
˛ˇ ˛z C ˇ
 
.z/ D
ı z Cı
 COMPUTATIONAL CLASS FIELD THEORY 519

of the modular group SL2 .Z / on H is uniquely determined by Œa 2 ClK . In this

orbit, there is a unique element
p
b C b 2 4ac
a D 2H
2a
that lies in the standard fundamental domain for the action of SL2 .Z / on H
consisting of those z 2 H that satisfy the two inequalities jRe.z/j  21 and zz  1
and, in case we have equality in either of them, also Re.z/  0. This yields a
description
p
b C b 2 4ac
h i
Œa D Z
CZ “ .a; b; c/
2a
of the elements of ClK as reduced integer triples .a; b; c/ whose discriminant
is b 2 4ac D
K =Q . As we have Re.a / D b=2a and a  a D c=a, the re-
duced integer triples .a; b; c/ corresponding to a in the fundamental domain for
SL2 .Z / are those satisfying

jbj  a  c and b2 4ac D
K =Q ;

where b is nonnegative if jbj D a or a D c. For reduced forms, one sees from the
inequality
K =Q D b 2 4ac  a2 4a2 D 3a2 that we have bounds jbj  a 
p
j
K =Q j=3, so the list is indeed finite and can easily be generated [Cohen 1993,
Algorithm 5.3.5]. See [Cox 1989] for the classical interpretation of the triples
.a; b; c/ as positive definite integral binary quadratic forms aX 2 C bX Y C cY 2
of discriminant b 2 4ac D
K =Q .
If we put j . / D j .Z  C Z /, the j -function .6-7/ becomes a holomorphic
function j W H ! C invariant under the action of SL2 .Z /. As it is in particular
invariant under  ‘  C 1, it can be expressed in various ways in terms of the
variable q D e 2 i from .6-1/. Among them is the well-known integral Fourier
expansion
1 1
j . / D j .q/ D q C 744 C 196884q C : : : 2 q C Z ŒŒq (6-10)

that explains the normalizing factor 1728 in the definition .6-7/ of j . It implies
[Lang 1987, Chapter 5, ~ 2] that the roots of HilK .X / in .6-8/ are algebraic
integers, and so HilK .X / is a polynomial in Z ŒX  that can be computed exactly
from complex approximations of its roots that are sufficiently accurate to yield
the right hand side of .6-8/ in C ŒX  to ‘one-digit precision’. For numerical
computations of j . /, one uses approximate values of the Dedekind -function
Y X
. / D q 1=24 .1 q n / D q 1=24 . 1/n q n.3n 1/=2 ; (6-11)
n1 n2Z
520 HENRI COHEN AND PETER STEVENHAGEN

which has a lacunary Fourier expansion that is better suitedpfor numerical pur-
poses than .6-10/. From -values one computes f2 ./ D 2.2/=./ and
finally j . / as

2 ./ C 16/
.f24 3
j ./ D : (6-12)
2 ./
f24
This finishes the description of the classical algorithm to compute the Hilbert
class field H of K.
Having computed the irreducible polynomial HilK .X / of jK D j .ZK /, we
can write down a Weierstrass model EK for C =ZK over H D K.jK / (or even
over Q .jK /) and use it to generate the ray class field extensions H  Hm .
Choosing EK is easy in the special cases K D Q .3 /; Q .i /, when one of g2 D
g2 .ZK / and g3 D g3 .ZK / vanishes and the other can be scaled p to have any
nonzero rational value. For K ¤ Q .3 /; Q .i /, the number  D g3 =g2 2 C 
is determined up to sign, and since we have

4 6 jK
cK D  g2 D  g3 D g23 g3 2 D 27 ;
jK 1728

the model y 2 D 4x 3 cK x cK for C =ZK is defined over Q .jK /  H . A

more classical choice is 2 D
=.g2 g3 /, with g2 , g3 and
associated to ZK ,
giving rise to the model
cK cK
EK W y 2 D wK .x/ D 4x 3 x : (6-13)
.cK 27/2 .cK 27/3

Any scaled Weierstrass parametrization WK W C =ZK Ž E with E defined

K K
over H can serve as the imaginary quadratic analogue of the isomorphism q W
 T in .6-1/. For the model E in .6-13/, the x-coordinate }
R =Z Ž K ZK .z/ D
 }ZK .z/ of WK .z/ is given by the Weber function
2

g2 .ZK /g3 .ZK /

fK .z/ D }ZK .z/: (6-14)

.ZK /

It has ‘weight 0’ in the sense that the right side is invariant under simultaneous
scaling .ZK ; z/ ! .ZK ; z/ by  2 C  of the lattice ZK and the argument z.

In the special cases K D Q .i / and Q .3 / that have ZK of order 4 and 6,
there are slightly different Weber functions fK that are not the x-coordinates
on a Weierstrass model for C =ZK over H , but an appropriately scaled square
and cube of such x-coordinates, respectively. In all cases, the analogue of the
Kronecker–Weber theorem for K is the following second main theorem of com-
plex multiplication.
 COMPUTATIONAL CLASS FIELD THEORY 521

T HEOREM 6.15. The ray class field Hm of conductor mZK of K is generated

over the Hilbert class field H of K by the values of the Weber function fK at
the nonzero m-torsion points of C =ZK .
In the non-special cases, the values of fK at the m-torsion points of C =ZK are
the x-coordinates of the nonzero m-torsion points of the elliptic curve EK in .6-
13/. For K D Q .i/ and Q .3 /, one uses squares and cubes of these coordinates.
In all cases, generating Hm over H essentially amounts to computing division
polynomials Tm 2 C ŒX  that have these x-coordinates as their roots. We will
define these polynomials as elements of H Œx, because the recursion formulas
at the end of this section show that their coefficients are elements of the ring
generated over Z by the coefficients of the Weierstrass model of EK .
If m is odd, the nonzero m-torsion points come in pairs fP; P g with the
same x-coordinate xP D x P , and we can define a polynomial Tm .x/ 2 H Œx
of degree .m2 1/=2 up to sign by
Y
Tm .x/2 D m2 .x xP /:
P 2EK Œm.C /;
P ¤O

For even m, we adapt the definition by excluding the 2-torsion points satisfying
P D P from the product, and define Tm .X / 2 H Œx of degree .m2 4/=2 by
Y
Tm .x/2 D .m=2/2 .x xP /:
P 2EK Œm.C /;
2P ¤O

The ‘missing’ x-coordinates of the nonzero 2-torsion points are the zeros of the
cubic polynomial wK 2 H Œx in .6-13/. This is a square in the function field of
the elliptic curve .6-13/, and in many ways the natural object to consider is the
‘division polynomial’

Tm .x/
(
if m is odd;
m .x; y/ D
2yTm .x/ if m is even.

This is an element of the function field C .x; y/ living in the quadratic extension
H Œx; y of the polynomial ring H Œx defined by y 2 D wK .x/. It is uniquely
defined up to the sign choice we have for Tm . Most modern texts take the sign
of the highest coefficient of Tm equal to 1. Weber [1908, p. 197] takes it equal
to . 1/m 1 , which amounts to a sign change y ‘ y in mP .x; y/.
By construction, the function m has divisor .1 m /ŒOC P ¤O; mP DO ŒP .
2

The normalizing highest coefficients m and m=2 in Tm lead to neat recursive

522 HENRI COHEN AND PETER STEVENHAGEN

formulas
3 3
2mC1 D mC2 m mC1 m 1;
1 2 2
2m D .2y/ m . mC2 m 1 mC1 m 2/

for m that are valid for m > 1 and m > 2. These can be used to compute m
and Tm recursively, using ‘repeated doubling’ of m. One needs the initial values
T1 D T2 D 1 and

T3 D 3X 4 C 6aX 2 C 12bX a2 ;
T4 D 2X 6 C 10aX 4 C 40bX 3 10a2 X 2 8abX 16b 2 2a3 ;

where we have written the Weierstrass polynomial in .6-13/ as wK D 4.x 3 C

ax C b/ to indicate the relation with the nowadays more common affine model
y 2 D x 3 C ax C b to which EK is isomorphic under .x; y/ ‘ .x; y=2/.

7. Class fields from modular functions

The algorithms in the previous section are based on the main Theorems 6.9
and 6.15 of complex multiplication, which can be found already in Weber’s
textbook [1908] and predate the class field theory for general number fields.
The oldest proofs of 6.9 and 6.15 are of an analytic nature, and derive arithmetic
information from congruence properties of Fourier expansions such as .6-10/.
Assuming general class field theory, one can shorten these proofs as it suffices,
just as after Theorem 2.2, to show that, up to sets of primes of zero density, the
‘right’ primes split completely in the purported class fields. In particular, it is
always possible to restrict attention to the primes of K of residue degree one in
such arguments. Deuring [1958] provides analytic proofs of both kinds in his
survey monograph.
Later proofs [Lang 1987, Part 2] of Deuring and Shimura combine class field
theory with the reduction of the endomorphisms in .6-6/ modulo primes, which
yields endomorphisms of elliptic curves over finite fields. These proofs are
firmly rooted in the algebraic theory of elliptic curves [Silverman 1986; Silver-
man 1994]. Here one takes for E in .6-6/ an elliptic curve E that has CM
by ZK and is given by a Weierstrass equation over the splitting field H 0 over
K of the Hilbert class polynomial HilK .X / in .6-8/. In this case the Weier-
strass equation can be considered modulo any prime q of H 0 , and for almost
all primes, known as the primes of good reduction, this yields an elliptic curve
Eq D E mod q over the finite field kq D ZH 0 =q. For such q, the choice of an
extension of q to Q yields a reduction homomorphism EK .Q / ! Eq .k q / on
points that is injective on torsion points of order coprime to q. The endomor-
phisms of E are given by rational functions with coefficients in H 0 , and for
 COMPUTATIONAL CLASS FIELD THEORY 523

primes q of H 0 of good reduction there is a natural reduction homomorphism

End.E/ ! End.Eq /
that is injective and preserves degrees. The ‘complex multiplication’ by an ele-
ment ˛ 2 End.E/ D ZK multiplies the invariant differential dx=y on E by ˛,
so it becomes inseparable in End.Eq / if and only if q divides ˛. The first main
theorem of complex multiplication (Theorem 6.9), which states that H 0 equals
the Hilbert class field H of K and provides the Galois action on the roots of
HilK .X /, can now be derived as follows.
P ROOF OF T HEOREM 6.9. Let p be a prime of degree one of K that is coprime
to the discriminant of HilK .X /, and let ˛ 2 ZK be an element of order 1 at p,
say ˛p 1 D b with .b; p/ D 1. Let a be a fractional ZK -ideal. Then the complex
multiplication ˛ W C =a ! C =a factors in terms of complex tori as
can
C =a Ž C =ap 1 Ž  C =ab Ž can
C =a:
˛

If E and E 0 denote Weierstrass models over H 0 for C =a and C =ap 1 , we obtain

isogenies E ! E 0 ! E of degree p D N p and N b with composition ˛. If
we assume that E and E 0 have good reduction above p, we can reduce the
isogeny E ! E 0 at some prime qjp to obtain an isogeny Eq ! Eq0 of degree p.
This isogeny is inseparable as ˛ lies in q, and therefore equal to the Frobe-
p p 
nius morphism Eq ! Eq. / followed by an isomorphism Eq. / Ž Eq0 . The
.p /
result is an equality j .Eq / D j .Eq0 / of j -invariants that amounts to j .a/p D
j .ap 1 / mod q, and this implies the Frobenius automorphism q 2 Gal.H 0 =K/
acts as j .a/q D j .ap 1 /, independent of the choice of the extension prime qjp.
Because the j -function is an invariant for the homothety class of a lattice, we
have j .a/ D j .ap 1 / if and only if p is principal. It follows that up to finitely
many exceptions, the primes p of degree one splitting completely in K  H 0
are the principal primes, so H 0 equals the Hilbert class field H of K, and the
splitting primes in K  H are exactly the principal primes. Moreover, we have
j .a/c D j .ac 1 / for the action of the Artin symbol c , and HilK is irreducible
over K as its roots are transitively permuted by Gal.H =K/ D ClK . 
In a similar way, one can understand the content of the second main theorem
of complex multiplication. If EK is a Weierstrass model for C =ZK defined
over the Hilbert class field H of K, then the torsion points in EK .C / have
algebraic coordinates. As the group law is given by algebraic formulas over H ,
the absolute Galois group GH of H acts by group automorphisms on
tor
EK .C / Š K=ZK :
Moreover, the action of GH commutes with the complex multiplication action
of End.EK / Š ZK , which is given by isogenies defined over H . It follows that
524 HENRI COHEN AND PETER STEVENHAGEN

GH acts by ZK -module automorphisms on EK tor

.C /. For the cyclic ZK -module
1
EK Œm.C / Š m ZK =ZK of m-torsion points, the resulting Galois representation
1
GH Ž AutZK . m ZK =ZK / Š .ZK =mZK /
of GH is therefore abelian. It shows that, just as in the cyclotomic case .6-2/,
the Galois action over H on the m-division field of EK , which is the extension
of H generated by the m-torsion points of EK , comes from multiplications on
1
m ZK =ZK by integers ˛ 2 ZK coprime to m. The content of Theorem 6.15 is
that, in line with .2-8/, we obtain the m-th ray class field of K from this m-

division field by taking invariants under the action of ZK D Aut.EK /. In the

‘generic case’ where ZK D f˙1g has order 2, adjoining m-torsion points ‘up to
inversion’ amounts to the equality
Hm D H fxP W P 2 EK Œm.C /; P ¤ Og


(7-1)
occurring in Theorem 6.15, since the x-coordinate xP determines P up to multi-

plication by ˙1. More generally, a root of unity  2 ZK acts as an automorphism
of EK by xŒP D  xP , and so in the special cases where K equals Q .i / or
2

Q .3 / and ZK has order 2k with k D 2; 3, one replaces xP by xPk in .7-1/. The
classical Weber functions replacing .6-14/ for K D Q .i/ and K D Q .3 / are
fK .z/ D .g22 .ZK /=
.ZK //}Z2K .z/ and fK .z/ D .g3 .ZK /=
.ZK //}Z3K .z/.

P ROOF OF T HEOREM 6.15. As in the case of Theorem 6.9, we show that the
primes of degree one of K that split completely in the extension K  Hm 0 defined

by adjoining to H the m-torsion points of EK ‘up to automorphisms’ are, up

to a zero density subset of primes, the primes in the ray group Rm . Primes p
of K splitting in Hm 0 are principal as they split in H . For each Z -generator
K

 of p, which is uniquely determined up to multiplication by ZK , one obtains
a complex multiplication by  2 ZK Š End.EK / that fixes EK Œm.C / ‘up to
automorphisms’ if and only if p 2 Rm .
Let p D  ZK be a prime of degree 1 over p for which EK has good reduction
modulo p. Then the isogeny  W EK ! EK , which corresponds to multiplica-
tion by  as in .6-5/, reduces modulo a prime qjp of the m-division field of EK
to an endomorphism of degree p. Since  is in q, this reduction is inseparable,
and so it equals the Frobenius endomorphism of EK ;q up to an automorphism.
One shows [Lang 1987, p. 125] that this local automorphism of EK ;q is induced
by a global automorphism of EK , that is, a complex multiplication by a unit in

ZK , and concludes that  induces a Frobenius automorphism above p on Hm 0 .

As the reduction modulo q induces an isomorphism EK Œm Ž  E Œm on the

K ;q
m-torsion points, this Frobenius automorphism is trivial if and only if we have
  1 mod mZK for a suitable choice of . Thus, p splits completely in Hm 0
0
if and only if p is in Rm , and Hm is the ray class field Hm . 
 COMPUTATIONAL CLASS FIELD THEORY 525

The argument just given shows that we have a concrete realization of the Artin
isomorphism .ZK =mZK / =imŒZK 
Ž Gal.H =H / from .2-8/ by complex
m
multiplications. Passing to the projective limit, this yields the analogue
b =Z  Ž
Z  Gal.K =H /  G ab
ab
K K K

of .3-1/. For the analogue of .6-3/, we note first that for imaginary quadratic
K, the subgroup U1 in .3-3/, which equals C  , maps isomorphically to the
connected component of the unit element in AK 
=K  . Because it is the kernel
of the Artin map K in .3-7/, we obtain a commutative diagram
b
Z
1 / Z  =Z  
 AK =.K 
C  /
K K K

can   Artin  (7-2)

  
AutZK .K=ZK / / Gal.Kab =H /  Gal.Kab =K/
in which the inversion map 1 arises just as in .3-8/. A slight difference with the
diagram .6-3/ for Q is that the horizontal arrows now have a small finite kernel

coming from the unit group ZK . Moreover, we have only accounted for the
automorphisms of Kab over H , not over K. Automorphisms of Hm that are not
the identity on H arise as Artin maps c of nonprincipal ideals c coprime to m,
and the proof of Theorem 6.9 shows that for the isogeny c in the commutative
diagram
C =Z K
can / C =c 1

W  W0  (7-3)
 c

EK / E0 ;
K
we have to compute the restriction c W EK Œm ! EK 0
Œm to m-torsion points.
To do so in an efficient way, we view the j -values and x-coordinates of torsion
points involved as weight zero functions on complex lattices such as ZK or c.
As we may scale all lattices as we did for .6-10/ to Z  C Z with  2 H, such
functions are modular functions H ! C as defined in [Lang 1987, Chapter 6].
The j -function itself is the primordial modular function: a holomorphic
function on H that is invariant under the full modular group SL2 .Z /. Every
meromorphic function on H that is invariant under SL2 .Z / and, when viewed
as a function of q D e 2 i , meromorphic in q D 0, is in fact a rational function
of j . The Weber function fK in .6-14/ is a function
g2 ./g3 ./
f .z/ D }Œ;1 .z/

./
that depends on the lattice ZK D Z  C Z D Œ; 1, and fixing some choice of a
generator  of ZK over Z , we can label its m-torsion values used in generating
526 HENRI COHEN AND PETER STEVENHAGEN

Hm as
1 2 2
Fu . / D f .u1  C u2 / with u D .u1 ; u2 / 2 m Z =Z n f.0; 0/g: (7-4)
For m > 1, the functions Fu W H ! C in .7-4/ are known as the Fricke functions
of level m. These are holomorphic functions on H that are x-coordinates of m-
torsion points on a ‘generic elliptic curve’ over Q .j / with j -invariant j . As they
are zeroes of division polynomials in Q .j /ŒX , they are algebraic over Q .j / and
generate a finite algebraic extension of Q .j /, the m-th modular function field
Fm D Q .j ; fFu gu2. 1 Z =Z /2 nf.0;0/g /: (7-5)
m

Note above that F1 D Q .j /. We may now rephrase the main theorems of

complex multiplication in the following way.
T HEOREM 7.6. Let K be an imaginary quadratic field with ring of integers
Z Œ . Then the m-th ray class field extension K  Hm is generated by the finite
values f . / of the functions f 2 Fm .
For generic K this is directly clear from Theorems 6.9 and 6.15. In the special
cases K D Q .i /; Q .3 /, the functions Fu ./ in .7-4/ vanish at the generator
 of ZK , so an extra argument [Lang 1987, p. 128] involving modified Weber
functions in Fm is needed.
It is not really necessary to take  in Theorem 7.6 to be a generator of ZK ; it
suffices that the elliptic curve C =Œ; 1 is an elliptic curve having CM by ZK .
In computations, it is essential to have the explicit action of Gal.Kab =K/ on
the values f . / from Theorem 7.6 for arbitrary functions f in the modular func-
tion field F D [m1 Fm : As class field theory gives us the group Gal.Kab =K/
in .7-2/ as an explicit quotient of the idele class group AK 
=K  under the Artin
map .3-7/, this means that we need to find the natural action of x 2 AK 
on the
values f . / in Theorem 7.6. We will do so by reinterpreting the action of the
Artin symbol x 2 Gal.Kab =K/ on the function value of f at  as the value of
some other modular function f g .x/ at  , that is,
.f .//x D f g .x/ ./; (7-7)
for some natural homomorphism g W AK 
! Aut.F/ induced by  .
To understand the automorphisms of F, we note first that the natural left
action of SL2 .Z / on H gives rise to a right action on Fm that is easily made
explicit for the Fricke functions .7-4/, using the ‘weight 0’ property of fK . For
M D ˛ ˇı 2 SL2 .Z / we have

 g ./g ./
˛ Cˇ

2 3
Fu .M  / D Fu D }Œ;1 .u1 .˛ C ˇ/ C u2 .  C ı//
 Cı
./
D FuM ./:
 COMPUTATIONAL CLASS FIELD THEORY 527

1 2
As u D .u1 ; u2 / is in m Z =Z 2 , we only need to know M modulo m, so the
Fricke functions of level m are invariant under the congruence subgroup
.m/ D kerŒSL2 .Z / ! SL2 .Z =mZ /
of SL2 .Z /, and they are permuted by SL2 .Z /. As we have F u1 ; u2 D Fu1 ;u2 ,
we obtain a natural right action of SL2 .Z =mZ /=f˙1g on Fm .
Besides this ‘geometric action’, there is a cyclotomic action of .Z =mZ / on
the functions f 2 Fm via their Fourier expansions, which lie in Q .m /..q 1=m //
since they involve rational expansions in

e 2 i.a1  Ca2 /=m D m

a2 a1 =m
q for a1 ; a2 2 Z .

On the Fricke function Fu D F.u1 ;u2 / , the automorphism k W m ‘ m k clearly in-

duces k W F.u1 ;u2 / ‘ F.u1 ;ku2 / . Thus, the two actions may be combined to give
an action of GL2 .Z =mZ /=f˙1g on Fm , with SL2 .Z =m
Z /=f˙1g acting geo-
metrically and .Z =mZ / acting as the subgroup f˙ 01 k0 W k 2 .Z =mZ / g=f˙1g.
The invariant functions are SL2 .Z /-invariant with rational q-expansion; so they
lie in Q .j /, and we have a natural isomorphism
GL2 .Z =mZ /=f˙1g Ž  Gal.F =Q .j //; (7-8)
m

or, if we take the union F D m Fm on the left hand side and the corresponding
S
projective limit on the right hand side,
GL2 .Z  Gal.F=Q .j //:
b/=f˙1g Ž (7-9)
Note that Fm contains Q .m /.j / as the invariant field of SL2 .Z =mZ /=f˙1g,
and that the action of GL2 .Zb/=f˙1g on the subextension Q .j /  Q ab .j / with
 b.
group Gal.Q ab =Q / Š Z is via the determinant map det W GL2 .Z
b b/=f˙1g ! Z
To discover the explicit form of the homomorphism g in .7-7/, let p D  ZK
be a principal prime of K. Then the Artin symbol p is the identity on H , and
the proof of Theorem 6.15 shows that its action on the x-coordinates of the
m-torsion points of EK for m not divisible by  can be written as
Fu ./p D Fu ./ D FuM ./;
where M is the matrix in GL2 .Z =mZ / that represents the multiplication by
1
 on m ZK =ZK with respect to the basis f; 1g. In explicit coordinates, this
means that if  2 H is a zero of the polynomial X 2 C BX C C of discriminant
B 2 4C D
K and  D x1  C x2 is the representation of  on the Z -basis
Œ; 1 of ZK , then we have
 
Bx1 C x2 C x1
M D 2 GL2 .Z =mZ /: (7-10)
x1 x2
528 HENRI COHEN AND PETER STEVENHAGEN

As the Fricke functions of level m generate Fm , we obtain in view of .7-8/ the

identity
f . /p D f M ./ for f 2 Fm and  - m,
which is indeed of the form .7-7/. We can rewrite this in the style of the dia-
gram .7-2/ by observing that the Artin symbol of  2 Kp  AK 
acts as p on
torsion points of order m coprime to p, and trivially on -power torsion points.
Moreover, . mod K  / 2 AK =K  is in the class of the idele x 2 Z b having
K
component 1 at p and  1 elsewhere. Thus, if we define
b Ž GL2 .Z
g W Z b/
K
(7-11)
x ’ Mx 1
by sending x D x1  C x2 2 Z bK to the inverse of the matrix Mx describing mul-
tiplication by x on ZK with respect to the basis Œ; 1, then Mx is given explicitly
b
as in .7-10/, and formula .7-7/ holds for f 2 F and x 2 Z b if we use the natural
K
action of GL2 .Zb/ on F from .7-9/.
To obtain complex multiplication by arbitrary ideles, we note that on the one
hand, the idele class quotient AK
=.K 
C  / from .7-2/, which is isomorphic
to Gal.Kab =K/ under the Artin map, is the quotient of the unit group K b of the
finite adele ring
Y0
K
bDZ bK ˝Z Q D Kp  AK D K bC
p finite

b
by the subgroup K   K of principal ideles. On the other hand, not all au-
tomorphisms of F come from GL2 .Z b/ as in .7-9/: there is also an action of
the projective linear group PGL2 .Q / D GL2 .Q /C =Q  of rational matrices of
C

positive determinant, which naturally act on H by linear fractional transforma-

tions. It does not fix j , as it maps the elliptic curve C =Œ; 1 defined by  2 H
not to an isomorphic, but to an isogenous curve. More precisely, if we pick
M D ˛ ˇı 2 GL2 .Q /C in its residue class modulo Q  such that M 1 has

integral coefficients, then the lattice

 1
h i h i
.  C ı/ 1 Œ; 1 D ; D M 1 .˛ C ˇ/=.  C ı/; 1
 Cı  Cı
is a sublattice of finite index det M 1 in Œ.˛ C ˇ/=.  C ı/; 1; and putting
 D .  C ı/ 1 , we have a commutative diagram

C =Œ; 1 / C =ŒM ; 1D C =Œ.˛ C ˇ/=.  C ı/; 1

W  W0 
  
E / EM 
 COMPUTATIONAL CLASS FIELD THEORY 529

as in .7-3/. Moreover, the torsion point u1  Cu2 having coordinates u D .u1 ; u2 /

with respect to Œ; 1 is mapped to the torsion point with coordinates uM 1 with
respect to the basis ŒM ; 1.Q
We let Q b DZ b ˝Z Q D 0 Qp be the ring of finite Q -ideles. Then every
p
element in the ring GL2 .Q b / can be written as UM with U 2 GL2 .Z b/ and M 2
GL2 .Q /C . This representation is not unique since GL2 .Z b/ and GL2 .Q /C have
nontrivial intersection SL2 .Z /, but we obtain a well-defined action GL2 .Qb/ !
Aut.F/ by putting f UM . / D f .M /. We now extend, for the zero  2 H of
U

a polynomial X C BX C C 2 Q ŒX , the map g in .7-11/ to

2


b D .Q b / Ž GL2 .Q
b C Q b/
g W K
1
(7-12)
 
1 Bx1 C x2 C x1
x D x1  C x2 ’ Mx D
x1 x2


to obtain the complete Galois action of Gal.Kab =K/ Š K b =K  on modular
function values f . /. The result is known as Shimura’s reciprocity law:

T HEOREM 7.13. Let  2 H be imaginary quadratic, f 2 F a modular function

b=K  a finite idele for K D Q ./. Then f ./ is
that is finite at  , and x 2 K
abelian over K, and the idele x acts on it via its Artin symbol by

f ./x D f g .x/ ./;

where g is defined as in .7-12/.

8. Class invariants

Much work has gone into algorithmic improvements of the classical algo-
rithms in Section 6, with the aim of reducing the size of the class polynomials
obtained. Clearly the degree of the polynomials involved cannot be lowered,
as these are the degrees of the field extensions one wants to compute. There
are however methods to reduce the size of their coefficients. These already go
back to Weber, who made extensive use of ‘smaller’ functions than j to compute
class fields in his algebra textbook [Weber 1908]. The function f2 that we used to
compute j in .6-12/, and that carries Weber’s name (as does the elliptic
p function
in .6-14/) provides a good example. A small field such as K D Q . 71/, for
which the class group of order 7 is easily computed by hand, already has the
530 HENRI COHEN AND PETER STEVENHAGEN

sizable Hilbert class polynomial

HilK .X / D X 7 C 313645809715 X 6 3091990138604570 X 5

C 98394038810047812049302 X 4
823534263439730779968091389 X 3
C 5138800366453976780323726329446 X 2
425319473946139603274605151187659 X
C 737707086760731113357714241006081263 :

However, the Weber function f2 , when evaluated at an appropriate generator of

ZK over Z , also yields a generator for H over K, with irreducible polynomial

X7 CX6 X5 X4 X 3 C X 2 C 2X 1:

As Weber showed, the function f2 can be used to generate H over K when 2

splits and 3 does not ramify in Q  K. The general situation illustrated by this
example is that, despite the content of Theorem 7.6, it is sometimes possible to
use a function f of high level, like the Weber function f2 2 F48 of level 48, to
generate the Hilbert class field H of conductor 1. The attractive feature of such
high level functions f is that they can be much smaller than the j -function
itself. In the case of f2 , the extension Q .j /  Q .f2 / is of degree 72 by .6-
12/, and this means that the size of the coefficients of class polynomials using
f2 is about a factor 72 smaller than the coefficients of HilK .X / itself. Even
though this is only a constant factor, and complex multiplication is an intrin-
sically ‘exponential’ method, the computational improvement is considerable.
For this reason, Weber’s use of ‘small’ functions has gained renewed interest in
present-day computational practice.
Shimura’s reciprocity law Theorem 7.13 is a convenient tool to understand
the occurrence of class invariants, that is, modular functions f 2 F of higher
level that generate the Hilbert class field of K when evaluated at an appropriate
generator  ofpZK . Classical examples of such functions used by Weber are 2 D
p
3
j and 3 D j 1728, which have level 3 and 2. As is clear from .6-12/, the
j -function can also be constructed out of even smaller building blocks involving
the Dedekind -function .6-11/. Functions that are currently employed in actual
computations are
.pz/ .pz/.qz/
and ; (8-1)
.z/ .pqz/.z/
which are of level 24p and 24pq. These functions, or sometimes small powers
of them, can be used to generate H , and the resulting minimal polynomials have
much smaller coefficients than HilK .X /. We refer to [Cohen 2000, Section 6.3]
 COMPUTATIONAL CLASS FIELD THEORY 531

for the precise theorems, and indicate here how to use Theorem 7.13 to obtain
such results for arbitrary modular functions f 2 F.
Let f 2 F be any modular function of level m, and assume Q .f /  F is
Galois. Suppose we have an explicit Fourier expansion in Q .m /..q 1=m // that
we can use to approximate its values numerically. Suppose also that we know
the explicit action of the generators S W z ‘ 1=z and T W z ‘ z C 1 on f . Then
we can determine the Galois orbit of f ./ for an element  2 H that generates
ZK in the following way. First, we determine elements x D x1  C x2 2 ZK

with the property that they generate .ZK =mZK / =ZK . Then the Galois orbit
of f . / over H is determined using Theorem 7.13, and amounts to computing
the (repeated) action of the matrices g .x/ 2 GL2 .Z =mZ / (given by the right
hand side of .7-10/) on f . This

involves writing g .x/ as a product of powers
of S and T and a matrix 01 k0 acting on f via its Fourier coefficients. Although
f may have a large GL2 .Z =mZ /-orbit over Q .j /, the matrices g .x/ only

generate a small subgroup of GL2 .Z =mZ / isomorphic to .ZK =mZK / =ZK ,
and one often finds that the orbit of f under this subgroup is quite small. In many
cases, one can slightly modify f , multiplying it by suitable roots of unity or
raising it to small powers, to obtain an orbit of length one. This means that f 2 F
b   GL2 .Z
is invariant under g ŒZ b/. As we have the fundamental equivalence
K

f . /x D f ./ () f g .x/ D f; (8-2)

this is equivalent to finding that f ./ is a class invariant for K D Q ./. The
b  stabilizes f takes place modulo the level m of f , so it
verification that g ŒZ K
follows from .7-12/ that if f ./ is a class invariant for K D Q ./, then f . 0 /
is a class invariant for K 0 D Q . 0 / whenever  0 2 H is a generator of ZK 0 that
has an irreducible polynomial congruent modulo m to that of . In particular, a
function of level m that yields class invariants does so for families of quadratic
fields for which the discriminant is in certain congruence classes modulo 4m.
If f . / is found to be a class invariant, we need to determine its conjugates
over K to determine its irreducible polynomial over K as we did in .6-8/ for
j . /. This amounts to computing f ./c as in Theorem 6.9, with c ranging over
the ideal classes of ClK . If we list the ideal classes of ClK as in Section 6 as
integer triples .a; b; c/ representing the reduced quadratic forms of discriminant

K , the Galois action of their Artin symbols in Theorem 6.9 may be given by
p
b C b 2 4ac
 
.a; b;c/
j . / Dj :
2a
For a class invariant f . p/ a similar formula is provided by Shimura’s reciprocity
law. Let a D Z
.. b C b 2 4ac/=2/ C Z
a be a ZK -ideal in the ideal class
corresponding to the form .a; b; c/. Then the Z bK -ideal aZ
bK is principal since
ZK -ideals are locally principal, and we let x 2 ZK be a generator. The element
b
532 HENRI COHEN AND PETER STEVENHAGEN


b , and the Artin symbol of x 1 acts on f ./ as the Artin
x is a finite idele in K
symbol of the form .a; b; c/. We have U D g .x 1 /M 1 2 GL2 .Z b/ for the
matrix M 2 GL2 .Q / defined by
C
p
b C b 2 4ac
h i
Œ; 1M D ; 2a ;
2
since U stabilizes the ZbK -lattice spanned by the basis Œ; 1. Applying Theorem
1
7.13 for the idele x yields the desired formula
p
b C b 2 4ac
 
.a; b;c/ U
f . / Df :
2a
This somewhat abstract description may be phrased as a simple explicit recipe
for the coefficients of U 2 GL2 .Z b/, which we only need to know modulo m,
see [Stevenhagen 2001].
There are limits to the improvements coming from intelligent choices of mod-
ular functions to generate class fields. For any nonconstant function f 2 F, there
is a polynomial relation .j ; f / D 0 between j and f , with 2 C ŒX; Y  some
irreducible polynomial with algebraic coefficients. The reduction factor one
obtains by using class invariants coming from f (if these exist) instead of the
classical j -values is defined as
degf . .f; j //
r .f / D :
degj . .f; j //
By [Hindry and Silverman 2000, Proposition B.3.5], this is, asymptotically, the
inverse of the factor
h.f .//
lim :
h.j. //!1 h.j .//

Here h is the absolute logarithmic height, and we take the limit over all CM-
points SL2 .Z /
 2 H. It follows from gonality estimates for modular curves
[Bröker and Stevenhagen 2008, Theorem 4.1] that r .f / is bounded above by
1=.241 /, where 1 is ‘Selberg’s eigenvalue’ as defined in [Sarnak 1995]. The
currently proved bounds [Kim 2003, p. 176] on 1 yield r .f /  32768=325 
100:8, and conjectural bounds imply r .f /  96. Thus Weber’s function f2 ,
which has r .f / D 72 and yields class invariants for a positive density subset of
all discriminants, is close to being optimal.

Acknowledgements
Useful comments on earlier versions of this paper were provided by Reinier
Bröker, René Schoof and Marco Streng. Bjorn Poonen provided us with the
reference to [Kim 2003].
 COMPUTATIONAL CLASS FIELD THEORY 533

References
[Artin and Tate 1990] E. Artin and J. Tate, Class field theory, 2nd ed., Advanced Book
Classics, Addison-Wesley, Redwood City, CA, 1990.
[Bröker and Stevenhagen 2008] R. Bröker and P. Stevenhagen, “Constructing elliptic
curves of prime order”, pp. 17–28 in Computational Arithmetic Geometry, edited by
K. E. Lauter and K. A. Ribet, Contemp. Math. 463, 2008.
[Buhler and Wagon 2008] J. P. Buhler and S. Wagon, “Basic algorithms in number
theory”, pp. 25–68 in Surveys in algorithmic number theory, edited by J. P. Buhler
and P. Stevenhagen, Math. Sci. Res. Inst. Publ. 44, Cambridge University Press, New
York, 2008.
[Bump et al. 2003] D. Bump, J. W. Cogdell, E. de Shalit, D. Gaitsgory, E. Kowalski,
and S. S. Kudla, An introduction to the Langlands program, Birkhäuser Boston
Inc., Boston, MA, 2003. Lectures presented at the Hebrew University of Jerusalem,
Jerusalem, March 12–16, 2001, Edited by Joseph Bernstein and Stephen Gelbart.
[Cassels and Fröhlich 1967] J. W. S. Cassels and A. Fröhlich (editors), Algebraic
number theory, Academic Press, London, 1967.
[Cohen 1993] H. Cohen, A course in computational algebraic number theory, Graduate
Texts in Mathematics 138, Springer, Berlin, 1993.
[Cohen 2000] H. Cohen, Advanced topics in computational number theory, Graduate
Texts in Mathematics 193, Springer, New York, 2000.
[Cox 1989] D. A. Cox, Primes of the form x 2 C ny 2 : Fermat, class field theory and
complex multiplication, John Wiley & Sons, New York, 1989.
[Deuring 1958] M. Deuring, Die Klassenkörper der komplexen Multiplikation, Enzyk-
lopädie der mathematischen Wissenschaften, Band I2 , Heft 10, Teil II, Teubner,
Stuttgart, 1958.
[Fieker 2001] C. Fieker, “Computing class fields via the Artin map”, Math. Comp.
70:235 (2001), 1293–1303.
[Hindry and Silverman 2000] M. Hindry and J. H. Silverman, Diophantine geometry:
an introduction, Graduate Texts in Mathematics 201, Springer, New York, 2000.
[Kim 2003] H. H. Kim, “Functoriality for the exterior square of GL4 and the symmetric
fourth of GL2 ”, J. Amer. Math. Soc. 16:1 (2003), 139–183.
[Lang 1987] S. Lang, Elliptic functions, Second ed., Graduate Texts in Mathematics
112, Springer, New York, 1987.
[Lang 2002] S. Lang, Algebra, Third ed., Graduate Texts in Mathematics 211, Springer,
New York, 2002.
[Sarnak 1995] P. Sarnak, “Selberg’s eigenvalue conjecture”, Notices Amer. Math. Soc.
42:11 (1995), 1272–1277.
[Schneps 1994] L. Schneps (editor), The Grothendieck theory of dessins d’enfants
(Luminy, 1993), London Math. Soc. Lecture Note Ser. 200, Cambridge Univ. Press,
Cambridge, 1994.
534 HENRI COHEN AND PETER STEVENHAGEN

[Schoof 2008] R. J. Schoof, “Computing Arakelov class groups”, pp. 447–495 in

Surveys in algorithmic number theory, edited by J. P. Buhler and P. Stevenhagen,
Math. Sci. Res. Inst. Publ. 44, Cambridge University Press, New York, 2008.
[Serre 1989] J.-P. Serre, Abelian l-adic representations and elliptic curves, Second ed.,
Advanced Book Classics, Addison-Wesley, Redwood City, CA, 1989.
[Shimura 1998] G. Shimura, Abelian varieties with complex multiplication and modu-
lar functions, Princeton Mathematical Series 46, Princeton University Press, Prince-
ton, NJ, 1998.
[Silverman 1986] J. H. Silverman, The arithmetic of elliptic curves, Graduate Texts in
Mathematics 106, Springer, New York, 1986.
[Silverman 1994] J. H. Silverman, Advanced topics in the arithmetic of elliptic curves,
Graduate Texts in Mathematics 151, Springer, New York, 1994.
[Stevenhagen 2001] P. Stevenhagen, “Hilbert’s 12th problem, complex multiplication
and Shimura reciprocity”, pp. 161–176 in Class field theory — its centenary and
prospect (Tokyo, 1998), edited by K. Miyake, Adv. Stud. Pure Math. 30, Math. Soc.
Japan, Tokyo, 2001.
[Stevenhagen 2008] P. Stevenhagen, “The arithmetic of number rings”, pp. 209–266
in Surveys in algorithmic number theory, edited by J. P. Buhler and P. Stevenhagen,
Math. Sci. Res. Inst. Publ. 44, Cambridge University Press, New York, 2008.
[Stevenhagen and Lenstra 1996] P. Stevenhagen and H. W. Lenstra, Jr., “Chebotarëv
and his density theorem”, Math. Intelligencer 18:2 (1996), 26–37.
[Völklein 1996] H. Völklein, Groups as Galois groups: an introduction, Cambridge
Studies in Advanced Mathematics 53, Cambridge Univ. Press, Cambridge, 1996.
[Weber 1908] H. Weber, Lehrbuch der Algebra, F. Vieweg und Sohn, Braunschweig,
1908. Reprinted by Chelsea Pub., New York, 1961.

H ENRI C OHEN
L ABORATOIRE A2X, U.M.R. 5465 DU C.N.R.S.
U NIVERSIT É B ORDEAUX I
351 C OURS DE LA L IB ÉRATION
33405 TALENCE C EDEX
F RANCE
cohen@math.u-bordeaux1.fr

P ETER S TEVENHAGEN
M ATHEMATISCH I NSTITUUT,
U NIVERSITEIT L EIDEN , P OSTBUS 9512
2300 RA L EIDEN
T HE N ETHERLANDS
psh@math.leidenuniv.nl