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 over a given prime . 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 be any *order* in
, i.e., a subring of such that the additive abelian group
is finite. Let
.

**Solution (sketch).**

*Let
be a number field given
by an algebraic integer as root of its
minimal monic polynomial of degree .
We assume that an order has been
given by a basis
and that that contains
.
*

*Given a prime number
, the following ( sketch of an) algorithm
computes the primes
lying over , i.e., the
maximal ideals
of that contain . Each of the following
steps can be carried out very efficiently using little more
than linear algebra over
. The details are in [1, §6.2.5].
*

- [Check if easy] If then by a slight modification of Theorem 2.1, we easily factor .
- [Compute radical] Using linear algebra over the finite field
, compute a basis for , where is the radical of .
(The
*radical*of is the ideal of elements such that for some positive integer .) - [Compute quotient]
Compute an
basis of
- [Decompose] Decompose as a product of fields.
- [Compute the maximal ideals] Each maximal ideal lying over is the kernel of .