## Remarks on Ideal Factorization in General

Recall (from Definition 2.3.13) that an order in is a subring of that has finite index in . For example, if , then is an order in , and as an abelian group is cyclic of order .

Most algebraic number theory books do not describe an algorithm for decomposing primes in the general case. Fortunately, Cohen's book [Coh93, Ch. 6] does describe how to solve the general problem, in more than one way. The algorithms are nontrivial, and occupy a substantial part of Chapter 6 of Cohen's book. Our goal for the rest of this section is to give a hint as to what goes into them.

The general solutions to prime ideal factorization are somewhat surprising, since the algorithms are much more sophisticated than the one suggested by Theorem 4.2.3. However, these complicated algorithms all run very quickly in practice, even without assuming the maximal order is already known. In fact, they avoid computing  altogether, and instead compute only an order  that is -maximal, i.e., is such that .

For simplicity we consider the following slightly easier problem whose solution illustrates the key ideas needed in the general case.

Problem 4.3.3   Let be any order in and let  be a prime of . Find the prime ideals of that contain .

Given a prime  that we wish to factor in , we first find a -maximal order . We then use a solution to Problem 4.3.3 to find the prime ideals of that contain . Second, we find the exponents such that exactly divides . The resulting factorization in completely determines the factorization of .

A -maximal order can be found reasonably quickly in practice using algorithms called round 2'' and round 4''. To compute , given an order , one takes a sum of -maximal orders, one for every  such that divides . The time-consuming part of this computation is finding the primes  such that , not finding the -maximal orders. This example illustrates that a fast algorithm for factoring integers would not only break the RSA cryptosystems, but would massively speed up computation of the ring of integers of a number field.

Remark 4.3.4   The MathSciNet review of [BL94] by J. Buhler contains the following:
A result of Chistov says that finding the ring of integers in an algebraic number field is equivalent, under certain polynomial time reductions, to the problem of finding the largest squarefree divisor of a positive integer. No feasible (i.e., polynomial time) algorithm is known for the latter problem, and it is possible that it is no easier than the more general problem of factoring integers.
Thus it appears that computing the ring is quite hard.

William Stein 2012-09-24