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

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

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

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

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

William Stein 2012-09-24