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

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

- [Check if easy] If (so ), then by a slight modification of Theorem 8.1.3, we easily factor .
- [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 .)* - [Compute quotient by radical]
Compute an
basis for
- [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].
- [Compute the maximal ideals over ] Each maximal ideal lying over is the kernel of .

William Stein 2004-05-06