##

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:

*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:

*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