Method that Always Works

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

I looked in a large handful of algebraic number theory books, and found only one (see [1, §6.2]) that reports on how to solve the general problem of computing the maximal ideals of $\O _K$ over a given prime $p$. In general, this appears to be a surprising problem, in the sense that the algorithms to solve it are much more sophisticated than Theorem 2.1. However, these complicated algorithms all run very quickly in practice.

For simplicity we consider the following slightly easier problem, whose solution contains the key ideas. Let $\O$ be any order in $\O _K$, i.e., a subring of $\O _K$ such that the additive abelian group $\O _K/\O$ is finite. Let $[\O _K : \O ] = \char93 (\O _K/\O )$.

Problem 3.1   For any prime $p\in\mathbb{Z}$, compute the set of maximal ideals of $\O$ that contain $p$.

Solution (sketch).

Let $K=\mathbb{Q}(\theta)$ be a number field given by an algebraic integer $\theta$ as root of its minimal monic polynomial $F$ of degree $n$. We assume that an order $\O$ has been given by a basis $\omega_1,\ldots,\omega_n$ and that $\O$ that contains $\mathbb{Z}[\theta]$.

Given a prime number $p\in\mathbb{Z}$, the following (sketch of an) algorithm computes the primes $\mathfrak{p}_i\in\Spec(\O )$ lying over $p$, i.e., the maximal ideals $\mathfrak{p}_i$ of $\O$ that contain $p$. Each of the following steps can be carried out very efficiently using little more than linear algebra over $\mathbb{F}_p$. The details are in [1, §6.2.5].

1. [Check if easy] If $p\nmid \disc(\mathbb{Z}[\theta]) / \disc(\O )$ then by a slight modification of Theorem 2.1, we easily factor $p\O$.
2. [Compute radical] Using linear algebra over the finite field $\mathbb{F}_p$, compute a basis for $I/p\O$, where $I$ is the radical of $p\O$. (The radical of $p\O$ is the ideal of elements $x\in\O$ such that $x^m\in p\O$ for some positive integer $m$.)
3. [Compute quotient] Compute an $\mathbb{F}_p$ basis of
   $$A = \O /I = (\O /p\O )/(I/p\O ).$$

4. [Decompose] Decompose $A$ as a product $A \cong \prod \mathbb{F}_p[x]/g_i(x)$ of fields.
5. [Compute the maximal ideals] Each maximal ideal $\mathfrak{p}_i$ lying over $p$ is the kernel of $\O\rightarrow A \rightarrow F_p[x]/g_i(x)$.