Factoring over a finite field

Let be a polynomial in . The idea is to try to find a polynomial such that is of deg . This is then a factor of .

A basic fact here is the following result.

Theorem 2.4.10   If is an irreducible polynomial of degree in then there is an such that divides . In fact, one may take .

The smallest satisfying Theorem 2.4.10 is called the order of mod .

This theorem suggests the following strategy to factor a polynomial over the finite field , one may use the following procedure.

• Eliminate any multiple factors by dividing by , as in Lemma 2.4.6. Let denote the resulting quotient.
• Let .
• Compute . If this gcd is not equal to and if , replace by , replace by , and go to the previous step. If , stop. If but the gcd equals then replace by , and go to the previous step.

Example 2.4.11   Let and , so . We have . Since is irreducible, the method above has completely factored.

Exercise 2.4.12   Factor all monic polynomials of degree in .

Exercise 2.4.13   Factor all monic polynomials of degree in .

Exercise 2.4.14   Factor all monic polynomials of degree in .

Exercise 2.4.15   Prove Lemma 2.4.2.

Exercise 2.4.16   Find all the irreducible polynomials of degree over .

Exercise 2.4.17   Find all the irreducible polynomials of degree over .

Exercise 2.4.18   Find all the irreducible polynomials of degree over .

Exercise 2.4.19   Factor in .

Exercise 2.4.20   Factor in .

Exercise 2.4.21   Factor in .

Exercise 2.4.22   Let be any field. Show that there are infinitely many irreducible polynomials in . (Hint: Think of the polynomial analog of Euclid's second theorem (Theorem 1.5.1).)

Exercise 2.4.23   Find if in has a multiple root or not.

Exercise 2.4.24   Find if in has a multiple root or not.

Exercise 2.4.25   Find if in has a multiple root or not.

Exercise 2.4.26   Find if in has a multiple root or not.

Exercise 2.4.27   Find an such that divides in . (This illustrates Theorem 2.4.10.)

david joyner 2008-04-20