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

Leave a Reply

Your email address will not be published. Required fields are marked *