A Method for Factoring that Always Works

There are numbers fields $K$ such that $\O _K$ is not of the form $\mathbf{Z}[a]$ for any $a\in K$. Even worse, Dedekind found a field $K$ such that $2\mid [\O _K : \mathbf{Z}[a]]$ for all $a\in\O _K$, so there is no choice of $a$ such that Theorem 8.1.3 can be used to factor $2$ for $K$ (see Example 8.1.6 below).

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 $\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$.

To go from this special case to the general case, given a prime $p$ that we wish to factor in $\O _K$, we find a $p$-maximal order $\O$, i.e., an order $\O$ such that $[\O _K:\O ]$ is coprime to $p$. A $p$-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 $\O _K$, we take the sum of $p$-maximal orders, one for every $p$ such that $p^2$ divides $\Disc (\O _K)$. The time-consuming part of this computation of $\O _K$ is finding the primes $p$ such that $p^2\mid \Disc (\O _K)$, not finding the $p$-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.)

Algorithm 8.1.4   Suppose $\O$ is an order in the ring $\O _K$ of integers of a number field $K$. For any prime $p\in\mathbf{Z}$, the following (sketch of an) algorithm computes the set of maximal ideals of $\O$ that contain $p$.

Sketch of algorithm. Let $K=\mathbf{Q}(a)$ be a number field given by an algebraic integer $a$ as a root of its minimal monic polynomial $f$ of degree $n$. We assume that an order $\O$ has been given by a basis $w_1,\ldots,w_n$ and that $\O$ that contains $\mathbf{Z}[a]$. Each of the following steps can be carried out efficiently using little more than linear algebra over $\mathbf{F}_p$. The details are in [Coh93, §6.2.5].

1. [Check if easy] If $p\nmid \disc (\mathbf{Z}[a]) / \disc (\O )$ (so $p\nmid [\O :\mathbf{Z}[a]]$), then by a slight modification of Theorem 8.1.3, we easily factor $p\O$.
2. [Compute radical] Let $I$ be the of $p\O$, which is the ideal of elements $x\in\O$ such that $x^m\in p\O$ for some positive integer $m$. Using linear algebra over the finite field $\mathbf{F}_p$, we can quickly compute a basis for $I/p\O$. (We never compute $I\subset \O$.)
3. [Compute quotient by radical] Compute an $\mathbf{F}_p$ basis for
   $$A = \O /I = (\O /p\O )/(I/p\O ).$$
   The second equality comes from the fact that $p\O\subset I$, which is clear by definition. Note that $\O /p\O\cong \O\otimes \mathbf{F}_p$ is obtained by simply reducing the basis $w_1,\ldots,w_n$ modulo $p$.
4. [Decompose quotient] The ring $A$ is a finite Artin ring with no nilpotents, so it decomposes as a product $A \cong \prod \mathbf{F}_p[x]/g_i(x)$ of fields. We can quickly find such a decomposition explicitly, as described in [Coh93, §6.2.5].
5. [Compute the maximal ideals over $p$] Each maximal ideal $\mathfrak{p}_i$ lying over $p$ is the kernel of $\O\rightarrow A \rightarrow \mathbf{F}_p[x]/g_i(x)$.

The algorithm finds all primes of $\O$ that contain the radical $I$ of $p\O$. Every such prime clearly contains $p$, so to see that the algorithm is correct, we must prove that the primes $\mathfrak{p}$ of $\O$ that contain $p$ also contain $I$. If $\mathfrak{p}$ is a prime of $\O$ that contains $p$, then $p\O\subset \mathfrak{p}$. If $x\in I$ then $x^m\in p\O$ for some $m$, so $x^m\in \mathfrak{p}$ which implies that $x\in \mathfrak{p}$ by primality of $\mathfrak{p}$. Thus $\mathfrak{p}$ contains $I$, as required.