## A Method for Factoring that Always Works

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

Most algebraic number theory books do not describe an algorithm for decomposing primes in the general case. Fortunately, Cohen's book [Coh93, §6.2]) describes how to solve the general problem. The solutions are somewhat surprising, since the algorithms are much more sophisticated than the one suggested by Theorem 8.1.3. However, these complicated algorithms all run very quickly in practice, even without assuming the maximal order is already known.

For simplicity we consider the following slightly easier problem whose solution contains the key ideas: Let be any order in and let be a prime of . Find the prime ideals of that contain .

To go from this special case to the general case, given a prime that we wish to factor in , we find a -maximal order , i.e., an order such that is coprime to . A -maximal order can be found very quickly in practice using the round 2'' or round 4'' algorithms. (Remark: Later we will see that to compute , we take the sum of -maximal orders, one for every such that divides . The time-consuming part of this computation of is finding the primes such that , not finding the -maximal orders. Thus a fast algorithm for factoring integers would not only break many cryptosystems, but would massively speed up computation of the ring of integers of a number field.)

Algorithm 8.1.4   Suppose is an order in the ring of integers of a number field . For any prime , the following (sketch of an) algorithm computes the set of maximal ideals of that contain .

Sketch of algorithm. Let be a number field given by an algebraic integer as a root of its minimal monic polynomial of degree . We assume that an order has been given by a basis and that that contains . Each of the following steps can be carried out efficiently using little more than linear algebra over . The details are in [Coh93, §6.2.5].

1. [Check if easy] If (so ), then by a slight modification of Theorem 8.1.3, we easily factor .
2. [Compute radical] Let be the of , which is the ideal of elements such that for some positive integer . Using linear algebra over the finite field , we can quickly compute a basis for . (We never compute .)
3. [Compute quotient by radical] Compute an basis for The second equality comes from the fact that , which is clear by definition. Note that is obtained by simply reducing the basis modulo .
4. [Decompose quotient] The ring is a finite Artin ring with no nilpotents, so it decomposes as a product of fields. We can quickly find such a decomposition explicitly, as described in [Coh93, §6.2.5].
5. [Compute the maximal ideals over ] Each maximal ideal lying over is the kernel of .

The algorithm finds all primes of that contain the radical of . Every such prime clearly contains , so to see that the algorithm is correct, we must prove that the primes of that contain also contain . If is a prime of that contains , then . If then for some , so which implies that by primality of . Thus contains , as required.

William Stein 2004-05-06