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].
William Stein 2004-05-06