## Finding a -Maximal Order

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

Theorem 4.3.5 (Pohst-Zassenhaus)   Let be an order in the the ring of integers of a number field, let be a prime, and let for some $m&ge#geq;1$ be the radical of , which is an ideal of . Let Then is an order and either , in which case is -maximal, or and divides .

Proof. We prove here only that , where is the degree of . We have , so if , then , which implies that . Since is of order , the claim follows.

To complete the proof, we would show that if , then is already -maximal. See [Coh93, §6.1.1] for the rest if this proof. After deciding on how to represent elements of and orders and ideals in , one can give an efficient algorithm to compute the 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 . The trick for reducing the computation of to linear algebra is the following lemma:

Lemma 4.3.6   Define a homomorphism given by sending to left multiplication by the reduction of modulo . Then Proof. If , then , so is the 0 endomorphism. Conversely, if acts as 0 on , then clearly . Note that to give an algorithm one must also figure out how to explicitly compute and the kernel of this map (see the next section for more details).

William Stein 2012-09-24