Remarks on Ideal Factorization in General

Recall (from Definition 2.3.13) that an order in $\O_K$ is a subring $\O$ of $\O_K$ that has finite index in $\O_K$. For example, if $\O_K = \mathbf{Z}[i]$, then $\O=\mathbf{Z}+ 5\mathbf{Z}[i]$ is an order in $\O_K$, and as an abelian group $\O_K/\O$ is cyclic of order $5$.

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 $\O_K$ altogether, and instead compute only an order $\O$ that is $p$-maximal, i.e., is such that $p \nmid [\O_K:\O]$.

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 $\O$ be any order in $\O_K$ and let $p$ be a prime of $\mathbf {Z}$. Find the prime ideals of $\O$ that contain $p$.

Given a prime $p$ that we wish to factor in $\O_K$, we first find a $p$-maximal order $\O$. We then use a solution to Problem 4.3.3 to find the prime ideals $\mathfrak{p}$ of $\O$ that contain $p$. Second, we find the exponents $e$ such that $\mathfrak{p}^e$ exactly divides $p\O$. The resulting factorization in $\O$ completely determines the factorization of $p\O_K$.

A $p$-maximal order can be found reasonably quickly in practice using algorithms called ``round 2'' and ``round 4''. To compute $\O_K$, given an order $\mathbf{Z}[\alpha]\subset \O_K$, one takes a sum of $p$-maximal orders, one for every $p$ such that $p^2$ divides $\Disc (\mathbf{Z}[\alpha])$. The time-consuming part of this computation is finding the primes $p$ such that $p^2\mid \Disc (\mathbf{Z}[\alpha])$, not finding the $p$-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 $\O_K$ in an algebraic number field $K$ 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 $\O_K$ is quite hard.