Finding a $p$-Maximal Order

Before describing the general factorization algorithm, we sketch some of the theory behind the general algorithms for computing a $p$-maximal order $\O$ in $\O_K$. The main input is the following theorem:

Theorem 4.3.5 (Pohst-Zassenhaus)   Let $\O$ be an order in the the ring of integers $\O_K$ of a number field, let $p\in\mathbf{Z}$ be a prime, and let

$$I_p = \{x \in \O: x^m \in p\O$$ for some $m&ge#geq;1$ $$\} \subset \O$$

be the radical of $p\O$, which is an ideal of $\O$. Let

$$\O' = \{x \in K : xI_p \subset I_p\}.$$

Then $\O'$ is an order and either $\O'=\O$, in which case $\O$ is $p$-maximal, or $\O\subset\O'$ and $p$ divides $[\O':\O]$.

Proof. We prove here only that $[\O':\O] \mid p^n$, where $n$ is the degree of $K$. We have $p\in I_p$, so if $x \in \O'$, then $xp \in I_p\subset \O$, which implies that $x\in \frac{1}{p}\O$. Since $(\frac{1}{p}\O)/\O$ is of order $p^n$, the claim follows.

To complete the proof, we would show that if $\O'=\O$, then $\O$ is already $p$-maximal. See [Coh93, §6.1.1] for the rest if this proof. $\qedsymbol$

After deciding on how to represent elements of $K$ and orders and ideals in $K$, one can give an efficient algorithm to compute the $\O'$ of the theorem. The algorithm mainly involves linear algebra over finite fields. It is complicated to describe, but efficient in practice, and is conceptually simple--just compute $\O'$. The trick for reducing the computation of $\O'$ to linear algebra is the following lemma:

Lemma 4.3.6   Define a homomorphism $\psi:\O\hookrightarrow \End (I_p/ p I_p)$ given by sending $\alpha\in\O$ to left multiplication by the reduction of $\alpha$ modulo $p$. Then

$$\O'=\frac{1}{p} \Ker (\psi).$$

Proof. If $x \in \O'$, then $x I_p \subset I_P$, so $\psi(x)$ is the 0 endomorphism. Conversely, if $\psi(x)$ acts as 0 on $I_p/ p I_p$, then clearly $x I_p \subset I_p$. $\qedsymbol$

Note that to give an algorithm one must also figure out how to explicitly compute $I_p/ p I_p$ and the kernel of this map (see the next section for more details).