Factoring over a finite field

Let $p(x)$ be a polynomial in ${\mathbb{F}}_p[x]$. The idea is to try to find a polynomial $q(x)$ such that $g(x)=gcd(p(x),q(x))$ is of deg$(g(x))>0$. This is then a factor of $p(x)$.

A basic fact here is the following result.

Theorem 2.4.10   If $p(x)$ is an irreducible polynomial of degree $d$ in ${\mathbb{F}}_p[x]$ then there is an $n>1$ such that $p(x)$ divides $x^n-1$. In fact, one may take $n=p^d-1$.

The smallest $n$ satisfying Theorem 2.4.10 is called the order of $x$ mod $p(x)$.

This theorem suggests the following strategy to factor a polynomial $f(x)$ over the finite field ${\mathbb{F}}_p$, one may use the following procedure.

• Eliminate any multiple factors by dividing $f(x)$ by $gcd(f(x),f'(x))$, as in Lemma 2.4.6. Let $q(x)$ denote the resulting quotient.
• Let $d=1$.
• Compute $gcd(q(x),x^{p^d}-x)$. If this gcd is not equal to $1$ and if $d<deg(q(x))$, replace $q(x)$ by $q(x)/gcd(q(x),x^{p^d}-x)$, replace $d$ by $d+1$, and go to the previous step. If $d\geq deg(q(x))$, stop. If $d<deg(q(x))$ but the gcd equals $1$ then replace $d$ by $d+1$, and go to the previous step.

Example 2.4.11   Let $F={\mathbb{F}}_3$ and $p(x)=(x+2)^3(x^2+1)^5\in F[x]$, so $q(x)=(x+2)(x^2+1)$. We have $gcd(q(x),x^{3^i}-x)\equiv x+2\, ({\rm mod}\, 3)$. Since $q(x)/(x+2)=x^2+1$ is irreducible, the method above has completely factored.

Exercise 2.4.12   Factor all monic polynomials of degree $\leq 4$ in ${\mathbb{F}}_2[x]$.

Exercise 2.4.13   Factor all monic polynomials of degree $\leq 3$ in ${\mathbb{F}}_3[x]$.

Exercise 2.4.14   Factor all monic polynomials of degree $\leq 2$ in ${\mathbb{F}}_5[x]$.

Exercise 2.4.15   Prove Lemma 2.4.2.

Exercise 2.4.16   Find all the irreducible polynomials of degree $\leq 3$ over $\mathbb{F}_2$.

Exercise 2.4.17   Find all the irreducible polynomials of degree $\leq 3$ over $\mathbb{F}_3$.

Exercise 2.4.18   Find all the irreducible polynomials of degree $\leq 2$ over $\mathbb{F}_5$.

Exercise 2.4.19   Factor $x^2+1$ in $\mathbb{F}_2[x]$.

Exercise 2.4.20   Factor $x^3+1$ in $\mathbb{F}_3[x]$.

Exercise 2.4.21   Factor $x^3+2$ in $\mathbb{F}_3[x]$.

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

Exercise 2.4.23   Find if $x^2+x+1$ in $\mathbb{Q}[x]$ has a multiple root or not.

Exercise 2.4.24   Find if $x^2+x+1$ in $\mathbb{F}_3[x]$ has a multiple root or not.

Exercise 2.4.25   Find if $x^4+x^3+x^2+x+1$ in $\mathbb{Q}[x]$ has a multiple root or not.

Exercise 2.4.26   Find if $x^4+x^3+x^2+x+1$ in $\mathbb{F}_5 [x]$ has a multiple root or not.

Exercise 2.4.27   Find an $n>1$ such that $x^3+4x^2+3$ divides $x^n-1$ in $\mathbb{F}_5 [x]$. (This illustrates Theorem 2.4.10.)