## General Factorization Algorithm of Buchman-Lenstra

We finally give an algorithm to factor in general. This is a summary of the algorithm described in more detail in [Coh93, §6.2].

Algorithm 4.3.7 (Factoring a Finite Separable Algebra)   Let be a finite separable algebra over . This algorithm either shows that is a field or finds a nontrivial idempotent in , i.e., an such that with and .
1. 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 .
2. If we are done. Terminate.
3. Otherwise, choose with . (Think of as the diagonal embedding of in ). Compute powers of and find the minimal polynomial of .
4. 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.
5. Use the Euclidean algorithm in to find and such that

6. Let . Then we have

so since , we have . Also, since , we have and .

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

Since , we see that , so that the sume of the two kernels equals . Also, if is in the intersection of the two kernels, then and , so , so the sum is direct.

Remark 4.3.8   The beginning of [Coh93, §6.2.4] suggests that one can just randomly find an such that where is the minimal polynomial of . This is usually the case, but is wrong in general, since there need not be an such that . For example, let and be as in Example 4.3.2. Then , which as a ring is not generated by a single element, since there are only 2 distinct linear polynomials over .

Algorithm 4.3.9 (Factoring a General Prime Ideal)   Let be a number field given by an algebraic integer  as a root of its minimal monic polynomial  of degree . We assume that an order has been given by a basis and that  that contains . For any prime , the following algorithm computes the set of maximal ideals of  that contain .
1. [Check if easy] If (so ), then using Theorem 4.2.3 we factor .
2. [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 .
3. [Compute quotient by radical] Compute an basis for

The second equality comes from the fact that . Note that is obtained by simply reducing the basis modulo . Thus this step entirely involves linear algebra modulo .

4. [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.

5. [Compute the maximal ideals over ] Each maximal ideal lying over  is the kernel of one of the compositions

Algorithm 4.3.9 finds all primes of that contain the radical of . Every such prime clearly contains , so to see that the algorithm is correct, we prove that the primes of that contain  also contain . If is a prime of that contains , then . If then for some , so which implies that by primality of . Thus contains , as required. Note that we do not find the powers of primes that divide in Algorithm 4.3.9; that's left to another algorithm that we will not discuss in this book.

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