Next: Essential Discriminant Divisors Up: Factoring Primes in Rings Previous: A Method that Usually

# Method that Always Works

Unfortunately, there are numbers fields such that is not of the form for any . Even worse, Dedekind found a field  such that for all , so Theorem 2.1 can not be used to factor  (see Example 4.2 below).

I looked in a large handful of algebraic number theory books, and found only one (see [1, §6.2]) that reports on how to solve the general problem of computing the maximal ideals of over a given prime . In general, this appears to be a surprising problem, in the sense that the algorithms to solve it are much more sophisticated than Theorem 2.1. However, these complicated algorithms all run very quickly in practice.

For simplicity we consider the following slightly easier problem, whose solution contains the key ideas. Let be any order in , i.e., a subring of such that the additive abelian group is finite. Let .

Problem 3.1   For any prime , compute the set of maximal ideals of  that contain .

Solution (sketch).

Let be a number field given by an algebraic integer as root of its minimal monic polynomial  of degree . We assume that an order has been given by a basis and that that contains .

Given a prime number , the following (sketch of an) algorithm computes the primes lying over , i.e., the maximal ideals of that contain . Each of the following steps can be carried out very efficiently using little more than linear algebra over . The details are in [1, §6.2.5].

1. [Check if easy] If then by a slight modification of Theorem 2.1, we easily factor .
2. [Compute radical] Using linear algebra over the finite field , compute a basis for , where  is the radical of . (The radical of is the ideal of elements such that for some positive integer .)
3. [Compute quotient] Compute an basis of

4. [Decompose] Decompose  as a product of fields.
5. [Compute the maximal ideals] Each maximal ideal lying over  is the kernel of .

Next: Essential Discriminant Divisors Up: Factoring Primes in Rings Previous: A Method that Usually
William A Stein 2002-03-08