- The dimension of the kernel of the map is equal to . This is because abstractly we have that , with each a finite field extension of .
- If we are done. Terminate.
- Otherwise, choose with . (Think of as the diagonal embedding of in ). Compute powers of and find the minimal polynomial of .
- Since ( factors), the polynomial is a square-free product of linear factors, that has degree since . Thus we can compute a splitting , where both have positive degree.
- Use the Euclidean algorithm in
to find
and such that
- Let
. Then we have

Given Algorithm 4.3.7, we compute an idempotent , and observe that

- [Check if easy] If (so ), then using Theorem 4.2.3 we factor .
- [Compute radical]
Let be the
*radical*of , which is the ideal of elements such that for some positive integer . Note that , i.e., ; also is the product of the primes that divide , without multiplicity. Using linear algebra over the finite field , we compute a basis for by computing the abelian subgroup of of all nilpotent elements. This computes , since . - [Compute quotient by radical]
Compute an
basis for
- [Decompose quotient] The ring is isomorphic to
the quotient of by a radical ideal,
so it decomposes as a product
of finite fields.
We find such a decomposition explicitly using Algorithm 4.3.7.
- [Compute the maximal ideals over ] Each maximal ideal
lying over is the kernel of one of the compositions

Algorithm 4.3.9 was invented by J. Buchmann and H.W. Lenstra, though their paper seems to have never been published; however, the algorithm is described in detail in [Coh93, §6.2.5]. Incidentally, this chapter is based on Chapters 4 and 6 of [Coh93], which is highly recommended, and goes into much more detail about these algorithms.

William Stein 2012-09-24