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.

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.

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