# Polynomial factorisation over finite fields, part 0: Overview

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).

This site uses Akismet to reduce spam. Learn how your comment data is processed.