## A Method for Factoring 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 .

The cover is easy to understand because it is defined by the single equation . 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 8.1.2   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 factorization of .

Proof. Hi-brow argument: 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 , so .
Low-brow argument: The inclusion map is defined by a matrix over that has determinant , which is coprime to . The reduction of this matrix modulo  is invertible, so it defines an isomorphism . Any homomorphism is the composition of a homomorphism with a homomorphism . Since , the homomorphisms are in bijection with the homomorphisms , which proves the lemma.

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

We formalize the above discussion in the following theorem:

Theorem 8.1.3   Let denote 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 , the maximal order has discriminant :

   > Discriminant(MaximalOrder(K));
2945785

The order has the same discriminant as , so and we can apply the above theorem.
   > 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.

   > f:=MinimalPolynomial(7*a);
> f;
x^5 + 49*x^4 + 1029*x^2 - 2401*x + 16807
> Discriminant(f);
235050861175510968365785
> Discriminant(f)/Discriminant(MaximalOrder(K));
79792266297612001    // coprime to 5
> S<t> := PolynomialRing(GF(5));
> Factorization(S!f);
[
<t + 1, 2>,
<t + 4, 1>,
<t^2 + 3*t + 3, 1>
]

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 .
   > f:=MinimalPolynomial(5*a);
> f;
x^5 + 35*x^4 + 375*x^2 - 625*x + 3125
> Discriminant(f) / Discriminant(MaximalOrder(K));
95367431640625    // divisible by 5
> Factorization(S!f);
[
<t, 5>
]


William Stein 2004-05-06