COMPUTING RAY CLASS GROUPS,

CONDUCTORS AND DISCRIMINANTS

H. Cohen, F. Diaz y Diaz and M. Olivier

Abstract. We describe algorithmic tools to compute exact sequences of Abelian groups, and use them to compute the complete structure of (ℤ_{K}/𝔪)^{∗} for an ideal 𝔪 of a number field K, as well as ray class groups of number fields, and conductors and discriminants of the corresponding Abelian extensions. As an application we give several number fields with discriminants less than previously known ones.

The paper is divided as follows. In §1, we describe the tools necessary for dealing with exact sequences of Abelian groups (mainly finite). In §2, we apply these tools to the determination of the groups (ℤ_{K}/𝔪)^{∗} for an arbitrary modulus 𝔪. In §3, we give a complete algorithm for computing the ray class group of a number field, and also for solving the corresponding principal ideal problem. In §4, we explain how to compute signatures, conductors and discriminants of the fields associated to subgroups of the ray class group by global class field theory. In principle we can give relative and absolute discriminants of all Abelian extensions of a given base field. Finally in §5, we give some numerical examples obtained by these methods. In particular, we obtain in this way 7 totally complex number fields of degree less than 80 whose discriminants are less than previously known ones.

Using Kummer theory (see e.g. [Da-Po]), we can usually also obtain a defining equation for these number fields, and we have done this for the three new fields of smallest degree that we have found.

1. Exact sequences of Abelian groups

In this section, we consider finitely generated (in fact usually finite) Abelian groups which, in view of our applications, will be written multiplicatively. The word “group” will always mean finitely generated Abelian group.

We will use systematically matrix notation as follows. Let A be a group and let A = (α_{1}, …, α_{r}) be a row vector of elements in A. If X is a column vector with integer entries x_{i}, we denote by AX the element ∏_{i} α_{i}^{x_{i}} of A. More generally, if M is a matrix with r rows having integer entries, we denote by AM the row vector of the elements β_{j} = AM_{j}, where M_{j} denotes the j-th column of M. If A and B are row vectors or matrices with the same number of rows, we denote by (A|B) the (horizontal) concatenation of A and B.

Typeset by AMS-TEX

Key words and phrases. Exact sequences, Ray class groups, Conductors, Discriminants.

1991 Mathematics Subject Classification. Primary 11R37, 11Y40.

If X and Y are column vectors, we will denote by (\frac{X}{Y}) the (vertical) concatenation of X and Y.

Note that row vectors will always represent a list of elements in some Abelian group, while column vectors and matrices will always have integer (or sometimes rational) coefficients.

Definition 1.1. Let A be a group, G = (g_{1}, …, g_{r}) be elements of A, and M be a matrix with r rows and integral entries. We say that (G, M) is a system of generators and relations for A if the g_{i} are generators, and if any relation between the g_{i} is a linear combination with integer coefficients of the columns of the matrix M. In matrix terms, this can be written concisely as follows:

α ∈ A ⟺ ∃X ∈ ℤ^{r}, GX = α ,
GX = 1 ⟺ ∃Y ∈ ℤ^{r}, X = MY

(in particular, we have GM = 1, where 1 is a row vector of unit elements of A).

Another way of writing the above is the existence of the following exact sequence (i.e. a presentation of A):

ℤ^{k} ⟶^{M} ℤ^{r} ⟶^{G} A ⟶ 1 .

Definition 1.2. Let A be a group. We say that (A, D_{A}) is a Smith normal form for A if (A, D_{A}) is a system of generators and relations for A and if D_{A} is a diagonal matrix in Smith normal form (i.e. the diagonal elements a_{i} satisfy a_{i+1} | a_{i} for i < r) and no diagonal element is equal to 1.

Note that, by the elementary divisor theorem we know that there exists a Smith normal form and that the matrix D_{A} is unique. On the other hand, the generators A are not unique.

The following algorithm, although immediate, will be of constant use.

Algorithm 1.3 (SNF for groups). Let (G, M) be a system of generators and relations for a finite group A. This algorithm computes a Smith normal form (A, D_{A}) for A. It also outputs a matrix which will be useful for later use.

1. [Apply Hermite] Let H be the Hermite normal form of the matrix M obtained by applying the HNF algorithm. If H is not a square matrix (i.e. if M was not of maximal rank), output an error message stating that M cannot be a complete system of relations or that A is infinite, and terminate.

2. [Apply Smith] Using the Smith normal form algorihm, compute unimodular matrices U and V and a diagonal matrix D in Smith normal form such that UHV = D. Set A′ ← GU^{−1}.

3. [Remove trivial components] Let n be the largest i such that D_{i,i} ≠ 1 (0 if none exists). Let D_{A} be the matrix obtained from D be keeping only the first n rows and columns, let A be the row obtained by keeping only the first n entries of A′, and let U_{a} be the (not necessarily square) matrix obtained by keeping only the first n rows of U. Output (A, D_{A}), output U_{a} and terminate the algorithm.

The validity of this algorithm is clear. Note the important relation AU_{a} = G. Moreover, if an element α of A is known on the generators G as α = GX, then on the new generators A we have α = A(U_{a}X), so the matrix U_{a} allows us to go from one system of generators to another.

We can now set the following definitions.

Definition 1.4. Let A be a group. We say that we have effectively computed the group A if we have done the following.

(1) We have computed a system (G, M) of generators and relations for the group A, or equivalently by Algorithm 1.3, a Smith normal form (A, D_{A}).

(2) We have an algorithm which, given an element α ∈ G, finds a column vector X with integer entries such that α = GX (or α = AX if we have the SNF). The column vector X will be called the discrete logarithm of α on the given generators.

When we say that we compute an Abelian group, we will always mean compute in the above sense.

A similar definition applies to maps:

Definition 1.5. Let A and B be two groups and ψ a homomorphism from A to B. We say that ψ is algorithmically known if the following properties are true. If B has been computed, then if α ∈ A, we can compute ψ(α) expressed on the generators of B. Conversely, if A has been computed, then, if β ∈ Im(ψ), we can compute α ∈ A such that β = ψ(α).

1.1. Computing quotients

Let

1 ⟶ A ⟶^{ψ} B ⟶^{ϕ} C ⟶ 1

be a 3-term exact sequence of Abelian groups. In this section, we assume that A and B are known (in the sense of Definition 1.4), and that we want to compute C. We assume also that the maps ψ and ϕ are algorithmically known. Let (A, D_{A}) (resp. (B, D_{B})) be a Smith normal form of A (resp. B) (note that it is only necessary for these to be generators and relations, but usually they will be in SNF). Since ϕ is surjective, it is clear that if we set B′ = ϕ(B), B′ is a system of generators of C. We must find all the relations between them. Let V = (v_{i}) be such a relation, expressed as a column vector. Then

B′V = 1 ⟺ BV ∈ Im(ψ) ⟺ BV = ψ(A)X

for a certain integer vector X.

However, since the group B is known, we know how to compute algorithmically a matrix P such that ψ(A) = BP. Hence

B′V = 1 ⟺ BV = BP X ⟺ B(V − P X) = 1
⟺ V − P X ∈ Im(D_{B}) ⟺ V ∈ Im(P |D_{B}) .

It follows that (ϕ(B), (P |D_{B})) is a system of generators and relations for C. Formally, this gives the following.

Algorithm 1.6 (Quotient of groups). Given two groups A = (A, D_{A}) and B = (B, D_{B}) in SNF and an exact sequence 1 ⟶ A ⟶^{ψ} B ⟶^{ϕ} C ⟶ 1, this algorithm computes the SNF of the group C.

1. [Compute P] Using the discrete logarithm problem in B, compute a matrix P such that ψ(A) = BP.

2. [Compute SNF] Apply Algorithm 1.3 to (ϕ(B), (P |D_{B})), output the SNF (C, D_{C}) of the result and the auxilliary matrix U_{a}, and terminate the algorithm.

To solve the discrete logarithm problem, we proceed as follows. Let γ ∈ C. Since ϕ is surjective and is known algorithmically, we can find β ∈ B such that γ = ϕ(β). Since we know how to compute discrete logarithms in B, we can find X such that β = BX, hence

γ = ϕ(BX) = ϕ(B)X = CU_{a}X ,

where U_{a} is the auxilliary matrix output by Algorithm 1.3. It follows that the discrete logarithm of γ on the generators C is given by the vector U_{a}X.

1.2. Computing kernels

Although we will not need to compute kernels in this paper, to be complete we also give the algorithm. Let B = (B, D_{B}) and C = (C, D_{C}) given in SNF, and assume again that we have an exact sequence

1 ⟶ A ⟶^{ψ} B ⟶^{ϕ} C ⟶ 1 .

We want to compute the SNF (A, D_{A}) of A. For this, we will compute the kernel of ϕ as an Abelian group. Since ψ will give an explicit isomorphism between A and this kernel, and we assume that it is given algorithmically (as well as its inverse) we will thus have computed A.

Now β ∈ B is in the kernel of ϕ if and only if β = BX for some column vector X satisfying ϕ(BX) = 1. In other words β ∈ Ker(ϕ) ⟺ ϕ(B)X = 1. Since we can solve the discrete logarithm problem in C we can compute a matrix P such that ϕ(B) = CP. Thus

β ∈ Ker(ϕ) ⟺ CP X = 1 ⟺ P X ∈ Im D_{C} ⟺ P X + D_{C}Y = 0

for some integer vector Y. Let R = (\frac{X}{Y}). We thus have

β ∈ Ker(ϕ) ⟺ (P |D_{C})R = 0 for some Y .

This is an instance of the integer kernel problem for which we refer to [Coh]. We thus obtain the following algorithm.

Algorithm 1.7 (Kernels of groups). Given two groups B = (B, D_{B}) and C = (C, D_{C}) in SNF and an exact sequence 1 ⟶ A ⟶^{ψ} B ⟶^{ϕ} C ⟶ 1, this algorithm computes the SNF of the group A.

1. [Compute matrix P] Using the discrete logarithm problem in C, compute a matrix P such that ϕ(B) = CP.

2. [Compute generators] Applying the HNF algorithm, compute a unimodular matrix U such that (P |D_{C})U = (0|W) where W is in HNF. If r is the number of elements of B, let K be the upper left r × r submatrix of U, and set A′ ← BK.

3. [Compute relations] Applying the HNF algorithm, compute a unimodular matrix U′ such that (K|D_{B})U′ = (0|W′) where W′ is in HNF. Let K′ be the upper left r × r submatrix of U′.

4. [Terminate] Find A′′ such that A′ = ψ(A′′) (which is possible since ψ is algorithmically known), apply Algorithm 1.3 to (A′′, K′), output the SNF (A, D_{A}) and the auxilliary matrix U_{a}K^{−1} (we will see below that K is invertible in GL_{r}(ℚ)), and terminate the algorithm.

To solve the discrete logarithm problem, let α ∈ A and β = ψ(α). Since we know how to solve the discrete logarithm problem in B, we can find X such that β = BX. Since β ∈ Ker(ϕ), the above reasoning shows that X is in the image of K. Assume proved that the matrix K is invertible (in GL_{r}(ℚ)). Then, if Y = K^{−1}X, Y must have integral entries since X is in the ℤ-image of K, and we have

ψ(A′′)Y = A′Y = BKY = BX = β = ψ(α) ,

and since ψ is injective, α = A′′Y, hence Y is the discrete logarithm on the generators A′′, hence as usual the desired discrete logarithm is equal to U_{a}Y = U_{a}K^{−1}X.

Thus we must prove the following lemma.

Lemma 1.8. Assume that we have a matrix equality of the form (P |D)U = (0|W), where U is invertible and D is a square matrix with nonzero determinant. Let r be the number of columns of P, or equivalently the number of 0 columns on the right hand side. Then if K is the upper left r × r submatrix of U, then K has nonzero determinant.

Proof. Write U = ( \begin{matrix}K & L \\ M & N \end{matrix} ), and let X be a column vector such that KX = 0. Since

P K + DM = 0, we have P KX + DMX = 0 so DMX = 0, and since D has nonzero determinant, MX = 0. This implies that U(\frac{X}{0}) = 0, and since U is invertible, X = 0 so the kernel of K is reduced to 0 and hence K has nonzero determinant. (Note that it is easy to write the inverse of K in GL_{r}(ℚ) in terms of the block matrix decomposition of U^{−1}.) ⊓ ⊔

1.3. Computing group extensions

This is by far the most important and useful case. Let A = (A, D_{A}) and C = (C, D_{C}) given in SNF, and assume again that we have an exact sequence

1 ⟶ A ⟶^{ψ} B ⟶^{ϕ} C ⟶ 1 .

We want to compute the SNF (B, D_{B}) of the group B.

Let B′ be chosen (arbitrarily but algorithmically) such that ϕ(B′) = C. Let β ∈ B. We can write ϕ(β) = CX = ϕ(B′)X = ϕ(B′X), hence β −B′X ∈ Ker(ϕ) so β −B′X = ψ(AY) for some integer vector Y. Thus β = B′X + ψ(A)Y = (B′|ψ(A))R where R = (\frac{X}{Y}). It follows that (B′|ψ(A)) forms a generating set for B (this is of course trivial, but we prefer to do everything in matrix terms).

Let us find the relations between these generators. If R = (\frac{X}{Y}) is such a relation, we have B′X + ψ(A)Y = 1. If we apply ϕ to this relation, we obtain ϕ(B′)X = CX = 1, hence X ∈ Im D_{C}, i.e. X = D_{C}X_{1}. Thus we have B′D_{C}X_{1} + ψ(A)Y = 1.

Set B′′ = B′D_{C}. Then ϕ(B′′) = ϕ(B′)D_{C} = CD_{C} = 1. Thus the entries of B′′ are in Ker(ϕ) = Im(ψ), hence since we can solve the discrete logarithm problem in A we can find a matrix P such that B′′ = ψ(AP) = ψ(A)P.

So finally, the equation for our relation is

ψ(A)P X_{1} + ψ(A)Y = 1 ⟺ ψ(A)(P X_{1} + Y) = 1 ⟺ P X_{1} + Y ∈ Im D_{A}
⟺ P X_{1} + Y = D_{A}T for some integer vector T .

In other words, R is a relation if and only if we have

R = ( \begin{matrix}D_{C} & 0 \\ −P & D_{A} \end{matrix} ) ( \begin{matrix}X_{1} \\ T \end{matrix} )

for some integer vectors X_{1} and T. We then obtain the SNF as before by applying Algorithm 1.3. Formally, this gives the following.

Algorithm 1.9 (Group extensions). Given two groups A = (A, D_{A}) and C = (C, D_{C}) in SNF and an exact sequence 1 ⟶ A ⟶^{ψ} B ⟶^{ϕ} C ⟶ 1, this algorithm computes the SNF (B, D_{B}) of the group B.

1. [Compute generators] Compute B′ such that ϕ(B′) = C (which can be done since ϕ is known algorithmically), and compute ψ(A).

2. [Compute P] Set B′′ ← B′D_{C}, and let A′′ be such that B′′ = ψ(A′′) (B′′ is in the image of ψ and A′′ can be found since ψ is known algorithmically). Using the discrete logarithm problem in A, compute a matrix P such that A′′ = AP.

3. [Terminate] Set G ← (B′|ψ(A)) and M ← ( \begin{matrix}D_{C} & 0 \\ −P & D_{A} \end{matrix} ). Apply Algorithm 1.3 to the

system of generators and relations (G, M), output the SNF (B, D_{B}) of B and the auxilliary matrix U_{a}, and terminate the algorithm.

To solve the discrete logarithm problem is easy. Let β ∈ B. Using the discrete logarithm in C we can find X such that ϕ(β) = CX = ϕ(B′)X, hence ϕ(β − B′X) = 1 so β − B′X ∈ Im(ψ), and using the discrete logarithm problem in A we obtain β − B′X = ψ(A)Y for some Y, so β = (B′|ψ(A))(\frac{X}{Y}). Finally, this gives β = BU_{a}(\frac{X}{Y}) hence U_{a}(\frac{X}{Y}) is our desired discrete logarithm.

Remark. From the above discussion, it is clear that the matrix −P measures exactly the obstruction to the fact that the exact sequence is split.

1.4. Four-term exact sequences

In view of our application to ray class group computations, we will also use four term exact sequences. More precisely, assume that we have an exact sequence of the form

E ⟶^{ρ} Z ⟶^{ψ} B ⟶^{ϕ} C ⟶ 1 .

We assume that we know the groups E = (E, D_{E}), Z = (Z, D_{Z}) and C = (C, D_{C}), and we want to compute B. Note that in the application that we have in mind, E is in general infinite, and in that case the diagonal entry of D_{E} is equal to 0 for each infinite cyclic component. This could be treated as a 3-term exact sequence by introducing the group Z/ρ(E), but it is more elegant and just as easy to treat it directly as a four term exact sequence. We leave the details to the reader, and simply give the algorithm.

Algorithm 1.10 (our-term exact sequences). Given three groups E = (E, D_{E}), Z = (Z, D_{Z}) and C = (C, D_{C}) in SNF and an exact sequence E ⟶^{ρ} Z ⟶^{ψ} B ⟶^{ϕ} C ⟶ 1, this algorithm computes the SNF (B, D_{B}) of the group B.

1. [Compute generators] Compute B′ such that ϕ(B′) = C (which can be done since ϕ is known algorithmically), and compute ψ(Z).

2. [Compute P] Set B′′ ← B′D_{C}, and let Z′ be such that B′′ = ψ(Z′) (B′′ is in the image of ψ and Z′ can be found since ψ is known algorithmically). Using the discrete logarithm problem in Z, compute a matrix P such that Z′ = ZP.

3. [Compute Q] Using the discrete logarithm problem in Z, compute a matrix Q such that ρ(E) = ZQ.

4. [Terminate] Set G ← (B′|ψ(Z)) and M ← ( \begin{matrix}D_{C} & 0 & 0 \\ −P & Q & D_{Z} \end{matrix} ). Apply Algorithm 1.3 to

the system of generators and relations (G, M), output the SNF (B, D_{B}) of B and the auxilliary matrix U_{a} and terminate the algorithm.

In our application to ray class group computations, the group E will be the group of units of a number field, hence finitely generated but not finite in general. However, as can be seen from step 3, only a finite set of generators is needed. Apart from this group, all of the other groups that we will use are finite.

To solve the discrete logarithm problem is again easy. Let β ∈ B. Using the discrete logarithm in C we can find X such that ϕ(β) = CX = ϕ(B′)X, hence ϕ(β − B′X) = 1 so β − B′X ∈ Im(ψ). Since Z has been computed and ψ is known algorithmically, using the discrete logarithm problem in Z we obtain β − B′X = ψ(Z)Y for some Y, so β = (B′|ψ(Z))(\frac{X}{Y}). Finally, this gives β = BU_{a}(\frac{X}{Y}) hence U_{a}(\frac{X}{Y}) is our desired discrete logarithm.

2. Computing the structure of (ℤ_{K}/𝔪)^{∗}

Let K be a number field, and 𝔪 a modulus in K, in other words 𝔪 = 𝔪_{0}𝔪_{∞} is a (formal) product of an integral ideal of K and a subset of the set of real places of K. We denote by ℤ_{K} the ring of integers of K.

In this section, we explain how to compute the group (ℤ_{K}/𝔪)^{∗} in the sense of Definition 1.4. The theoretical answer to this question is in principle solved in [Nak]. However this is not suited to algorithmic purposes, and in addition is much more complicated than the solution we present below.

We must first explain how to represent elements of (ℤ_{K}/𝔪)^{∗}: if 𝔪 = 𝔪_{0}𝔪_{∞} we simply represent an element in (ℤ_{K}/𝔪)^{∗} as a pair (\overline{α}, v) where \overline{α} ∈ (ℤ_{K}/𝔪_{0})^{∗} and v ∈ 𝔽_{2}^{𝔪_{∞}} considered as a column vector. Note that even when 𝔪 is an ideal (i.e. 𝔪_{∞} is empty), we still consider pairs (\overline{α}, v) where v is the unique vector in 0-dimensional space over 𝔽_{2}. If (\overline{α}, v) ∈ (ℤ_{K}/𝔪)^{∗}, we will say that \overline{α} is the finite part, and v the infinite part or the Archimedean part. The group law in (ℤ_{K}/𝔪)^{∗} corresponds to multiplying the finite parts and adding the infinite parts. In all the algorithms that we will present, the above representation is sufficient and simpler than the single element representation. In some cases, however, it may be desirable to obtain such a single element representation. For this, the following simple-minded algorithm works very well.

Algorithm 2.1 (One-element representation in (ℤ_{K}/𝔪)^{∗}. ) Let 𝔪 = 𝔪_{0}𝔪_{∞} be a modulus and (\overline{α}, v) a pair representing an element of (ℤ_{K}/𝔪)^{∗}, with v = (v_{j})_{j∈𝔪_{∞}}. Call s the sign homomorphism from ℤ_{K} to 𝔽_{2}^{𝔪_{∞}}. This algorithm computes an element β ∈ ℤ_{K} such that β ≡ α (mod 𝔪_{0}) and s(β) = v. We let k = |𝔪_{∞}|. 1.[Initialize] If not already done so, compute a ℤ-basis γ_{1}, …,γ_{n} of the ideal 𝔪_{0}. 2.[Find elements] By considering small linear combinations of the γ_{i}, find k elements β_{1}, …,β_{k}

such that the matrix A over 𝔽_{2} whose columns are the s(β_{j}) is invertible. 3.[Multiply] Set w ← A^{−1}v, and let w = (w_{j}). Set β ← α, and for each j such that w_{j} ≠ 0, set β ← ββ_{j}. Output β and terminate the algorithm.

Evidently if many conversions of this sort must be done, steps 1 and 2 should be done once and for all. Note that the final β may be large, and it may be desired to reduce it. This cannot be done too rashly however, since we must now preserve the signature of β. We will discuss this in §3.

We first deal with the finite part, i.e. we will start by computing (ℤ_{K}/𝔪_{0})^{∗}, and deal with 𝔪_{∞} later.

Lemma 2.2. Let 𝔞 and 𝔠 be two coprime integral ideals of K.

(1) We can find in polynomial time elements a ∈ 𝔞 and c ∈ 𝔠 such that a + c = 1.

(2) Set 𝔟 = 𝔞𝔠. We have a split exact sequence

1 ⟶ (ℤ_{K}/𝔞)^{∗} ⟶^{ψ} (ℤ_{K}/𝔟)^{∗} ⟶^{ϕ} (ℤ_{K}/𝔠)^{∗} ⟶ 1 ,

where ψ(\overline{α}) = \overline{cα + a}, ϕ(\overline{β}) = \overline{β} and a section σ of ϕ is given by σ(\overline{γ}) = \overline{aγ + c}. (Here denotes the classes in the respective groups, but using the same notation for each will not lead to any confusion as long as we know in which group we work.)

Proof. (1) By assumption, we have 𝔞 + 𝔠 = ℤ_{K}. Thus there exist a ∈ 𝔞 and c ∈ 𝔠 such that a + c = 1. The algorithm to find them is explained in [Coh2]. For completeness we sketch it here. Let A (resp. C) be the Hermite normal form of 𝔞 and 𝔠 on some fixed integral basis of ℤ_{K}. We assume (it is easy to reduce to this case) that the first element of the integral basis is 1. We apply the Hermite normal form algorithm to the matrix (A|C). If U is a unimodular matrix obtained during the HNF, we have (A|C)U = (0|I) where I is the d×d identity matrix (where d = [K : ℚ]) since 𝔞 and 𝔠 are coprime. Let X_{1} (resp. X_{2}) be the top (resp. bottom) half of the (d + 1)st column of U. Then AX_{1} and CX_{2} represent on the integral basis elements a and c satisfying the required conditions.

The proof of (2) is straightforward and tedious, and left to the reader. ⊓ ⊔

Remark. More generally, if 𝔞 and 𝔠 are two coprime moduli (i.e. 𝔞_{0} + 𝔠_{0} = ℤ_{K} and 𝔞_{∞} ∩ 𝔠_{∞} = ∅) there exist elements a and c such that a + c = 1, a ≡ 1 (mod ^{∗}𝔠), c ≡ 1 (mod ^{∗}𝔞) and these elements can also be found by a polynomial-time algorithm. There is also an exact sequence generalizing (2).

We have mentioned in §1.3 that the matrix P introduced there measures the obstruction to an exact sequence being split. Let (ℤ_{K}/𝔞)^{∗} = (A, D_{A}) and (Z_{K}/𝔠)^{∗} = (C, D_{C}). If we follow the algorithm explained in §1.3, we must first choose lifts B′ of C. Since our sequence is split, we will take B′ = σ(\overline{C}) = \overline{aC + c1}. Since σ is a homomorphism, we have B′D_{C} = σ(\overline{CD_{C}}) = σ(\overline{1}) = \overline{1}, hence P = 0 as claimed.

Thus, to obtain the structure of (ℤ_{K}/𝔟)^{∗} we simply use D_{A} and D_{C} as diagonal blocks and perform the Smith normal form Algorithm 1.3.

From the above results, we see that to compute (ℤ_{K}/𝔞)^{∗} for an ideal 𝔞, it is enough to compute (ℤ_{K}/𝔭^{k})^{∗} for a prime ideal 𝔭 and a positive integer k, and we now consider this problem.

Definition and Proposition 2.3. Let 𝔞 and 𝔟 be (nonzero) ideals Assume that 𝔞 | 𝔟 | 𝔞^{k} for some positive integer k. We denote by (1 + 𝔞)/(1 + 𝔟) the quotient set of 1 + 𝔞 by the equivalence relation R defined by (1 + x)R(1 + y) ⟺ x ≡ y (mod 𝔟). Then multiplication in K induces a multiplication in (1 + 𝔞)/(1 + 𝔟) which makes this set into an Abelian group.

Proof. It is clear that R is an equivalence relation. Since 𝔞 is an ideal, 1 + 𝔞 is stable by multiplication, and since 𝔟 is an ideal, R is compatible with multiplication. Thus (1 + 𝔞)/(1 + 𝔟) has a natural commutative multiplication and the class of 1 is the unit element. We only need to show that any element has an inverse. But if x ∈ 𝔞, then by assumption x^{k} ∈ 𝔟. It follows that for any x ∈ 𝔞 we have

(1 + x) (1 + ∑_{i=1}^{k−1}(−1)^{i}x^{i}) = 1 + (−1)^{k−1}x^{k} ,

hence, if we set y = ∑_{i=1}^{k−1}(−1)^{i}x^{i}, then y ∈ 𝔞 and (1 + x)(1 + y) − 1 ∈ 𝔟 so the class of 1 + y is an inverse of the class of 1 + x. Thus (1 + 𝔞)/(1 + 𝔟) is in a natural way an Abelian group.

Note that it is not difficult to prove that this group is also finite. This will in fact follow from the results proven in the rest of this section. ⊓ ⊔

Proposition 2.4. Let 𝔭 be a prime ideal of degree f, and let q = p^{f} = |ℤ_{K}/𝔭|. Set G = (ℤ_{K}/𝔭^{k})^{∗}. Let

W = {x ∈ G | x^{q−1} = 1} and G_{𝔭} = (1 + 𝔭)/(1 + 𝔭^{k}) .

Then

(1) W ≃ (ℤ_{K}/𝔭)^{∗}, and in particular W is a cyclic subgroup of order q − 1 of G. More precisely, if \overline{g_{0}} is a generator of (ℤ_{K}/𝔭)^{∗}, then ⌈log_{2}(k)⌉ iterations of g ← g − (g^{q−1} − 1)/((q − 1)g^{q−2}) mod 𝔭^{k} applied to g_{0} gives a generator of W.

(2) G_{𝔭} is a p-subgroup of G of order q^{k−1}.

(3) G = W × G_{𝔭}.

We leave the (easy) proof to the reader. ⊓ ⊔

Finding a generator \overline{g_{0}} of the finite field (ℤ_{K}/𝔭)^{∗} is easily done if q − 1 is completely factored, simply by trying random elements. Since the probability of finding a generator is ϕ(q − 1)/(q − 1), this is quite close to 1 in general, so g_{0} will be found rapidly.

On the other hand, the converse problem which we also need to solve, of computing discrete logarithms in (ℤ_{K}/𝔭)^{∗}, is a famous problem for which there exists a vast literature. Note however that, in the context of number fields, q will not be too large in general, hence rather simple-minded techniques such as Shanks’s baby-step giant step method can be used. However if we deal with inert primes of the order of a few thousands in number fields of degree 20 (this is a reasonable proposition with today’s capabilities), then q will have of the order of 70 decimal digits, and the problem starts to become extremely difficult. In this paper, we assume that we deal with numbers of reasonable size.

Once g_{0} is found, doing the Hensel iterations explained in Proposition 2.4. (1) is easy. Similarly, once one knows how to compute discrete logarithms in (ℤ_{K}/𝔭)^{∗}, lifting them to W is also easy. In fact, as we will see we do not even need to perform these Hensel liftings.

So the task that remains before us is the computation of the group G_{𝔭} = (1+𝔭)/(1+𝔭^{k}). An idea that immediately comes to mind is the use of 𝔭-adic logarithms. When the

ramification index e of 𝔭 is not too large (more precisely when e < p − 1), then the 𝔭-adic logarithm series induces an explicit isomorphism between G_{𝔭} and the additive group 𝔭/𝔭^{k}, and computing this last group is easy. Although simple, this method cannot be applied in all cases, hence we prefer to use the more complicated but general method based on the following ideas.

Proposition 2.5.

(1) Let a ≤ b ≤ c be integers. We have the exact sequence

1 ⟶ (1 + 𝔭^{b})/(1 + 𝔭^{c}) ⟶ (1 + 𝔭^{a})/(1 + 𝔭^{c}) ⟶ (1 + 𝔭^{a})/(1 + 𝔭^{b}) ⟶ 1 .

(2) Assume that b ≤ 2a. Then the map from the multiplicative group (1 + 𝔭^{a})/(1 + 𝔭^{b}) to the additive group 𝔭^{a}/𝔭^{b} which sends the class of 1 + x modulo 1 + 𝔭^{b} to the class of x modulo 𝔭^{b} is well defined and is a group isomorphism.

Proof. Trivial and left to the reader. Note that in (2) the condition b ≤ 2a is only needed for the map to be a group homomorphism, otherwise the map is always well defined and is a bijection between the two sets. ⊓ ⊔

Assume that we can compute 𝔭^{a}/𝔭^{b} for a ≤ b ≤ 2a. Using the explicit isomorphism, we thus compute (1 + 𝔭^{a})/(1 + 𝔭^{b}). Then using inductively Proposition 2.5 (1) and §1.3, we compute (1 + 𝔭)/(1 + 𝔭^{2}), (1 + 𝔭)/(1 + 𝔭^{4}), …,(1 + 𝔭)/(1 + 𝔭^{2^{m}}), (1 + 𝔭)/(1 + 𝔭^{k}), where m = ⌊log_{2}(k − 1)⌋. By §1.3, this will give the structure of G_{𝔭}, hence of (ℤ_{K}/𝔭^{k})^{∗} and enable us also to solve the discrete logarithm problem in (ℤ_{K}/𝔭^{k})^{∗}.

Apart from the computation of 𝔭^{a}/𝔭^{b} which is easily done (see below), this description of the method is completely explicit, and we could almost end here this section. However it seems preferable to give a little more detail on the setup.

To compute 𝔭^{a}/𝔭^{b} algorithmically, the simplest is perhaps to proceed as follows. Let 𝔭 = pℤ_{K} + πℤ_{K} be a two-element representation of 𝔭, where we may assume π chosen so that v_{𝔭}(π) = 1 (if this is not the case, then v_{𝔭}(p) = 1, i.e. 𝔭 is unramified, and hence we replace π by π + p).

Then for all m, if q = ⌈m/e⌉ = ⌊(m + e − 1)/e⌋ where e = e(𝔭/p) is the ramification index of 𝔭, we have 𝔭^{m} = p^{q}ℤ_{K} + π^{m}ℤ_{K}. Indeed, for any prime ideal 𝔮 different from 𝔭, min(v_{𝔮}(p), v_{𝔮}(π)) = 0, hence v_{𝔮}(p^{q}ℤ_{K} + π^{m}ℤ_{K}) = 0, while v_{𝔭}(p^{q}ℤ_{K} + π^{m}ℤ_{K}) = min(qv_{𝔭}(p), mv_{𝔭}(π)) = min(qe, m) = m.

From this, it is easy to compute the Hermite normal form of 𝔭^{m} on some fixed integral basis of ℤ_{K}: construct the n × 2n matrix whose obtained by concatenating p^{q} times the identity matrix with the n × n matrix giving the endomorphism multiplication by π^{m} on the integral basis, and then apply a Hermite normal form algorithm to obtain the desired HNF.

Let A and B be the HNF matrices of 𝔭^{a} and 𝔭^{b} obtained as above. The columns of A (resp. B) give on the chosen integral basis a ℤ-basis (α_{i}) of the ideal 𝔭^{a} (resp. (β_{i}) of 𝔭^{b}). Since a ≤ b, we have 𝔭^{b} ⊂ 𝔭^{a}, hence the matrix A^{−1}B which expresses the β_{i} in terms of the α_{i} has integer coefficients. If we apply the Smith normal form algorithm to this matrix, we will find unimodular matrices U and V such that UA^{−1}BV = D_{C} is a diagonal matrix in Smith normal form. If (c_{i}) are the diagonal entries of D_{C} and if we set C = AU^{−1}, then the columns of C give the coordinates on the chosen integral basis of elements γ_{i} ∈ 𝔭^{a}, and we have 𝔭^{a}/𝔭^{b} = ⨁(ℤ/c_{i}ℤ)\overline{γ_{i}}, where \overline{γ} denotes the class of γ modulo 𝔭^{b}. If in addition b ≤ 2a, it follows from Proposition 2.5 that

(1 + 𝔭^{a})/(1 + 𝔭^{b}) = ⨁(ℤ/c_{i}ℤ)\overline{(1 + γ_{i})} .

Note that the above is simply a rephrasing of the method explained in §1.1.

We can now give formal algorithms for computing (ℤ_{K}/𝔭^{k})^{∗}. We start by a basic subalgorithm corresponding to Proposition 2.5.

Algorithm 2.6 (Computation of (1 + 𝔭^{a})/(1 + 𝔭^{b}). ) Let K be a number field, 𝔭 a prime ideal given by a two-element representation, and let a and b be two positive integers such that a ≤ b ≤ 2a. This algorithm computes integers c_{a,i} and elements γ_{a,i} ∈ 𝔭^{a} such that (1+𝔭^{a})/(1+𝔭^{b}) = ⨁(ℤ/c_{a,i}ℤ)\overline{(1 + γ_{a,i})} and c_{a,i+1} | c_{a,i}. In addition it outputs an additional matrix U_{a} which will be needed in later algorithms.

1. [Compute HNF matrices] By using the method explained above, compute the Hermite normal forms A and B of 𝔭^{a} and 𝔭^{b} respectively.

2. [Apply Smith] Apply the Smith normal form algorithm to the integer matrix A^{−1}B, thus obtaining unimodular matrices U and V such that UA^{−1}BV = C is a diagonal matrix in Smith normal form.

3. [Terminate] Let c_{a,i} be the diagonal entries of C. For each i, let γ_{a,i} be the element of ℤ_{K} (in fact of 𝔭^{a}) whose coefficients on the given integral basis is the i-th column of the matrix AU^{−1}. Output (1+𝔭^{a})/(1+𝔭^{b}) = ⨁(ℤ/c_{a,i}ℤ)\overline{(1 + γ_{a,i})}, and for future use set U_{a} ← UA^{−1}, output the matrix U_{a} and terminate the algorithm.

Note that we could clean up the trivial components as is done at the end of Algorithm 1.3. However, since this is essentially going to be used only as a subalgorithm of the complete algorithm for computing (ℤ_{K}/𝔪)^{∗}, we will do the cleaning up at the very end.

The corresponding discrete logarithm problem is essentially trivial. Indeed, since a ≤ 2b, Proposition 2.5 tells us that

∏(1 + γ_{a,i})^{x_{i}} ≡ 1 + ∑ x_{i}γ_{a,i} (mod 1 + 𝔭^{b}) .

Hence if \overline{β} ∈ (1 + 𝔭^{a})/(1 + 𝔭^{b}), we want to solve ∑ x_{i}γ_{a,i} = β − 1, or in matrix terms on the integral basis, AU^{−1}X = B − 1_{K}, where B is the column vector representing β on the integral basis, and 1_{K} is the column vector representing 1 (i.e. (1, 0, …, 0)^{t} since we choose an integral basis starting with 1). It follows that X = UA^{−1} = U_{a}(B − 1_{K}) is the desired discrete logarithm, and this is the reason we have kept the matrix U_{a}. Thus, the second basic subalgorithm that we need is the following.

Algorithm 2.7 (Discrete logarithm in (1 + 𝔭)/(1 + 𝔭^{k})). Let K be a number field, 𝔭 a prime ideal and k an integer, which we can assume greater or equal to 2, otherwise the problem is trivial. For each a ≥ 1 such that 2^{a} ≤ k we assume computed the c_{a,i}, γ_{a,i} and U_{a} corresponding to b = min(2a, k) by Algorithm 2.6. Finally, let β ∈ (1 + 𝔭), where β is given by a column vector B on the integral basis. This algorithm computes the discrete logarithm of \overline{β} in (1 + 𝔭)/(1 + 𝔭^{k}), i.e. integers y_{a,i} such that \overline{β} = \overline{∏_{a,i}(1 + γ_{a,i})^{y_{a,i}}} in (1 + 𝔭)/(1 + 𝔭^{k}) (Note that the γ_{a,i} and c_{a,i} do not give a Smith basis of (1 + 𝔭)/(1 + 𝔭^{k}), but this is not necessary. In addition, note that a will always be a power of 2.) As above, we let 1_{K} denote the column vector representing 1.

1. [Initialize] Set a ← 1.

2. [Main step] Set Z ← U_{a}(B − 1_{K}). If Z = (z_{i}), for each i set y_{a,i} ← −((−z_{i}) mod c_{a,i}) where we choose the smallest nonnegative residue of −z_{i}. Finally, set β ← β ∏_{i}(1+γ_{a,i}^{−y_{a,i}}). Note that this product can and should be reduced modulo 𝔭^{k} (see §3), and that the exponents are nonnegative.

3. [Loop and terminate] Set a ← 2a. If a < k, let B be the column vector whose entries are the coefficients of β on the integral basis, and go to step 2. Otherwise terminate the algorithm.

There is a little trick in the main step of this algorithm. We could have simply set y_{a,i} ← z_{i} mod c_{i}. However, we would then have to set β ← β/ ∏_{i}(1 + γ_{a,i}^{y_{a,i}}) mod 𝔭^{k}, and although division modulo an ideal is not too difficult, it is slower than multiplication, hence we have preferred to use the above trick (see §3).

We are now ready to give the algorithm for computing (ℤ_{K}/𝔭^{k})^{∗}.

Algorithm 2.8 (Computation of (ℤ_{K}/𝔭^{k})^{∗}). Let K be a number field, 𝔭 a prime ideal above p and of degree f of ℤ_{K} given by a two-element representation, and let k be a positive integer.

This algorithm computes integers d_{i} and elements δ_{i} of ℤ_{K} such that (ℤ_{K}/𝔭^{k})^{∗} = ⨁(ℤ/d_{i}ℤ)\overline{δ_{i}} with d_{i+1} | d_{i}. It also outputs a number of other quantities which will be needed in other algorithms.

1. [Initialize] If k = 1 go to step 4. Otherwise, set a ← 1 and b ← 2.

2. [Compute (1 + 𝔭^{a})/(1 + 𝔭^{b})] Using Algorithm 2.6, compute the quantities c_{a,i}, 1 + γ_{a,i} and U_{a} giving the structure of (1 + 𝔭^{a})/(1 + 𝔭^{b}). Call n_{a} the number of cyclic components c_{a,i} (or γ_{a,i}). For future use, output all these quantities.

3. [Loop] Set a ← 2a. If a < k, set b ← max(2b, k) and go to step 2.

4. [Prime to p part] Set q ← p^{f}. By choosing at random elements of ℤ_{K} − 𝔭, find g_{0} ∈ ℤ_{K} such that g_{0} mod 𝔭 is of order exactly q −1 in (ℤ_{K}/𝔭)^{∗} (so that the class of g_{0} is a generator of (ℤ_{K}/𝔭)^{∗}).

5. [Start computation of big matrix] Set c_{0,1} ← q − 1, γ_{0,1} ← g_{0} − 1, n_{0} ← 1. In the next step, we will compute a square h × h matrix H where h = ∑_{a≥0} n_{a}. It is very convenient to index the rows and columns of H by the pairs (a, i) as for the generators, and we will consider these pairs to be lexicographically ordered, so that (a, i) ≤ (b, j) if and only if a < b or a = b and i ≤ j.

6. [Compute big matrix H] For each pair (a, i), do the following. Set H_{a,i} ← V, where V = (v_{b,j}) is the column vector computed as follows. Set v_{b,j} ← 0 for (b, j) < (a, i), set v_{a,i} ← c_{a,i}. Let β ← (1 + γ_{a,i})^{c_{a,i}}. Using Algorithm 2.7, compute the discrete logarithm (y_{b,j}) of β (we will have y_{b,j} = 0 for (b, j) ≤ (a, i)). Finally, for (b, j) > (a, i) set v_{b,j} ← −y_{b,j}.

7. [Terminate] Let G be the row vector of the \overline{1 + γ_{a,i}} (here is modulo 𝔭^{k}), and let H be the matrix whose columns are the H_{a,i}. Apply Algorithm 1.3 to the system of generators and relations (G, H), output the SNF (P, D_{P}) and the auxilliary matrix U_{𝔭} = U_{a} obtained in that algorithm and terminate the algorithm.

The corresponding discrete logarithm problem has essentially been solved by Algorithm 2.7, but we give the algorithm anyway.

Algorithm 2.9 (Discrete logarithm in (ℤ_{K}/𝔭^{k})^{∗}). In addition to the data given in Algorithm 2.8, we are given an element β ∈ ℤ_{K} coprime to 𝔭^{k} (or equivalently to 𝔭). This algorithm computes the discrete logarithm of β with respect to the δ_{i} output by Algorithm 2.8.

1. [Compute discrete log modulo 𝔭] Using for example Shanks’s baby-step giant step method or a more sophisticated method, compute the discrete logarithm y_{0,1} of \overline{β} with respect to \overline{g_{0}} in (ℤ_{K}/𝔭)^{∗} (this may be the most time-consuming part of the algorithm if q = |ℤ_{K}/𝔭| is large). Then set β ← β/g_{0}^{y_{0,1}} mod 𝔭^{k}.

2. [Use Algorithm 2.7] (Here β ∈ (1 + 𝔭)). Compute the discrete logarithm (y_{a,i}) of β in (1 + 𝔭)/(1 + 𝔭^{k}) in the sense of Algorithm 2.7, and let Y = (y_{a,i}) be the column vector of the y_{a,i} (always in lexicographic order, and including y_{0,1}).

3. [Terminate] Using the matrix U_{𝔭} output in Algorithm 2.8 (whose columns are indexed by the pairs (a, i), but whose rows are indexed normally), compute X ← U_{𝔭}Y, output X, and terminate the algorithm.

Now, we deal with the general case. At the beginning of this section, we have considered the product of two coprime ideals. It is clear that if we apply the results of that section by induction, we obtain a similar results for a product of an arbitrary number of pairwise coprime ideals. There remains to see what to do with 𝔪_{∞}.

Call s the signature homomorphism from K^{∗} to 𝔽_{2}^{𝔪_{∞}} defined by

s(α) = (sign(v(α)))_{v∈𝔪_{∞}} .

Denote by 0 the zero vector in 𝔽_{2}^{𝔪_{∞}}. We will apply our exact sequence techniques to the split exact sequence

0 ⟶ 𝔽_{2}^{𝔪_{∞}} ⟶ (ℤ_{K}/𝔪)^{∗} ⟶ (ℤ_{K}/𝔪_{0})^{∗} ⟶ 1 .

For 1 ≤ j ≤ |𝔪_{∞}|, set ϵ_{j} = (\overline{1}, e_{j}) ∈ (ℤ_{K}/𝔪)^{∗} where e_{j} denotes the j-th canonical basis element of 𝔽_{2}^{𝔪_{∞}}. The ϵ_{j} form a generating set for 𝔽_{2}^{𝔪_{∞}} and the matrix of relations between them is clearly equal to twice the identity matrix of order k = |𝔪_{∞}|. If (C, D_{C}) are generators and relations for (ℤ_{K}/𝔪_{0})^{∗} with C = (\overline{γ_{i}}), we lift the \overline{γ_{i}} to γ′_{i} = (\overline{γ_{i}}, 0) (this is the reason the sequence is split). The γ′_{i} together with the ϵ_{j} form a generating set

for (ℤ_{K}/𝔪)^{∗} whose relation matrix is equal to ( \begin{matrix}D_{C} & 0 \\ 0 & 2I_{k} \end{matrix} ) and we conclude by a Smith

normal form computation as usual.

Combining all this with the methods of §1.1, 1.3, and 2, we obtain the following algorithm for computing (ℤ_{K}/𝔪)^{∗}.

Algorithm 2.10 (Computation of (ℤ_{K}/𝔪)^{∗}). Given a modulus 𝔪 = 𝔪_{0}𝔪_{∞}, this algorithm computes the SNF (ℤ_{K}/𝔪)^{∗} = (Z, D_{Z}). The entries ζ_{i} of Z will be represented as pairs (\overline{γ_{i}}, v_{i}) where \overline{γ_{i}} denotes the class modulo 𝔪_{0} of an element coprime to 𝔪_{0} and v_{i} ∈ 𝔽_{2}^{𝔪_{∞}}. The algorithm also outputs some additional information necessary for the discrete logarithm problem.

1. [Factor 𝔪_{0}] Using ideal factorization techniques (see for example [Coh]), find distinct prime ideals 𝔭 and exponents k_{𝔭} such that 𝔪_{0} = ∏_{𝔭} 𝔭^{k_{𝔭}}.

2. [Compute the (ℤ_{K}/𝔭^{k_{𝔭}})^{∗}] For each 𝔭 dividing 𝔪_{0}, apply Algorithm 2.8, thus finding integers d_{𝔭,i} and elements δ_{𝔭,i} of ℤ_{K} coprime to 𝔭 such that (ℤ_{K}/𝔭^{k_{𝔭}})^{∗} = ⨁_{i}(ℤ/d_{𝔭,i}ℤ)\overline{δ_{𝔭,i}}, and let n_{𝔭} be the number of cyclic components in this sum. Output for future use the auxilliary matrix U_{𝔭} also output by this algorithm.

3. [Modify generators] For each 𝔭 dividing 𝔪_{0} do the following. Using Lemma 2.2 applied to 𝔞 = 𝔭^{k_{𝔭}} and 𝔠 = 𝔪_{0}/𝔞, compute elements a_{𝔭} ∈ 𝔞 and c_{𝔭} ∈ 𝔠 such that a_{𝔭} + c_{𝔭} = 1. Then for all i, set ϵ_{𝔭,i} ← (\overline{c_{𝔭}δ_{𝔭,i} + a_{𝔭}}, 0) ∈ (ℤ_{K}/𝔪)^{∗} (these generators are indeed coprime to 𝔪_{0}, and they are still congruent to the initial δ_{𝔭,i} modulo 𝔭^{k_{𝔭}}).

4. [Deal with 𝔪_{∞}] Set n_{∞} ← |𝔪_{∞}|, and for i = 1 to i = n_{∞} set d_{∞,i} ← 2 and ϵ_{∞,i} ← (\overline{1}, e_{j}) where e_{j} is the j-th canonical basis vector of 𝔽_{2}^{𝔪_{∞}}.

5. [Compute big matrix H] Let S be the set formed by all prime ideals dividing 𝔪_{0} and the symbol ∞. In this step, we will compute a square h × h matrix H where h = ∑_{𝔭∈S} n_{𝔭}. It is convenient to index the rows and columns of H by the pairs (𝔭, i) as for the generators. Then we set H_{(𝔭,i),(𝔮,j)} ← 0 if (𝔮, j) ≠ (𝔭, i), H_{(𝔭,i),(𝔭,i)} ← d_{𝔭,i} otherwise.

6. [Terminate] Let G be the row vector of the ϵ_{𝔭,i}, and let H be the matrix whose columns are the H_{𝔭,i}. Apply Algorithm 1.3 to the system of generators and relations (G, H), output the SNF (Z, D_{Z}) and the auxilliary matrix U_{a} obtained in that algorithm and terminate the algorithm.

It will be useful to compute discrete logarithms for elements of K^{∗} coprime to 𝔪 which are not necessarily in ℤ_{K}. For this, we need the following subalgorithm.

Algorithm 2.11. Given a nonzero integral ideal 𝔞 and an element β of K^{∗} coprime to 𝔞, this algorithm computes elements α and γ of ℤ_{K} coprime to 𝔞 such that β = α/γ. We assume β given by its components on an integral basis of K.

1. [Trivial case] Let d be the lowest common multiple of the denominators of the components of β. If d = 1, then β is already in ℤ_{K}, hence set γ ← 1, α ← β and terminate the algorithm.

2. [Compute exponent] Let 𝔞 = ∏_{𝔭} 𝔭^{k_{𝔭}} be the prime ideal decomposition of 𝔞. Denote by e(𝔭) the ramification index of 𝔭. Compute k ← sup_{𝔭}⌊v_{p}(d)e(𝔭)/k_{𝔭}⌋+1, where v_{p}(d) denotes the ordinary exponent of p in d, where p is the prime number below 𝔭.

3. [Compute 𝔡^{−1}] Using standard ideal operations, compute the ideal 𝔡 ← dℤ_{K} + 𝔞^{k} and the inverse ideal 𝔡^{−1}.

4. [Terminate] (Here d𝔡^{−1} and 𝔞𝔡^{−1} are coprime integral ideals.) Using the algorithm explained in Lemma 2.2, compute a and c such that a ∈ d𝔡^{−1}, c ∈ 𝔞𝔡^{−1} and a + c = 1. Set γ ← a, α ← aβ and terminate the algorithm.

We leave to the reader the (easy) proof of the validity of this algorithm. Note that steps 3 and 4 follow from the ideas explained in [Coh2]. ⊓ ⊔

The discrete logarithm problem in (ℤ_{K}/𝔪)^{∗}, but applied to elements of K^{∗} coprime to 𝔪, is then as follows.

Algorithm 2.12 (Discrete logarithm in (ℤ_{K}/𝔪)^{∗}). Given a modulus 𝔪 = 𝔪_{0}𝔪_{∞}, the structure (ℤ_{K}/𝔪)^{∗} = ⨁_{i} (ℤ/z_{i}ℤ)ζ_{i} found by Algorithm 2.10, and an element β of K^{∗} coprime to 𝔪, this algorithm computes the discrete logarithm of β with respect to the ζ_{i}. We assume β given by its coordinates on a fixed integral basis. We let 𝔪_{0} = ∏_{𝔭} 𝔭^{k_{𝔭}} and, as in Algorithm 2.10, S is the set of prime ideals dividing 𝔪_{0} union the symbol ∞.

1. [Check if integral] If β ∈ ℤ_{K} (i.e. if its coordinates on the integral basis are all integers), go to step 2. Otherwise, using Algorithm 2.11, compute α and γ in ℤ_{K} coprime to 𝔪 such that β = α/γ. Let L_{α} (resp. L_{γ}) be the discrete logarithm of α (resp. γ) obtained by applying the present algorithm. Output L_{α} − L_{γ} (where each coordinate can be reduced modulo the respective z_{i}), and terminate the algorithm.

2. [Compute modulo 𝔭^{k_{𝔭}}] (Here β ∈ ℤ_{K}). Using Algorithm 2.9, compute the discrete logarithm (x_{𝔭,i}) of β in (ℤ_{K}/𝔭^{k_{𝔭}})^{∗}. Compute the vector V = (\overline{v_{i}}) of the signature of β, and for 1 ≤ i ≤ |𝔪_{∞}| set x_{∞,i} ← v_{i}, where v_{i} is any lift of \overline{v_{i}} to ℤ (for example in \{0, 1\}). Finally, let X = (x_{𝔭,i}) be the column vector indexed by the pairs (𝔭, i) for 𝔭 ∈ S.

3. [Terminate] Set W ← U_{a}X, where U_{a} is the matrix output in step 7 of Algorithm 2.10. Reduce each component w_{j} of W modulo the corresponding z_{j} (for example in the interval [0, z_{j} − 1], output W and terminate the algorithm.

This terminates the algorithmic computation of the group (ℤ_{K}/𝔪)^{∗}.

3. Computing ray class groups

Let 𝔪 be a modulus. Recall the exact sequence

U(K) ⟶ (ℤ_{K}/𝔪)^{∗} ⟶ Cl_{𝔪} ⟶ Cl(K) ⟶ 1 ,

where U(K) denotes the unit group of K, Cl(K) the ordinary class group of K, and Cl_{𝔪} = I_{𝔪}/P_{𝔪} the ray class group corresponding to the modulus 𝔪, i.e. the quotient of the group I_{𝔪} of nonzero fractional ideals of K coprime to 𝔪 by the subgroup P_{𝔪} of principal fractional ideals generated by an element α congruent to 1 mod ^{∗}𝔪. To apply the techniques that we have developped, the groups Cl(K) and U(K) must be known in the sense of Definition 1.4. This can be done using either the techniques of [Po-Za] or of [Coh]. Note that [Coh] assumes the GRH, but in fact in practical situations it is rather easy to remove the GRH condition by certifying the result inconditionally. We refer to [Zan] and [Di-Ol] for details. Note also that we need to solve the discrete logarithm problem in Cl(K) (in U(K) the problem is ordinary linear algebra). The solution to this is also given in [Coh], where in fact even more information is obtained as part of the principal ideal problem: if an ideal is principal, the algorithm also gives a generator. More precisely, if g_{i} are ideals such that \overline{g_{i}} are the given generators of Cl(K), then if g is an ideal of K, we can find (v_{i}) such that \overline{g} = ∏_{i} \overline{g_{i}}^{v_{i}}, but the same algorithm gives also α ∈ K such that g = α ∏_{i} g_{i}^{v_{i}}. We will also do this in the context of ray class groups.

The group (ℤ_{K}/𝔪)^{∗} has been extensively dealt with in §2.

Finally, we must show that the maps are known algorithmically in the sense of Definition 1.5. This is not completely trivial. First, consider the map ψ from (ℤ_{K}/𝔪)^{∗} to Cl_{𝔪}. Since Cl_{𝔪} is not yet known, to say that ψ is algorithmically defined means that if \overline{g} ∈ Cl_{𝔪} is of the form ψ(\overline{α}), we can find α ∈ ℤ_{K}. But g is then an ideal of K coprime to 𝔪 which is a principal ideal in the ordinary sense, hence, by using the solution of the principal ideal problem mentioned above, we can algorithmically find α such that g = αℤ_{K}. Since g is coprime to 𝔪, α will also be coprime to 𝔪. Using Algorithm 2.11, we can find β and γ such that α = β/γ and β and γ integral and coprime to 𝔪, hence we can take \overline{α} = \overline{β}/\overline{γ} in (ℤ_{K}/𝔪)^{∗}.

Consider now the map ϕ from Cl_{𝔪} to Cl(K). To say that ϕ is algorithmically defined, means that if \overline{g} ∈ Cl_{𝔪} we can compute ϕ(\overline{g}) ∈ Cl(K), which is of course trivial, but it also means that if \overline{g} ∈ Cl(K) = Im(ϕ) we can find an ideal g′ coprime to 𝔪 such that ϕ(\overline{g′}) = \overline{g}. This follows from the following lemma, whose theoretical version is well known.

Lemma 3.1. Given a fractional ideal g of K and a modulus 𝔪, we can algorithmically find α ∈ K^{∗} such that αg is an integral ideal coprime to 𝔪.

We refer to [Coh2] for one method of doing this using the approximation theorem in Dedekind domains, but also mention that the factor refinement method is better (cf. [B-D-S]).

We can now put everything together. We consider the above ray class group exact sequence as a four term exact sequence as in §1.4, and we thus obtain the following algorithm for computing the ray class group Cl_{𝔪}.

Algorithm 3.2 (Computing ray class groups). Let 𝔪 = 𝔪_{0}𝔪_{∞} be a modulus. This algorithm computes ideals b_{i} coprime to 𝔪 such that the SNF of Cl_{𝔪} is Cl_{𝔪} = (\overline{B}, D_{B}) (where \overline{b_{i}} denotes the ideal class of b_{i} in Cl_{𝔪}). It also outputs some extra information necessary for the discrete logarithm problem. We assume already computed U(K) = (E, D_{E}) with E = (ϵ_{i}), Cl(K) = (C, D_{C}) with C = (γ_{i}) = (\overline{g_{i}}) (by [Po-Za] or [Coh]) and (ℤ_{K}/𝔪)^{∗} = (Z, D_{Z}) with Z = (ζ_{i}) (by Algorithm 2.10). We denote by ψ the map from (Z_{K}/𝔪)^{∗} to Cl_{𝔪}.

1. [Find new g_{i}] Using the approximation theorem or factor refinement, for each i compute α′_{i} ∈ K^{∗} such that g′_{i} = α′_{i}g_{i} is an integral ideal coprime to 𝔪. Let G′ be the row vector of the \overline{g′_{i}}, and A′ the row vector of the α′_{i}. For future use, output the elements α′_{i}.

2. [Find principal ideals] For each ideal g_{i}, compute g_{i}^{c_{i}} (where c_{i} is the i-th diagonal entry of D_{C}), and using the solution to the principal ideal problem (see [Coh]), find α_{i} ∈ ℤ_{K} such that g_{i}^{c_{i}} = α_{i}ℤ_{K}.

3. [Compute P] (Here the α′_{i}^{c_{i}}α_{i} are elements of ℤ_{K} coprime to 𝔪.) Using Algorithm 2.12, compute the matrix P whose columns are the discrete logarithms of the α′_{i}^{c_{i}}α_{i} with respect to the ζ_{i}.

4. [Compute Q] Using again Algorithm 2.12, compute the matrix Q whose columns are the discrete logarithms of the ϵ_{i} with respect to the ζ_{i} for 0 ≤ i ≤ r.

5. [Terminate] Let B′ ← (G′|ψ(Z)) and H ← ( \begin{matrix}D_{C} & 0 & 0 \\ −P & Q & D_{Z} \end{matrix} ). Applying Algorithm 1.3 to

the system of generators and relations (B′, H), let (\overline{B}, D_{B}) be the Smith normal form of Cl_{𝔪} thus obtained. If \overline{B} = (\overline{b_{i}}), let b_{i} be ideals coprime to 𝔪 belonging to the class \overline{b_{i}}. Output the b_{i}, D_{B}, the auxilliary matrix U_{a} output by Algorithm 1.3 and terminate the algorithm.

To end this section, we give the corresponding algorithm for solving the discrete logarithm problem in Cl_{𝔪}. As in the case of Cl(K) itself, we will in fact solve a stronger problem, the principal ideal problem in ray class groups.

Algorithm 3.3 (Principal ideal problem in ray class groups). Let 𝔪 be a modulus, and let Cl_{𝔪} = (\overline{B}, D_{B}) as computed by Algorithm 3.2. Given a fractional ideal h coprime to 𝔪, this algorithm computes a column vector V and an element β ∈ K such that h = βBV and β ≡ 1 (mod ^{∗}𝔪).

1. [Work in Cl(K)] Applying the principal ideal problem in Cl(K), find a column vector W and γ ∈ K such that h = γGW (where G is the row vector of the ideals g_{i} whose classes are the given generators of Cl(K)).

2. [Work in (ℤ_{K}/𝔪)^{∗}] Set α ← γ/A′W where the A′ = (α′_{i}) is the row vector of elements computed in step 1 of Algorithm 3.2 (α will be coprime to 𝔪). Using Algorithm 2.12, compute Y such that α ≡ ZY (mod ^{∗}𝔪), and let α′ ← ZY as an element of (ℤ_{K}/𝔪)^{∗}.

3. [Terminate] Let R ← (\frac{W}{Y}). Output L ← U_{a}R, β ← α/α′ and terminate the algorithm.

This finally terminates the algorithmic computation of the ray class groups Cl_{𝔪}. It should be emphasized that although many algorithms and subalgorithms are involved, the basic computations are rather simple, and that the main bottlenecks will be in two places. First the computation of discrete logarithms in (ℤ_{K}/𝔭)^{∗}. For this, considering the vast amount of effort which has been spent on the problem, we have nothing more to say.

The second bottleneck will be the size of the generators. Indeed, several times we have to multiply a given set of generators by a unimodular matrix U^{−1}, or multiply generators by elements to make them coprime to certain ideals. All this makes the coefficients of the generators grow in size. Since this can rapidly make the algorithms completely useless in practice, we should like to give a few brief indications on how to get down to generators of manageable size.

The main place where size reduction is necessary is in Algorithm 1.3, i.e. in the SNF algorithm for Abelian groups. Recall that in that algorithm, a set of generators and relations (G, M) is given, and after reducing M to its HNF, which is a harmless process, we use the SNF algorithm to compute unimodular matrices U and V such that H = UDV (and afterwards we remove trivial components). The main problem comes from the fact that the new generators are given essentially by GU^{−1}, and these may be large objects if U^{−1} has large coefficients.

There are several complementary ways to improve this situation, and all should be applied.

(1) The matrix U^{−1} is not unique in general, hence it is worthwhile to find a small such matrix. This can be done using the techniques of [Ha-Ma].

However, in most cases, this just cannot be done, and all possible matrices U^{−1} have large coefficients.

(2) Another idea is to observe that GM = 1 in the Abelian group, hence if we add to the columns of U^{−1} any ℤ-linear combination of the columns of M (or of H), the resulting generators GU^{−1} are unchanged. For doing this reduction, the simplest is probably as follows. Let X be a column vector that we want to reduce modulo the columns of H. Compute first the matrix L obtained from H by applying the LLL algorithm to the columns of H. Then replace X by X −L⌊L^{−1}X⌉, where as usual ⌊x⌉ means rounding to the nearest integer coefficient per coefficient. This should now be rather small.

(3) We should try to avoid divisions as much as possible. For this, instead of computing a product of the form ∏_{i} g_{i}^{u_{i}} in the naive way, we write

∏_{i} g_{i}^{u_{i}} = ∏_{i, u_{i}>0} g_{i}^{u_{i}}/ ∏_{i, u_{i}<0} g_{i}^{−u_{i}}

so that we need to perform only one division. Note that division is in general an expensive operation.

(4) In the (very frequent) case where the group consists of classes of elements of a set modulo some equivalence relation, the elements of the group are usually given by the classes of some representatives, but the latter should be chosen with care. In other words, one should try to reduce modulo the equivalence relation as much as possible.

Let us look in detail at the two cases of importance to us, that of (ℤ_{K}/𝔪)^{∗} and that of Cl_{𝔪}.

(4.1) Recall that elements of (ℤ_{K}/𝔪)^{∗} are represented by pairs (\overline{α}, v) with α ∈ ℤ_{K} coprime to 𝔪_{0} and v ∈ 𝔽_{2}^{𝔪_{∞}}. To reduce such a pair, we consider α represented by a column vector X on a fixed integral basis. As in (2), we compute an LLL-reduced basis L of the ideal 𝔪_{0}, and set Y ← X − L⌊L^{−1}X⌉. This will be a reasonably small vector giving an element β congruent to α modulo 𝔪_{0}. We can then replace (\overline{α}, v) by (\overline{β}, v). Note that this is where the two-element representation is the most useful since we do not have to worry about the signature of β.

(4.2) To reduce an ideal modulo 𝔪 (so that we stay in the same ideal class in Cl_{𝔪}), we proceed as follows. First, exactly as in the case of (ℤ_{K}/𝔪)^{∗}, instead of representing ideal classes as such, i.e. as classes of ideals coprime to 𝔪_{0} modulo P_{𝔪}, we will represent them as pairs (𝔞, v) where 𝔞 ∈ I_{𝔪_{0}} is an ideal coprime to 𝔪_{0} and v ∈ 𝔽_{2}^{∞} as usual. The equivalence relation R on these pairs is defined by (𝔞′, v′)R(𝔞, v) if and only if there exists β ≡ 1 (mod ^{∗}𝔪_{0}) such that v′ = v + s(β). As in the case of (ℤ_{K}/𝔪)^{∗} this representation will avoid annoying problems due to signatures.

We will use the following basic algorithm.

Algorithm 3.4 Let 𝔞 and 𝔟 be coprime integral ideals. This algorithm computes an element γ ∈ 𝔞 such that γ ≡ 1 (mod 𝔟) and 𝔞/γ an LLL-reduced ideal, in the sense of [Coh, p. 347].

1. [LLL-reduce] Let α be the first element of an LLL-reduced basis of the ideal 𝔞𝔟 for the quadratic form ∑ |σ_{i}(α)|^{2} (see step 2 of [Coh, Algorithm 6.5.5]).

2. [Use Lemma 2.2] Using the algorithm described in the proof of Lemma 2.2, compute a ∈ 𝔞 and b ∈ 𝔟 such that a + b = 1.

3. [Terminate] Compute the element a′ ← a/α, and let q be the element obtained by rounding to the nearest integer the coefficients of α′ on the integral basis. Set γ ← a − qα. If γ = 0 (which can happen only if 𝔟 = ℤ_{K}), set γ ← α. Output γ and terminate the algorithm.

Using this algorithm, we can now write the algorithm for reducing modulo a modulus.

Algorithm 3.5 (Reduction of an ideal modulo a modulus). Given a modulus 𝔪 = 𝔪_{0}𝔪_{∞} and an element of (ℤ_{K}/𝔪)^{∗} represented by a pair (𝔞, v) as above, this algorithm computes another representative (α′, v′) of the same class in Cl_{𝔪} such that 𝔞′ is an “almost reduced” integral ideal.

1. [Use Algorithm 3.4] Using Algorithm 3.4 applied to 𝔞 and 𝔟 = 𝔪_{0}, compute γ ∈ 𝔞 such that γ ≡ 1 (mod 𝔪_{0}) and 𝔞/γ an LLL-reduced ideal.

2. [Use Algorithm 3.4 again] Using again Algorithm 3.4, but this time applied to γ/𝔞 and 𝔪_{0} (which are integral coprime ideals), compute δ ∈ γ/𝔞 such that δ ≡ 1 (mod 𝔪_{0}) and (γ/𝔞)/δ an LLL-reduced ideal. Set α ← δ/γ.

4. [Terminate] Set 𝔞′ ← α𝔞, v′ ← v + s(α), output the pair (𝔞′, v′) and terminate the algorithm.

The proof of the validity of these algorithms is trivial and left to the reader.

4. Computations in global class field theory

4.1. Algorithmic description of congruence groups

Congruence groups are subgroups of I_{𝔪} containing P_{𝔪}. They naturally correspond to subgroups of Cl_{𝔪}. We assume that Cl_{𝔪} has been computed, so that as usual

Cl_{𝔪} = ⨁_{i=1}^{n}(ℤ/c_{i}ℤ)\overline{γ_{i}} .

We have the following result.

Proposition 4.1. Let c_{i} and γ_{i} be as above, let D_{C} be the diagonal matrix of the c_{i}, and C the row matrix of the \overline{γ_{i}}. There is a one to one correspondence between congruence groups modulo 𝔪 and integral matrices A in Hermite normal form satisfying A^{−1}D_{C} ∈ M_{n}(ℤ). The correspondence is as follows.

(1) If A is such a matrix, we set C′ = CA in the multiplicative sense already used in the preceding sections. Then if C′ = (\overline{γ′_{i}}), the congruence subgroup H associated to A is the subgroup of I_{𝔪} generated by the γ′_{i} and by P_{𝔪}.

(2) Conversely, if H is a congruence subgroup, let (\overline{γ′_{i}})_{1≤i≤m} be a system of generators of H/P_{𝔪}, and let C′ be the row vector of the \overline{γ′_{i}}. We can write C′ = CP for an n × m matrix P. Then A is the Hermite normal form of the matrix (P |D_{C}).

(3) Let A be a matrix in HNF, and let H be the corresponding congruence group. Then |H/P_{𝔪}| = |Cl_{𝔪}|/ det(A) or equivalently, if \overline{H} = H/P_{𝔪}, then

h_{𝔪,H} = |Cl_{𝔪}/\overline{H}| = |I_{𝔪}/H| = det(A) .

Proof. We have Cl_{𝔪} ≃ ℤ^{n}/Λ, where Λ is the lattice Λ = ⨁ c_{i}ℤ, so that a ℤ-basis of Λ is (c_{i}ϵ_{i})_{1≤i≤n}, where the ϵ_{i} are the canonical basis elements of ℤ^{n}. The isomorphism is given explicitly by sending the i-th generator \overline{γ_{i}} of Cl_{𝔪} on ϵ_{i}. Subgroups of ℤ^{n}/Λ are of the form Λ′/Λ, where Λ′ is a lattice such that Λ ⊂ Λ′ ⊂ ℤ^{n}. Such a lattice Λ′ can be defined in a unique way by a matrix A in Hermite normal form so that the columns of this matrix express a ℤ-basis of Λ′ on the ϵ_{i}. The condition Λ′ ⊂ ℤ^{n} means that A has integer entries, and the condition Λ ⊂ Λ′ means that A^{−1}D also has integer entries, since it is the matrix which expresses the given basis of Λ in terms of that of Λ′. In terms of generators, this correspondence translates into the equality C′ = CA of (1).

For (2), we note that CD_{C} = 1, hence if C′′ = C(P |D_{C}) we have simply added some 1’s to the generators of H/P_{𝔪}. Thus, the group can be defined by the matrix of maximal rank (P |D_{C}), hence also by the Hermite normal form A of this matrix.

For (3), we know that A^{−1}D_{C} expresses a basis of Λ in terms of a basis of Λ′, hence

|H/P_{𝔪}| = |Λ′/Λ| = det(A^{−1}D_{C}) = |Cl_{𝔪}|/ det(A) .

⊓ ⊔

Thus, finding all congruence groups modulo 𝔪 is equivalent to finding integral HNF matrices A such that A^{−1}D_{C} also has integer entries. Note that there exist only a finite number of such matrices A, in fact exactly the number of subgroups of Cl_{𝔪} or equivalently of ⨁(ℤ/c_{i}ℤ). It is natural to call these matrices the left divisors of the matrix D_{C}.

The question of finding these divisors in an efficient manner does not seem to be easy. However, by the Cohen-Lenstra heuristics generalized to this case, it seems reasonable to assume that Cl_{𝔪} will often be cyclic or close to cyclic. Hence, we can proceed as follows. Let n be the number of cyclic components of Cl_{𝔪} as above.

If n = 1, A divides D_{C} if and only if A = (e_{1}) where e_{1} | d_{1} and e_{1} ≥ 1, hence we simply look at all (positive) divisors of d_{1}.

If n = 2 then an immediate computation shows that A = ( \begin{matrix}e_{1} & f_{1} \\ 0 & e_{2} \end{matrix} ) divides D_{C} if and

only if for i = 1 and i = 2, e_{i} is a positive divisor of d_{i}, and f_{1} = ke_{1}/ gcd(e_{1}, d_{2}/e_{2}) with 0 ≤ k < gcd(e_{1}, d_{2}/e_{2}).

If n = 3, we can write an explicit but much more complicated recipe for the coefficients of A, but for general n, it does not seem to be possible. Thus for n ≥ 3, there does not seem to be any better solution than to try all possible HNF matrices A = (a_{i,j}) with a_{i,i} | d_{i} and

a_{i,i+1} ≡ 0 (mod a_{i,i}/ gcd(a_{i,i}, d_{i+1}/a_{i+1,i+1})) ,

which are easily seen to be necessary conditions.

Finally, we consider the question of computing the image of a subgroup of Cl_{𝔪} by a surjective group homomorphism. The following algorithm, given in an abstract situation which does not necessarily refer to ray class groups, answers this question immediately.

Algorithm 4.2 (Image of a subgroup). Let B = (B, D_{B}) and C = (C, D_{C}) be two finite Abelian groups written in Smith normal form, let ϕ be a group homomorphism from B to C, and finally let H be a subgroup of B defined by an HNF matrix A_{B} dividing D_{B}. This algorithm computes the HNF matrix A_{C} dividing D_{C} which defines the subgroup ϕ(H) of C. 1.[Compute matrix P] Using the discrete logarithm problem in C, compute a matrix P such

that ϕ(B) = CP. 2.[Apply Hermite] Let A_{C} be the Hermite normal form of the matrix (P A_{B}|D_{C}). Output A_{C} and terminate the algorithm.

Proof. The generators of H are by definition the entries of BA_{B}. Hence the generators of ϕ(H) are the entries of ϕ(B)A_{B} = CP A_{B}. Since CD_{C} = 1, it follows that the entries of C(P A_{B}|D_{C}) also generate ϕ(H). But the advantage of this last matrix is that it is of maximal rank (since D_{C} is), hence if A_{C} is its HNF, then CA_{C} generates ϕ(H) and A_{C} is an integral matrix in HNF. Furthermore, since it is obtained as the “matrix GCD” of P A_{B} and D_{C}, it divides D_{C}. Explicitly, let U be the unimodular matrix such

that (P A_{B}|D_{C})U = (0|A_{C}). Write in block matrix form, U^{−1} = ( \begin{matrix}U_{1} & U_{2} \\ U_{3} & U_{4} \end{matrix} ). Then

(P A_{B}|D_{C}) = (0|A_{C})U^{−1} from which it follows in particular that A_{C}U_{4} = D_{C}, hence A_{C}^{−1}D_{C} = U_{4} has indeed integral coefficients. ⊓ ⊔

4.2. Computing discriminants, signatures and conductors

Let us now come back to the ray class field situation. Let K be a number field (our base field), let 𝔪 be a modulus, Cl_{𝔪} the ray class group, and N the ray class field corresponding to Cl_{𝔪}. In particular, we have Gal(N/K) ≃ Cl_{𝔪}.

For any congruence group H modulo 𝔪, denote by \overline{H} = H/P_{𝔪} the subgroup of Cl_{𝔪} corresponding to H. We will often identify H and \overline{H}.

By Galois theory, subfields L of N are in one to one correspondence with congruence groups H modulo 𝔪 by the maps H ↦ L = N\overline{H} and L ↦ Gal(N/L). We also have Gal(L/K) ≃ Cl_{𝔪}/\overline{H}.

Our goal in this section is to compute the signature, relative discriminant and conductor of these subfields L. The result is as follows.

Théorème 4.3. Let K be a number field. Set n = [K : ℚ], let (r_{1}, r_{2}) be the signature of K, so that r_{1} + 2r_{2} = n, and let d_{K/ℚ} be its discriminant. For any modulus 𝔫 dividing 𝔪, denote by s_{𝔫} the canonical surjection from Cl_{𝔪} to Cl_{𝔫}, and set

h_{𝔫,H} = |Cl_{𝔫}/s_{𝔫}(\overline{H})| .

Let 𝔪 = ∏_{i} 𝔭_{i}^{e_{i}}𝔪_{∞} be the prime decomposition of 𝔪.

Then, if L is the extension of K corresponding to the congruence group (𝔪, H), we have the following results.

(1) Let δ_{L/K} be the relative discriminant of L/K. Then:

δ_{L/K} = ∏_{i} 𝔭_{i}^{e_{i}h_{𝔪,H}−∑_{1≤k≤e_{i}} h_{𝔪/𝔭^{k}_{i},H}} .

(Recall also that we have |d_{L/ℚ}| = N_{K/ℚ}(δ_{L/K})|d_{K/ℚ}|^{h_{𝔪,H}}.)

(2) The modulus 𝔪 is the conductor of L if and only if h_{𝔪/𝔭,H} < h_{𝔪,H} for all 𝔭 | 𝔪, including the places at infinity.

(3) Let (R_{1}, R_{2}) be the signature of L, so that R_{1} + 2R_{2} = [L : ℚ] = n · h_{𝔪,H}. Then we have

R_{1} = h_{𝔪,H} (r_{1} − |𝔪_{∞}| + ∑_{v∈𝔪_{∞}} δ(h_{𝔪,H} − h_{𝔪/v,H})) ,

where δ(x) = 1 if x = 0 and δ(x) = 0 otherwise.

Proof. For (1), we know that

δ_{L/K} = ∏_{χ} F(χ) ,

where χ runs through all the characters of Cl_{𝔪}/\overline{H} and F(χ) is the conductor of χ.

For each 𝔫 | 𝔪, denote by f(𝔫) the number of characters of Cl_{𝔪}/\overline{H} of conductor exactly equal to 𝔫. Then since the total number of characters is equal to the order of the group, we have the equation

∑_{𝔫|𝔪} f(𝔫) = |Cl_{𝔪}/\overline{H}| = h_{𝔪,H} .

By Möbius inversion, it follows that

f(𝔫) = ∑_{𝔫|𝔪} μ(𝔪/𝔫)h_{n,H} ,

where μ(𝔫) is defined as in the case of ordinary integers (all this is valid since a modulus can be written as a product of finite or infinite primes in essentially only one way).

Thus, we have

δ_{L/K} = ∏_{𝔫|𝔪} ∏_{F(χ)=𝔫} F(χ) = ∏_{𝔫|𝔪}𝔫^{f(𝔫)} = ∏_{𝔫|𝔪}𝔫^{∑_{𝔡|𝔫}μ(𝔫/𝔡)h_{𝔡,H}}

= ∏_{𝔡|𝔪} ( ∏_{𝔠|(𝔪/𝔡)}(𝔠𝔡)^{μ(𝔠)})^{h_{𝔡,H}} = ∏_{𝔡|𝔪}(p_{1}(𝔡)p_{2}(𝔡))^{h_{𝔡,H}} ,

where

p_{1}(𝔡) = ∏_{𝔠|(𝔪/𝔡)}𝔠^{μ(𝔠)} and p_{2}(𝔡) = ∏_{𝔠|(𝔪/𝔡)}𝔡^{μ(𝔠)} .

The product p_{2}(𝔡) is trivial: we have

p_{2}(𝔡) = 𝔡^{∑_{𝔠|(𝔪/𝔡)}μ(𝔠)} ,

and by definition of the μ function, this exponent is equal to zero unless 𝔪/𝔡 = 1. Hence p_{2}(𝔡) = 1 if 𝔡 ≠ 𝔪, and p_{2}(𝔪) = 𝔪.

The product p_{1}(𝔡) can be treated as follows. Set L(𝔠) = 𝔭 if 𝔠 = 𝔭^{k} is a nontrivial prime power (finite or infinite), L(𝔠) = 1 otherwise. Then ∏_{𝔠|𝔫} L(𝔠) = 𝔫 is a formal equality which only expresses the existence and uniqueness of the decomposition of 𝔫 into prime powers. By multiplicative Möbius inversion, this gives

L(𝔫) = ∏_{𝔠|𝔫}(𝔫/𝔠)^{μ(𝔠)} = ∏_{𝔠|𝔫} 𝔫^{μ(𝔠)}/ ∏_{𝔠|𝔫} 𝔠^{μ(𝔠)} .

By definition of μ the numerator is equal to 1, hence we obtain the formula

∏_{𝔠|𝔫} 𝔠^{μ(𝔠)} = 1/L(𝔫) .

The reader will certainly have recognized that the function L(𝔫) is the ideal-theoretic analogue of the function e^{Λ(n)} of elementary prime number theory.

Replacing in our above formulas, we obtain that p_{1}(𝔡) = 1/L(𝔪/𝔡). Therefore,

δ_{L/K} = 𝔪^{h_{𝔪,H}} ∏_{𝔡|𝔪}L(𝔪/d)^{−h_{𝔡,H}} = 𝔪^{h_{𝔪,H}} ∏_{𝔭^{k}|𝔪}𝔭^{−h_{𝔪/𝔭^{k},H}}

= ∏_{i} 𝔭_{i}^{e_{i}h_{𝔪,H}−∑_{1≤k≤e_{i}} h_{𝔪/𝔭^{k}_{i},H}} ,

thus proving (1).

(2) is simply a restatement of the definition of the conductor of an Abelian extension. For (3), we note that R_{1} will be equal to [L : K] = h_{𝔪,H} times the number of real places

of K unramified in L. By definition of the ray class group, the r_{1} − |𝔪_{∞}| real places not in the modulus 𝔪 must be unramified. Now let v ∈ 𝔪_{∞}. If h_{𝔪/v,H} = h_{𝔪,H}, this means that v does not divide the conductor of L, hence that v is unramified in L. On the contrary, if h_{𝔪/v,H} < h_{𝔪,H} then v divides the conductor of L hence v is ramified in L. This gives the formula in (3). ⊓ ⊔

In is not necessary to give a formal algorithm for computing relative or absolute discriminants, signatures and conductors, since everything is contained in Algorithm 4.2 and Théorème 4.3. To compute the conductor, we recall simply that we replace 𝔪 inductively by 𝔪/𝔭 for some (finite or infinite) place 𝔭 dividing 𝔪, until there does not exist 𝔭 | 𝔪 such that h_{𝔪/𝔭,H} = h_{𝔪,H}.

4.3. Conductors of characters

The formulas given above (in particular in Théorème 4.3) have the great advantage that we do not need to compute the conductors of individual characters. In this subsection, we explain how to do this if these conductors are really needed.

Let

Cl_{𝔪}(K) = ⨁_{1≤i≤k}(ℤ/d_{i}ℤ)g_{i}

be the SNF of Cl_{𝔪}(K). Denote by ζ_{n} the specific primitive n-th root of unity exp(2iπ/n) and let ζ = ζ_{d_{1}} (recall that d_{i} divides d_{1} for all i). Then a character χ is uniquely defined by a vector (a_{1}, …, a_{k}) where a_{i} ∈ ℤ/d_{i}ℤ so that

χ(∏_{i} g_{i}^{x_{i}}) = ∏_{i} ζ_{d_{i}}^{a_{i}x_{i}} = ζ^{∑_{i}(d_{1}/d_{i})a_{i}x_{i}} .

By definition, the conductor of χ is equal to the conductor of the congruence group H = Ker(χ). Since this is a congruence group, we can use the above methods to compute its conductor. The only problem is to put this group into an algorithmic form, i.e. to compute the corresponding matrix A associated to H by Proposition 4.1.

We have χ(∏_{i} g_{i}^{x_{i}}) = 1 if and only if there exists an integer y such that

∑_{i}(d_{1}/d_{i})a_{i}x_{i} + d_{1}y = 0 .

This is again an instance of the integer kernel problem. In the present case, it is solved as follows. Set b_{i} = (d_{1}/d_{i})a_{i}, and let B = [b_{1}, …, b_{k}, d_{1}] considered as a 1 row matrix. Using the Hermite normal form algorithm, we can compute a unimodular matrix U such that BU = [0, …, 0, d] for some d (equal to the GCD of the entries of B). Write in block matrix form

U = ( \begin{matrix}E & C \\ R & a \end{matrix} ) ,

where E is a k × k matrix (and C is a column matrix and R a row matrix). The column vectors X = (x_{i}) such that there exists a y satisfying our equality above are then exactly the ℤ-linear combinations of the columns of the matrix E. But this means exactly that the kernel of χ is defined by the matrix E, or if we want it in normalized form, by the HNF of E. We can then compute the conductor as usual.

Formally, this can be written as follows.

Algorithm 4.4 (Conductor of a character). Let Cl_{𝔪}(K) = ⨁_{1≤i≤k}(ℤ/d_{i}ℤ)g_{i} be the SNF of the ray class group Cl_{𝔪}(K), and let χ be a character defined by χ(∏_{i} g_{i}^{x_{i}}) = ∏_{i} ζ_{d_{i}}^{a_{i}x_{i}}. This algorithm computes the conductor of χ (which is a modulus of K).

1. [Apply Hermite] For all i let b_{i} ← (d_{1}/d_{i})a_{i}, and let B ← [b_{1}, …, b_{k}, d_{1}] considered as a 1-row matrix. Using the HNF algorithm, find a unimodular matrix U such that BU = [0, …, 0, d].

2. [Compute A] Let E be the upper left k × k submatrix of U, let A be the HNF of E (this step can in fact be omitted), and call H the corresponding congruence group.

3. [Compute conductor] For each finite or infinite place 𝔭 dividing 𝔪, proceed as follows. While 𝔭 | 𝔪 and h_{𝔪/𝔭,H} = h_{𝔪,H}, set 𝔪 ← 𝔪/𝔭 and H ← s(H) (s being the surjection from Cl_{𝔪}(K) to Cl_{𝔪/𝔭}(K)), where s(H) is computed using Algorithm 3.2.

4. [Terminate] Output 𝔪 and terminate the algorithm.

4.4. Computing defining equations

There seems to be two ways to compute the defining equations of the number fields L defined by a congruence group (𝔪, H). One is by Kummer theory. We refer to work of Pohst and collaborators ([Da-Po]) for details on this. The other method, which works only in certain cases, is the use of Stark units. This is the subject of active research.

In this section, we would like to mention the main results which are used in this application of Kummer theory, and specialize to the case of quadratic and cubic extensions.

Let K be a fixed base field. In §4.2, we are given a congruence group (𝔪, H), and we compute the relative discriminant and signature of the class field L corresponding to this congruence group. We may of course assume that 𝔪 is the exact conductor of this field (otherwise we can easily reduce to this case). Our goal is to give a defining equation for L/K, here using Kummer theory.

Let us review what we know about the field L. We know its degree (equal to h_{𝔪,H}), its relative discriminant δ_{L/K}, and its signature. We also know exactly the finite and infinite primes of K which ramify in L, i.e. the prime divisors of 𝔪. In fact, the exponents of these primes in 𝔪 give more information. We of course know that L/K is an Abelian extension with Galois group isomorphic to Cl_{𝔪}.

We will make the following simplifying assumptions. First, we assume that h_{𝔪,H} = p is prime. Then the ramified primes in L/K (i.e. the prime divisors of 𝔪) are totally ramified. Second, we assume that p is coprime to 𝔪, i.e. 𝔪 is not divisible by any prime ideal of K above p.

We recall the following simple result, which is the beginning of Kummer theory.

Proposition 4.5. Let K be a number field and L/K be a cyclic extension of degree p. There exists α ∈ K such that L is a subfield of degree p of the Abelian extension N = K(ζ_{p}, \sqrt[p]{α}), where ζ_{p} is a primitive p-th root of unity.

If ζ_{p} ∈ K (for example when p = 2), then we have L = N and the only problem to solve is to find α. When ζ_{p} ∉ K, we must find α and also find L afterwards.

Assume first that ζ_{p} ∈ K. Then L = K(\sqrt[p]{α}). The discriminant of the polynomial X^{p} − α is p^{p}α^{p−1}, hence the only possible ramified prime ideals are those which divide p and those which divide α.

The following theorem gives the main result that we will need.

Theorem 4.6. Let p be a prime such that ζ_{p} ∈ K and let L = K(\sqrt[p]{α}).

(1) If 𝔮 is a prime ideal not dividing p, then 𝔮 is unramified in L/K if and only if v_{𝔮}(α) ≡ 0 (mod p). If 𝔮 is ramified, then v_{𝔮}(δ_{L/K}) = p − 1.

(2) If 𝔭 is a prime ideal dividing p, assume that 𝔭 ∤ α. Set a = v_{𝔭}(1−ζ_{p}) = e(𝔭/p)/(p−1). Then 𝔭 is unramified in L/K if and only if the congruence

x^{p} ≡ α (mod 𝔭^{ap})

has a solution in K.

(3) More precisely, if the congruence above has a solution, but the congruence mod 𝔭^{ap+1} does not, then 𝔭 stays inert, otherwise 𝔭 is totally split.

For a proof, see for example [Hec], Theorem 119.

To choose α, we first look at prime ideals dividing 𝔪, hence not dividing p by assumption. For each such prime ideal, we want v_{𝔮}(α) ≢ 0 (mod p). On the other hand, for any other prime ideal, we want v_{𝔮}(α) ≡ 0 (mod p). In many cases (but not all), we can even assume that v_{𝔮}(α) = 0 for these other prime ideals. Assume α thus chosen (there is of course an infinite number of choices). Multiplying α by a unit does not change the above conditions, and we will now use this freedom to deal with the primes above p.

Assume 𝔭 | p, so that in particular 𝔭 ∤ α and 𝔭 ∤ 𝔪. Thus 𝔭 must be unramified, and by Theorem 4.6 (2), this is equivalent to the congruence x^{p} ≡ α (mod 𝔭^{ap}) having a solution, and this must be true for all 𝔭 | p. So if 𝔠 = ∏_{𝔭|p} 𝔭, the necessary and sufficient conditions boil down to the solvability of the single congruence

x^{p} ≡ α (mod 𝔠^{ap}) .

Let α_{0} be obtained so that the local conditions at the primes 𝔮 not dividing p are satisfied. We want to find α = α_{0}u such that u is a unit and the congruence x^{p} ≡ α_{0}u (mod 𝔠^{ap}) is satisfied. For this, we use the following straightforward algorithm.

Algorithm 4.7 (Removal of ramification at p). Keep the above notation. This algorithm either finds a unit u such that if α = α_{0}u the congruence x^{p} ≡ α_{0}u (mod 𝔠^{ap}) is satisfied, or says that such a unit does not exist.

1. [Compute structure] Using Algorithm 2.10, compute the structure of the group (ℤ_{K}/𝔠^{ap})^{∗}.

2. [Compute discrete logarithms] Let ϵ_{0}, …, ϵ_{r} be a generating set for the units of K. Using Algorithm 2.12, compute the matrix H whose columns are the discrete logarithms of the ϵ_{j} in (ℤ_{K}/𝔠^{ap})^{∗} and the column vector B equal to the discrete logarithm of α_{0}.

3. [Perform Gauss] Using Gaussian elimination and performing all computations modulo p (i.e. in the field ℤ/pℤ), check whether the equation HX ≡ B (mod p) has a solution or not. If it does not, output a message saying that there does not exist a unit having the required properties.

4. Let X = (x_{0}, …, x_{r}) be a lift to ℤ^{r+1} (with small coefficients) of a solution of HX ≡ B (mod p). Set u ← ∏ ϵ_{j}^{−x_{j}}, output u and terminate the algorithm.

To continue, we need the following proposition, which is a refinement of Proposition 4.5.

Proposition 4.8. Assume that K contains the p-th roots of unity. Let g be a primitive root modulo p^{2}, and assume that there exists an automorphism τ of K extending the automorphism of ℚ(ζ_{p}) sending ζ_{p} to ζ_{p}^{g}. Let L/K be a cyclic extension of degree p. Then there exists β ∈ K such that if α = ∏_{a=0}^{p−2}(τ^{a}(β))^{g^{p−2−a}}, we have L = K(\sqrt[p]{α}).

Proof. Call σ a generator of the Galois group of L/K. By the normal basis theorem, we can find θ ∈ L such that L = K(θ) and σ^{i}(θ) a basis of L as a K-vector space. Set

γ = ∑_{i=0}^{p−1} ζ_{p}^{−i}σ^{i}(θ) .

Since the σ^{i}(θ) are linearly independent over K, γ is not equal to zero.

We have σ(γ) = ζ_{p}γ, from which it follows, as in Proposition 4.5, that

γ^{p} = (−1)^{p−1} N_{L/K}(γ) ∈ K

Similarly, it is clear that

σ(τ^{a}(γ)) = ζ_{p}^{g^{a}}τ^{a}(γ) .

We set β = γ^{g}/τ(γ). Then σ(β) = β, hence by Galois theory we have β ∈ K. Furthermore, an immediate calculation shows that

α = ∏_{a=0}^{p−2}(τ^{a}(β))^{g^{p−2−a}} = γ^{g^{p−1}−1} = δ^{p}

with δ = γ^{(g^{p−1}−1)/p}. To show that β is as desired, we must show that L = K(δ) or in other words, since [L : K] is prime, that δ ∉ K. But since g is a primitive root modulo p^{2}, (g^{p−1} − 1)/p ≢ 0 (mod p), so since γ^{p} ∈ K, if δ ∈ K we would have also γ ∈ K. But since σ(γ) = ζ_{p}γ, we would then have γ = 0, which is absurd. This proves the proposition. ⊓ ⊔

Corollary 4.9. Keep the notations of Proposition 4.8. Let θ = \sqrt[p]{α} such that L = K(θ). Then if we define

τ(θ) = θ^{g}/β^{(g^{p−1}−1)/p} ,

and extend τ in a natural way to all of L, this gives an automorphism of L extending the automorphism τ of K. In addition, we have for 0 ≤ a ≤ p − 2,

τ^{a}(θ) = θ^{g^{a}}/ ∏_{i=0}^{a−1}(τ^{i}(β))^{(g^{p−2+a−i}−g^{a−i−1})/p} .

Proof. Since θ^{p} = α, we must have τ(θ)^{p} = τ(α). Using the definition of α in terms of β, we find that

θ^{gp}/τ(θ)^{p} = β^{g^{p−1}−1} ,

from which it follows that

θ^{g}/τ(θ) = ζ_{p}^{k}β^{(g^{p−1}−1)/p} for some k .

We can choose k = 0 (the other choices will give the p different extensions of τ to L), and we obtain the first formula of the corollary. The second is easily proved by induction. ⊓ ⊔

Assume now that ζ_{p} ∉ K. We set as before M = K(ζ_{p}) which is a cyclic extension of K of degree p − 1. The conditions on α are exactly the same as before, except of course that we must choose α ∈ M and not in K. Thus, we may assume that N has been obtained. We now want to obtain L itself.

Corollary 4.10. Keep the notations of Proposition 4.8 and Corollary 4.9, applied to the extension N/M instead of L/K. Set

λ = ∑_{a=0}^{p−2} τ^{a}(θ)

as defined in Corollary 4.9. Then L = K(λ).

Proof. We have λ ∈ N and τ(λ) = λ, hence by Galois theory λ ∈ L. Since [L : K] is prime, to show that L = K(λ) we need only to show that λ ∉ K. Assume the contrary. Thus, ∑_{a=0}^{p−2} τ^{a}(θ) = λ ∈ K. Recall that N, as the compositum of the two Abelian extensions L/K and M/K, is Abelian, hence τ and σ commute. Applying σ^{i} to the above equality, and using σ(θ) = ζ_{p}θ and τ(ζ_{p}) = ζ_{p}^{g}, we obtain for each i

∑_{a=0}^{p−2} ζ_{p}^{ig^{a}}τ^{a}(θ) = λ .

Using these equalities only for 0 ≤ i ≤ p − 2, we thus obtain a system of p − 1 equations in p − 1 unknowns, whose determinant is that of the Van der Monde matrix ζ_{p}^{ig^{a}}. Since the ζ_{p}^{g^{a}} are distinct for 0 ≤ a ≤ p − 2, this determinant is nonzero, hence we obtain θ ∈ K, which is absurd. Hence λ ∉ K and L = K(λ) as claimed. ⊓ ⊔

5. Numerical results

5.1. Two examples of Kummer theory

To illustrate the results of §4, we give two examples coming from the numerical results given in §5.2. The first example is that of a quadratic extension, for which it is not necessary to adjoin roots of unity. The second example is that of a cubic extension.

In the first example, the base field K is defined by a root z of the polynomial x^{6} − x^{5} + 2x^{3} −2x^{2} +1. In this field, the prime number 41 splits as the product of three prime ideals of degree 1, and one prime ideal of degree 3. One of the prime ideals of degree 1 is equal to 𝔓_{41} = 41ℤ_{K} + (z + 4)ℤ_{K}. The number field K has two real places v_{1} and v_{2}. We take as modulus 𝔪 = 𝔓_{41}v_{1}v_{2} and H = I_{𝔪} as congruence group. Using the algorithms of §4.2, we find that the ray class group is of order 2, hence that there exists a quadratic extension L of K ramified only at primes above 𝔪, hence totally complex and ramified only at the finite prime 𝔓_{41}, and we compute its relative discriminant to be equal to 𝔓_{41} itself (in the present case, this is trivial). We now want a defining equation for L/K.

Since L/K is quadratic, we have L = K(\sqrt{α}) for some α ∈ ℤ_{K}. We first want this extension to be unramified outside 2 and 𝔓_{41}. For this, using the principal ideal problem in K, we compute that 𝔓_{41} = α_{0}ℤ_{K} with α_{0} = z^{5} + 2z^{2} − 2z. Since we want L/K to be ramified above 𝔓_{41} and no other prime ideals, from Theorem 4.6 and the fact that K is principal, we see that we must choose α = α_{0}u for u a unit of ℤ_{K}.

We now apply Algorithm 4.7 to remove ramification above 2. We check that 2 is inert in K, hence a = v_{𝔭}(1 − ζ_{2}) = 1. Thus 𝔠^{ap} = 4ℤ_{K}. Applying Algorithm 2.10, we find that

(ℤ_{K}/4ℤ_{K})^{∗} ≃ (ℤ/126ℤ) × (ℤ/2ℤ)^{5}

with generators −2z^{5} + z − 2, −1 and −2z^{i} + 1 for 1 ≤ i ≤ 4.

We can choose as generators of units ϵ_{0} = −1, ϵ_{1} = z, ϵ_{2} = z^{3}+1, ϵ_{3} = z^{4}−z^{3}+z^{2}+z−1. Using Algorithm 2.12, we find that the matrix H of discrete logarithms of the units is

H = ( \begin{matrix}0 & 64 & 97 & 11 \\ 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{matrix} ) ,

while the column vector B of the discrete logarithm of α_{0} is equal to B = [68, 0, 1, 1, 0, 0]^{t}. By Gaussian elimination in ℤ/2ℤ, we see that the column vector X = [0, 0, 1, 1]^{t} is the unique solution modulo 2 to HX ≡ B (mod 2). Thus if we set

α = α_{0}ϵ_{2}^{−1}ϵ_{3}^{−1} = −z^{5} + 2z^{4} − 3z^{2} + 3z ,

the ramification conditions at all the finite primes will be satisfied. The only freedom that we still have is to multiply by a square of a unit. In particular this does not change the signature, i.e. the ramification at infinity. One checks that indeed the real places are ramified, so L is a totally complex field.

Thus L can be defined over K by the equation

X^{2} − (−z^{5} + 2z^{4} − 3z^{2} + 3z) = 0 .

To get the absolute defining equation of L over ℚ, we simply compute the resultant with respect to z of X^{2}−(−z^{5}+2z^{4}−3z^{2}+3z) with the defining polynomial z^{6}−z^{5}+2z^{3}−2z^{2}+1, and we obtain

x^{12} − x^{10} + 2x^{8} + 28x^{6} − 23x^{4} − 47x^{2} + 41

as defining equation for our number field L.

Using polynomial reduction techniques (see [Coh] and [Co-Di]), we finally obtain the equation

x^{12} − 2x^{11} + 2x^{10} − x^{9} + 2x^{8} − 5x^{7} + 8x^{6} − 7x^{5} + 4x^{4} − 3x^{3} + 4x^{2} − 3x + 1

given below.

As a second example, we will take the case of a cubic extension. Here the base field K is defined by a root of the polynomial x^{6} − 2x^{5} + 3x^{4} + x^{2} + 3x + 1. This is a totally complex number field in which 2 is inert, and we choose as modulus 𝔪 the prime ideal 2ℤ_{K} alone, and H = I_{𝔪}. Using the algorithms of §4, we find that the ray class group is of order 3, hence that there exists a cubic extension L of K ramified only at 2, and we compute its relative discriminant ideal to be equal to 4ℤ_{K} = 2^{2}ℤ_{K}. We now want a defining equation for L/K. Since ζ_{3} ∉ K, we must start by adjoining ζ_{3} to K. Thus we set M = K(ζ_{3}) and N = L(ζ_{3}). A straightforward computation, followed by polynomial reduction, shows that M can be defined by a root of the polynomial

P = x^{12} − 2x^{11} + x^{10} − 6x^{9} + 8x^{8} + 7x^{7} + 5x^{6} − 20x^{5} − 2x^{4} + 3x^{3} + 8x^{2} + 3x + 1 .

Applying Proposition 4.8 to the extension N/M, we see that there exists β ∈ M such that N = M(\sqrt[3]{α}) with α = β^{2}τ(β). In M, the prime 2 splits as the product of two prime ideals of degree 6, and since M is principal, they are generated by elements β_{0} and β_{1} = τ(β_{0}) respectively which can be found using the principal ideal problem (note that we must choose β_{1} = τ(β_{0}) here and not any other generator). Since we do not want any ramification outside 2, we must choose β equal to some product of powers of β_{0} and β_{1} such that the corresponding α = β^{2}τ(β) satisfies the conditions of Theorem 4.6. It is easily checked that any choice of such a β will lead to the same field. Thus, we can choose β = β_{0}, and we will have the correct ramification outside from 3.

To get rid of the ramification at 3, we apply Algorithm 4.7, i.e. we look for a unit u such that α = α_{0}u is such that the congruence x^{3} ≡ α (mod 𝔠^{3a}) has a solution, with α_{0} = β_{0}^{2}τ(β_{0}). In our field M, we have 3ℤ_{M} = 𝔭^{2}𝔭′^{2} for prime ideals 𝔭 and 𝔭′ of degree 3, and hence (1 − ζ_{3})ℤ_{K} = 𝔭𝔭′. Thus a = 1, 𝔠 = 𝔭𝔭′, and so we must solve the congruence

x^{3} ≡ α_{0}u (mod 𝔭^{3}𝔭′^{3}) .

Using Algorithm 2.10, we compute that

(ℤ_{M}/(𝔭^{3}𝔭′^{3}))^{∗} ≃ (ℤ/78ℤ)^{2} × (ℤ/3ℤ)^{10}

and the corresponding SNF generators. Finishing Algorithm 4.7, we can easily find a desired unit u, which will be defined up to cubes of units.

However, to be able to get down to L, we will need to write u in the form u = ϵ^{2}τ(ϵ) for some unit ϵ. To do this, we must do two things. First, we must find the action of τ on the generators ϵ_{0}, …,ϵ_{5} of the units of M. If we have kept track of how the field M = K(ζ_{3}) was constructed, this is trivially done. If not, we can apply one of the techniques for the field isomorphism problem to get explicitly the action of τ.

In any case, in this way, we obtain a 6 × 6 matrix U such that the columns of U give (multiplicatively) the components of τ(ϵ_{j}) on the ϵ_{i}. Let X be the column vector giving the components of our the unit u found in Algorithm 4.7 on the ϵ_{j}. Then (2X − UX)/3 will be the components of the desired unit ϵ on the ϵ_{i}. Note that this is a good check of the correctness of many computations, since these components must be integers.

So finally, we choose β = β_{0}ϵ and α = β^{2}τ(β). To find L, we apply Corollaries 4.9 and 4.10 which tell us that L = K(y) with y = θ + θ^{2}/β, where θ is a root of x^{3} − α = 0. It is now easy to find a relative equation for L/K, and hence an absolute equation, which we can then reduce. This is how the degree 18 example below was computed.

Note that we have not given explicit values for the different numbers which are involved (the units, α_{0}, β, etc...) because they are not canonical and depend on the way the algorithms are programmed, so the reader will certainly have different values than ours. Only the final reduced equation given below should be similar.

5.2 Small discriminants

Using the algorithms described in this paper, we have computed a very large number of Abelian field extensions corresponding to congruence groups (𝔪, H). Here, to compute such an extension means to compute its degree, signature, absolute or relative discriminant, but not a defining equation.

We have proceeded as follows. Using tables of number fields K of degree less or equal to 7 available by anonymous ftp at the URL

             ftp://megrez.math.u-bordeaux.fr/pub/numberfields/

we have computed a list of moduli 𝔪 of norm less than or equal to a certain bound. For each of these (K, 𝔪) we have obtained the ray class group Cl_{𝔪} using the above algorithms, and then for each subgroup \overline{H} of Cl_{𝔪}, we have computed the signature and discriminant of the field L corresponding to the congruence group (𝔪, H). The subgroups \overline{H} can be obtained as explained in §4.1.

In the course of this computation, if we find that 𝔪 is not the conductor of L (i.e. that h_{𝔪,H} = h_{𝔪/v,H} for some v | 𝔪), then we stop the computation and go to the next. Otherwise, we keep only those L which give an absolute degree [L : ℚ] = h_{𝔪,H} ·[K : ℚ] less than or equal to 100. Finally, among those, we keep only those whose root discriminant is close compared to the GRH bounds (for example less than 1.2 times these bounds, see [Odl]).

To run these programs, we have recomputed these GRH bounds so as to have a complete list for all signatures (R_{1}, R_{2}) and degree up to 100. These are available as a text file readable by GP/Pari at the same URL given above.

Now the question arises of where to stop the search, both for the base fields, and, for a given base field, for the moduli.

We use the following criterium. Let C be the maximum of the allowable root discriminants. For example, we can take C = 1.2B where B is the upper bound of the Odlyzko bounds for all degrees considered with a given signature.

Set n = [K : ℚ] and N = [L : ℚ]. Then by Théorème 4.3, we have

|d_{L/ℚ}|^{1/h_{𝔪,H}} = \frac{N (𝔪)}{∏_{𝔭|𝔪} N (𝔭)^{∑_{1≤k≤e_{i}} h_{𝔪/𝔭^{k},H}/h_{𝔪,H}}} |d_{K/ℚ}| .

However, since 𝔪 is assumed to be the conductor, we have h_{𝔪/𝔭^{k},H} < h_{𝔪,H} for k ≥ 1. Call τ(a) the smallest prime divisor of an integer a. Thus h_{𝔪/𝔭^{k},H} ≤ h_{𝔪,H}/τ(h_{𝔪,H}). From this and the above formula giving d_{L/ℚ}, an immediate computation shows that

N (𝔪) ≤ (|d_{L/ℚ}|^{1/N}/|d_{K/ℚ}|^{1/n})^{nτ/(τ−1)} ,

with τ = τ(h_{𝔪,H}). Since we want the root discriminant to be less than C, and since τ/(τ − 1) is at most equal to 2, this implies

N (𝔪) ≤ C^{2n}/|d_{K/ℚ}|^{2} .

Now this is of course a very pessimistic upper bound, but it shows several things. First, the number of moduli to consider for a given base field is finite (assuming of course that we limit the degree and the discriminant).

Second, the number of base fields to consider is also finite. More precisely, as |d_{K/ℚ}| increases, the number of possible moduli will decrease rather fast, hence interesting fields will become rather rare.

Furthermore, note that the result does not depend on h_{𝔪,H} and in particular not on the group H. For a given degree, the bound can be considerably improved (for example if the relative degree is odd, then τ/(τ − 1) ≤ 3/2, which gives much better bounds). Furthermore, for a given modulus satisfying the bounds, usually only a small number of H will be able to satisfy the simple condition on the degree of the field.

Of course all these observations are well known, but it is useful to put them on a quantitative footing.

One can then ask if it is plausible to find completely all the Abelian extensions of number fields of degree less than or equal to 7 (we do not have reasonably large tables in higher degrees) satisfying the limitations of degree and discriminant given above (degree up to 100 and root discriminant up to 1.2 times the GRH bound). While not absolutely impossible, it seems like a huge amount of computation.

To compare with previous results, we had at our disposal two sources. First the computations of [Mar] which were done 15 years ago in exactly the same spirit as this paper, but without the computer power. It is all the more remarkable that we have not been able to beat many of his records.

Second the papers [Leu] and [Le-Ni] which deal with Euclidean fields, most of which are not obtained as Abelian extensions of subfields, and only in small degree (less than or equal to 11).

We give below a list of 10 totally complex number fields obtained by the ray class field method. These fields all seem to be new and give the smallest known discriminant corresponding to their signature. In each case, the congruence group is trivial, and 𝔪_{∞} is the set of all real places of the base field K (if this was not the case, either L would not be totally complex or 𝔪 would not be its conductor). Thus we list the absolute degree [L : ℚ], the base field K, the finite part 𝔪_{0} of the modulus 𝔪 as a product of prime ideals (written 𝔓_{p} to indicate a prime ideal of degree 1 above p and 𝔭_{p} a prime ideal of degree 2 above p), the discriminant in factored form, the root discriminant, and the percentage above the Odlyzko bound that we have computed (note that the bounds that we use are slightly better than those used by [Mar], hence when comparing the papers one should compare the root discriminant and not the percentage).

\begin{matrix}N & K & 𝔪_{0} & d_{L/ℚ} & |d_{L/ℚ}|^{1/N} & GRH \\ 12 & x^{6} − x^{5} + 2x^{3} − 2x^{2} + 1 & 𝔓_{41} & 37^{2} · 41 · 857^{2} & 7.666 & 0.843% \\ 16 & x^{4} − x − 1 & 𝔓_{17}𝔓_{37} & 17^{2} · 37^{2} · 283^{4} & 9.179 & 1.164% \\ 18 & x^{6} − 2x^{5} + 3x^{4} + x^{2} + 3x + 1 & (2) & −2^{12} · 23^{6} · 107^{3} & 9.836 & 1.378% \\ 28 & x^{4} + 2x^{2} − 2x + 1 & 𝔓_{71} & 2^{28} · 37^{7} · 71^{6} & 12.296 & 1.135% \\ 32 & x^{4} − x^{3} + 2x + 1 & 𝔓_{3}𝔭_{13} & 3^{28} · 7^{8} · 13^{14} & 13.065 & 1.135% \\ 36 & x^{4} − x^{3} + 31x^{2} − 24x + 252 & (1) & 3^{18} · 4057^{9} & 13.823 & 1.709% \\ 40 & x^{2} + 2 & 𝔓_{3}𝔓′_{3}𝔓_{11} & 2^{60} · 3^{20} · 11^{18} & 14.412 & 1.543% \\ 48 & x^{4} − x^{3} + 4x^{2} + 3x + 9 & 𝔭_{2}𝔭_{5} & 2^{16} · 3^{24} · 5^{20} · 13^{24} & 15.386 & 1.006% \\ 52 & x^{4} − 2x^{3} + 21x^{2} − 20x + 68 & (1) & 2^{78} · 1009^{13} & 15.941 & 1.626% \\ 56 & x^{4} − x^{3} − 2x + 8 & 𝔓_{2}^{3} & 2^{49} · 3^{42} · 241^{14} & 16.472 & 2.283% \end{matrix}

Using Kummer theory as explained in §4.4, we have computed relative and absolute defining equations for the fields above. The absolute equations of the first three are:

x^{12} − 2x^{11} + 2x^{10} − x^{9} + 2x^{8} − 5x^{7} + 8x^{6} − 7x^{5} + 4x^{4} − 3x^{3} + 4x^{2} − 3x + 1

x^{16} + 2x^{14} − x^{13} + 3x^{12} − 4x^{11} + 4x^{10} − 7x^{9} + 5x^{8} − 7x^{7} + 4x^{6} − 4x^{5} + 3x^{4} − x^{3} + 2x^{2} + 1

x^{18} − x^{17} + 3x^{16} + 2x^{15} − x^{14} + 11x^{13} + 3x^{12} + 3x^{11} + 28x^{10}
− 18x^{9} + 47x^{8} − 27x^{7} + 45x^{6} − 23x^{5} + 27x^{4} − 11x^{3} + 9x^{2} − 2x + 1 .

In addition to these fields, we have found a large number of fields of various signatures. This computation will be described in a forthcoming paper. Many of them have large discriminants compared to the Odlyzko bounds. This may be expected, since there is no reason, especially in large degrees, that small discriminants will correspond to Abelian extensions of subfields. On the contrary, it is plausible that the Galois group of such fields will tend to be the complete symmetric group S_{n}, which forbids the fields to have nontrivial subfields.

References

[B-D-S] E. Bach, J. Driscoll and J. Shallit, Factor refinement, J. of Algor. 15 (1993), 199–222.

[Coh] H. Cohen, A course in computational algebraic number theory, GTM 138, Springer-Verlag, Berlin, Heidelberg, New York, 1993.

[Coh2] H. Cohen, Hermite and Smith normal form algorithms over Dedekind domains, Math. Comp. (1996) (to appear).

[Co-Di] H. Cohen and F. Diaz y Diaz, A polynomial reduction algorithm, Sém. Th. des Nombres

Bordeaux (série 2) 3 (1991), 351–360.

[Da-Po] M. Daberkow and M. Pohst, Computations with relative extensions of number fields with an application to the construction of Hilbert class fields, Proc. ISAAC’95 (1995) (to appear).

[Di-Ol] F. Diaz y Diaz and M. Olivier, Algorithmique Algébrique dans les Corps de Nombres, Etat de

la Recherche en Algorithmique Arithmétique, Laboratoire A2X, Bordeaux, 1995.

[Ha-Ma] G. Havas and B. Majewski, Hermite normal form computation for integer matrices, preprint.

[Hec] E. Hecke, Lectures on the theory of algebraic numbers, GTM 77, Springer-Verlag, Berlin, Heidelberg, New York, 1981.

[Leu] A. Leutbecher, Euclidean fields having a large Lenstra constant, Ann. Inst. Fourier 35,2 (1985), 83–106.

[Le-Ni] A. Leutbecher and G. Niklasch, On cliques of exceptional units and Lenstra’s construction of

Euclidean fields, preprint, TUM Math. Inst. M8705 (1987).

[Mar] J. Martinet, Petits discriminants des corps de nombres, Journées arithmétiques 1980 (J.V. Armitage, Ed.), London Math. Soc. Lecture Notes Ser. 56 (1982), 151–193.

[Nak] N. Nakagoshi, The structure of the multiplicative group of residue classes modulo ℘^{N+1}, Nagoya Math. J. 73 (1979), 41–60.

[Odl] A. M. Odlyzko, Bounds for discriminants and related estimates for class numbers, regulators and zeros of zeta functions: a survey of recent results, Sém. Th. des Nombres Bordeaux (série 2) 2 (1990), 119–141.

[Po-Za] M. Pohst and H. Zassenhaus, Algorithmic algebraic number theory, Encyclopedia of Math. and

its Applications, Cambridge University Press, Cambridge, 1989.

[Zan] H. Zantema, Class numbers and units; Computational methods in number theory II (Math. Centrum, ed.), Math. Centre Tracts 155, Amsterdam, 1982, pp. 213–234.

Laboratoire A2X, Université Bordeaux I, 351 cours de la Libération, 33405 Talence cedex

E-mail address: cohen@math.u-bordeaux.fr,diaz@math.u-bordeaux.fr,olivier@math.u-bordeaux.fr