# A Method for Factoring Primes that Often Works

Suppose is such that , and let be the minimal polynomial of . Then , and we have a diagram of schemes

where is the factorization of the image of in , and is the factorization of in terms of prime ideals of . On the level of rings, the bottom horizontal map is the quotient map . The middle horizontal map is induced by

and the top horizontal map is induced by

where the isomorphism is by the Chinese Remainder Theorem, which we will prove in Chapter 5. The left vertical maps come from the inclusions

and the right from the inclusions .

The cover is easy to understand because it is defined by the single equation , in the sense that . To give a maximal ideal  of such that is the same as giving a homomorphism up to automorphisms of the image, which is in turn the same as giving a root of  in up to automorphism, which is the same as giving an irreducible factor of the reduction of  modulo .

Lemma 4.2.1   Suppose the index of in is coprime to . Then the primes  in the factorization of do not decompose further going from to , so finding the prime ideals of that contain  yields the primes that appear in the factorization of .

Proof. Fix a basis for and for as -modules. Form the matrix  whose columns express each basis element of as a -linear combination of the basis for . Then

is coprime to , by hypothesis. Thus the reduction of  modulo  is invertible, so it defines an isomorphism .

Let denote a fixed algebraic closure of ; thus is an algebraically closed field of characteristic , over which all polynomials in factor into linear factors. Any homomorphism sends  to 0, so is the composition of a homomorphism with a homomorphism . Since , the homomorphisms are in bijection with the homomorphisms . The homomorphisms are in bijection with the roots of the reduction modulo  of the minimal polynomial of  in .

Remark 4.2.2   Here is a high-brow'' proof of Lemma 4.2.1. By hypothesis we have an exact sequence of abelian groups

where is a finite abelian group of order coprime to . Tensor product is right exact, and there is an exact sequence

and (since has no -torsion), so .

As suggested in the proof of the lemma, we find all homomorphisms by finding all homomorphism . In terms of ideals, if is a maximal ideal of , then the ideal of is also maximal, since

where denotes the image of in .

We formalize the above discussion in the following theorem (note: we will not prove that the powers are here):

Theorem 4.2.3   Let be the minimal polynomial of  over  . Suppose that  is a prime. Let

where the are distinct monic irreducible polynomials. Let where is a lift of in . Then

We return to the example from above, in which , where  is a root of . According to SAGE, the ring of integers  has discriminant :

sage: K.<a> = NumberField(x^5 + 7*x^4 + 3*x^2 - x + 1)
sage: D = K.discriminant(); D
2945785
sage: factor(D)
5 * 353 * 1669

The order has the same discriminant as , which is the same as the discriminant of , so and we can apply the above theorem. (Here we use that the index of in is the square of the quotient of their discriminants, a fact we will prove later in Section 6.2.)
sage: R.<x> = QQ[]
sage: discriminant(x^5 + 7*x^4 + 3*x^2 - x + 1)
2945785

We have

which yields the factorization of given before the theorem.

If we replace by , then the index of in will be a power of , which is coprime to , so the above method will still work.

sage: K.<a> = NumberField(x^5 + 7*x^4 + 3*x^2 - x + 1)
sage: f = (7*a).minpoly('x')
sage: f
x^5 + 49*x^4 + 1029*x^2 - 2401*x + 16807
sage: f.disc()
235050861175510968365785
sage: factor(f.disc() / K.disc())
7^20
sage: f.factor_mod(5)
(x + 4) * (x + 1)^2 * (x^2 + 3*x + 3)

Thus factors in as

If we replace by and try the above algorithm with , then the method fails because the index of in is divisible by .
sage: K.<a> = NumberField(x^5 + 7*x^4 + 3*x^2 - x + 1)
sage: f = (5*a).minpoly('x')
sage: f
x^5 + 35*x^4 + 375*x^2 - 625*x + 3125
sage: f.factor_mod(5)
x^5


William Stein 2012-09-24