Another cool problem in computational number theory is how to factor a polynomial with coefficients in a finite field. Recall that for a field $K$, the ring $K[X]$ of polynomials in one indeterminate with coefficients in $K$ is a unique factorisation domain (UFD), which means that every polynomial of $K[X]$ can be factored as a product of irreducible polynomials and that this factorisation is unique up to order and unit factors. We are interested in finding a complete factorisation of a polynomial when $K$ is a finite field. Like primality testing, this involves several algorithms which must be run successively, so in this first post I will give an overview of each one, and I will describe them in detail in later posts.

For simplicity, we will work only over *prime* finite fields (*i.e.*, fields of the form $\mathbf{F}_p$ for a prime $p$). In all of the following, let $A \in \mathbf{F}_p$ be the polynomial we wish to factor. Since we are over a field, we can assume without loss of generality that $A$ is monic (multiply it by a suitable constant if it is not).

### 1. Squarefree factorisation

A polynomial $P$ is said to be *squarefree* if its factorisation into irreducible polynomials has no repeated factor. In other words, if there is no non-constant polynomial $Q$ such that $Q^2$ divides $P$. (This definition can naturally be extended to elements in any UFD, so in particular one also often speaks of *squarefree integers*.)

The first step to factor $A$ is to obtain a *squarefree factorisation* of $A$. This means that we wish to obtain polynomials $A_1,A_2,\dots,A_k \in \mathbf{F}_p[X]$ such that the $A_i$ are all squarefree and relatively prime, and

\[ A = A_1A_2^2 \dots A_k^k. \]

One way to obtain such a factorisation is to group together all the irreducible factors of $A$ which have the same exponent. For example, consider the polynomial

\[ \begin{align*}

A &= X^{13} + 2X^{12} + X^{11} + X^{10} + 3X^9 + X^8 + X^7 \\

&\ \ {}+{} 4X^6 + X^5 + 2X^3 + 4X^2 + 4X + 1 \in \mathbf{F}_5[X].

\end{align*} \]

This polynomial factors into

\[ A = (X+1) (X+2)^2 (X+3)^2 (X^2+X+1) (X^3+X+1)^2, \]

and so in our squarefree factorisation, we will have

\[\begin{align*}

A_1 &= (X+1) (X^2+X+1) \\

&= X^3 + 2X^2 + 2X + 1,

\end{align*} \]

and

\[ \begin{align*}

A_2 &= (X+2) (X+3) (X^3+X+1) \\

&= X^5 + 2X^3 + X^2 + X + 1.

\end{align*} \]

Since the $A_i$ are products of distinct irreducible polynomials, they are obviously squarefree and relatively prime. Of course, we do not know in advance what the irreducible factors are; the squarefree factorisation algorithm will only give us the expanded values of the $A_i$, we must then factor them further.

I describe the squarefree factorisation algorithm here.

### 2. Distinct degree factorisation

The next step is to factor each of the $A_i$ as

\[ A_i = A_{i,1}A_{i,2} \dots A_{i,\ell}, \]

where each $A_{i,d}$ is the product of the irreducible factors of $A_i$ which have degree $d$. Continuing with the example above, we will have

\[ \begin{align*}

A_{1,1} &= X+1, \\

A_{1,2} &= X^2+X+1, \\

A_{2,1} &= (X+2) (X+3) \\

&= X^2+1, \\

A_{2,3} &= X^3+X+1.

\end{align*} \]

I describe the distinct degree factorisation algorithm here.

### 3. Final splitting

Finally, the last algorithm factors each $A_{i,d}$ into $\deg(A_{i,d})/d$ irreducible factors of degree $d$. We then have a complete factorisation of $A$, including the exponents of each factor (they are given by $i$).

I describe one possible algorithm for the final splitting, due to Cantor and Zassenhaus, here. Another algorithm exists, due to Berlekamp (maybe later).