# Factorization of polynomials over a finite field and irreducibility tests

Finding the factorization of a polynomial over a finite field is of interest for many applications in computer algebra, coding theory, cryptography and computational number theory. Major improvements have been made in the polynomial factorization problem both in theory and in practice. From a theoretical point of view, asymptotically faster algorithms have been proposed. However, these advances are more striking in practice where variants of the asymptotically fastest algorithms allow us to factor polynomials over finite fields in reasonable amounts of time that were unassailable some years ago. Polynomial factorization over finite fields is used as a subproblem in algorithms for factoring polynomials over the integers, for constructing cyclic redundancy codes and BCH codes, for designing public key cryptosystems, and for computing the number of points on Elliptic curves.

## Introduction

A factor of polynomial ${\displaystyle P(x)}$ over the field ${\displaystyle K[x]}$ of degree ${\displaystyle n}$ is a polynomial ${\displaystyle Q(x)}$ over the field ${\displaystyle K[x]}$ of degree less than ${\displaystyle n}$ which can be multiplied by another polynomial ${\displaystyle R(x)}$ over a field ${\displaystyle K[x]}$ of degree less than ${\displaystyle n}$ to yield ${\displaystyle P(x)}$ i.e. a polynomial ${\displaystyle Q(x)}$ such that

${\displaystyle P(x)=Q(x)R(x)}$

For example, take the polynomial ${\displaystyle P(x)=x^{2}-1}$ over the field ${\displaystyle R[x]}$, then

${\displaystyle x^{2}-1=(x+1)(x-1)}$

## Finite field

The theory of finite fields, whose origins can be traced back to the works of Gauss and Galois, has played a part in various branches of mathematics. Due to the applicability of the concept in other topics of mathematics and sciences like computer science there has been a resurgence of interest in finite fields and this is partly due to important applications in coding theory and cryptography. Applications of finite fields introduce some of these developments in cryptography, computer algebra and coding theory.

A finite field is a field with a finite order and it is also called a Galois field. The order of a finite field is always a prime or a power of prime. For each prime power ${\displaystyle p^{r}}$, there exists exactly one finite field with ${\displaystyle p^{r}}$ elements (up to isomorphism). This field is denoted ${\displaystyle GF(p^{r})}$ or ${\displaystyle \mathbb {F} _{p^{r}}}$ (also written as ${\displaystyle F_{p^{r}}}$ when there are typesetting limitations). ${\displaystyle GF(p)}$ is called the prime field of order ${\displaystyle p}$, and is the field of residual classes modulo ${\displaystyle p}$, where the ${\displaystyle p}$ elements are denoted ${\displaystyle 0,1,...p-1}$. a=b in ${\displaystyle GF(p)}$ means the same as ${\displaystyle a\equiv b{\bmod {p}}}$.

Note: ${\displaystyle GF(p)}$ is a common notation of finite field with ${\displaystyle p}$ elements, where ${\displaystyle G}$ stands for Galois and ${\displaystyle F}$ stands for a Field. The F in ${\displaystyle F_{p}}$ stands for finite field.

## Factorization of polynomials over finite fields

Polynomial factoring algorithms use basic polynomial operations such as products, divisions, gcd, powers of one polynomial modulo another, etc. A multiplication of two polynomials of degree at most ${\displaystyle n}$ can be done in ${\displaystyle O(n^{2})}$ operations in ${\displaystyle F_{q}}$ using "classical" arithmetic, or in ${\displaystyle O(n\log n\log \log n)}$ operations in ${\displaystyle F_{q}}$ using "fast" arithmetic. A division with remainder can be performed within the same time bounds. The cost of a gcd between two polynomials of degree at most ${\displaystyle n}$ can be taken as ${\displaystyle O(n^{2})}$ operations in ${\displaystyle F_{q}}$ using classical methods, or as ${\displaystyle O(n\log ^{2}n\log \log n)}$ operations in ${\displaystyle F_{q}}$ using fast methods. For polynomials ${\displaystyle h}$, ${\displaystyle g}$ of degree at most ${\displaystyle n}$, the exponentiation ${\displaystyle h^{q}modg}$ can be done by means of the classical repeated squaring method, with ${\displaystyle O(\log q)}$ polynomial products, i.e. ${\displaystyle O(n^{2}\log q)}$ operations in ${\displaystyle F_{q}}$ using classical methods, or ${\displaystyle O(n\log q\log n\log \log n)}$ operations in ${\displaystyle F_{q}}$ using fast methods.

## Irreducible polynomials

Irreducible polynomials are useful for several applications: Pseudorandom number generators using feedback shift registers, discrete logarithm over ${\displaystyle F_{2^{n}}}$ and efficient arithmetic in finite fields.

Let ${\displaystyle F}$ be a finite field. A polynomial ${\displaystyle f(x)}$ from ${\displaystyle F[x]}$ that is neither the zero polynomial nor a unit in ${\displaystyle F[x]}$ is said to be irreducible over ${\displaystyle F}$ if, whenever ${\displaystyle f(x)}$ is expressed as a product ${\displaystyle f(x)=g(x)h(x)}$, with ${\displaystyle g(x)}$ and ${\displaystyle h(x)}$ from ${\displaystyle F[x]}$, then ${\displaystyle g(x)}$ or ${\displaystyle h(x)}$ is a unit in ${\displaystyle F[x]}$. A nonzero, non unit element of ${\displaystyle F[x]}$ that is not irreducible over ${\displaystyle F}$ is called reducible over ${\displaystyle F}$.

For prime power ${\displaystyle q}$ and an integer 2≤ ${\displaystyle n}$, let ${\displaystyle F_{q}}$ be a finite field with ${\displaystyle q}$ elements, and ${\displaystyle F_{q^{n}}}$ be its extension of degree ${\displaystyle n}$. One way of constructing an extension of finite field is via an irreducible polynomial over the ground field with degree equal to the degree of the extension. The central idea is to take polynomials at random and test them for irreducibility.

### Example

${\displaystyle x^{7}-1}$=${\displaystyle (x-1)(x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1)}$

The root of ${\displaystyle P(x)=0}$ has order 7 or 1 (for any field). The only element of order 1 is the identity element 1. If ${\displaystyle P(x)}$ had a linear factor in ${\displaystyle k[x]}$, then ${\displaystyle P(x)=0}$ would have a root in k. Since 1+1+1+1+1+1+1≠0 in ${\displaystyle k}$, 1 is not a root, so the other possible root must have order 7. But the order of ${\displaystyle k^{*}=F_{p}^{*}}$ is ${\displaystyle p-1}$, which is not divisible by 7, so there is no root in the base field ${\displaystyle k}$.

${\displaystyle |K^{*}|}$=${\displaystyle p^{2}-1=(p-1)(p+1)}$

By Lagrange's theorem, the order of any element of ${\displaystyle K^{*}}$ is a divisor of ${\displaystyle p^{2}-1}$, but 7 divides neither ${\displaystyle 3^{2}-1\equiv 8\equiv 1\mod 7}$ nor ${\displaystyle 5^{2}-1\equiv 24\equiv 3\mod 7}$, so there is no element in ${\displaystyle K}$ of order 7. That is, there is no quadratic irreducible factor. If ${\displaystyle P(x)}$ had an irreducible cubic factor ${\displaystyle q(x)}$ in ${\displaystyle k[x]}$, then ${\displaystyle P(x)=0}$ would have a root in a cubic extension ${\displaystyle K}$ of ${\displaystyle k}$. Since ${\displaystyle [K:k]=3}$, the field ${\displaystyle K}$ has ${\displaystyle p^{3}}$ elements, and

${\displaystyle |K*|=p^{3}-1}$

By Lagrange, the order of any element of ${\displaystyle K^{*}}$ is a divisor of ${\displaystyle p^{3}-1}$, but 7 divides neither ${\displaystyle 3^{3}-1\equiv 26\equiv 5\mod 7}$ nor ${\displaystyle 5^{3}-1\equiv -8\equiv -1\mod 7}$, so there is no element in K of order 7. That is, there is no cubic irreducible factor.

By additivity of degrees in products, lack of factors up to half the degree of a polynomial assures that the polynomial is irreducible. Thus, since the sextic ${\displaystyle x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1}$ has no linear, quadratic, or cubic factors, it is irreducible.

## Factoring algorithms

Many algorithms for factoring polynomials over finite fields include the following three stages:

### Square-free factorization

The algorithm determines a square-free factorization for polynomials whose coefficients come from the finite field ${\displaystyle F_{q}}$ of order ${\displaystyle q=p^{m}}$ with ${\displaystyle p}$ a prime. This algorithm firstly determines the derivative and then computes the gcd of the polynomial and its derivative. If it is not one then the gcd is again divided into the original polynomial, provided that the derivative is not zero (a case that exists for non-constant polynomials defined over finite fields).

  Algorithm: Square-free Factorization (SFF)
Input: A monic polynomial f(x) ${\displaystyle \in F_{q}[x]}$
Output: Square-free factorization of f(x)

  i←1; Output←1; g(x)←ƒ′(x);
if g(x)≠0 then {
c(x)←gcd(f(x), g(x));
w(x)←f(x)/c(x);
while w(x)≠1 do {
y(x)←gcd(w(x), c(x)); z(x)←w(x)/y(x)
Output←Output · ${\displaystyle z(x)^{i}}$; i←i+1
w(x)←y(x); c(x)←c(x)/y(x) }
if c(x)≠1 then {
${\displaystyle c(x)\leftarrow c(x)^{1/p}}$
Output←Output · ${\displaystyle Square-freeFF(c(x))^{p}}$}
else {
${\displaystyle f(x)\leftarrow f(x)^{1/p}}$
Output←Output · ${\displaystyle Square-freeFF(f(x))^{p}}$}}
end


### Example

Let ${\displaystyle f(x)\in F_{3}[x]}$ be defined by ${\displaystyle f(x)=x^{11}+2x^{9}+2x^{8}+x^{6}+x^{5}+2x^{3}+2x^{2}+1}$ and ${\displaystyle c(x)=\gcd(f(x),f'(x))=x^{9}+2x^{6}+x^{3}+2}$. Since g(x)≠0 we have ${\displaystyle w(x)=x^{2}+2}$ and we enter the while loop. After one loop we have ${\displaystyle y(x)=x+2}$, ${\displaystyle z(x)=x+1}$ and Output=${\displaystyle x+1}$ with updates ${\displaystyle i=2}$, ${\displaystyle w(x)=x+2}$ and ${\displaystyle c(x)=x^{8}+x^{7}+x^{6}+x^{2}+x+1}$. The second time through the loop gives ${\displaystyle y(x)=x+2}$, ${\displaystyle z(x)=1}$, Output=${\displaystyle x+1}$, with updates ${\displaystyle i=3}$, ${\displaystyle w(x)=x+2}$ and ${\displaystyle c(x)=x^{7}+2x^{6}+x+2}$. The third time through the loop also does not change Output. For the fourth time through the loop we get ${\displaystyle y(x)=1}$, ${\displaystyle z(x)=x+2}$, Output=${\displaystyle (x+1)(x+2)^{4}}$, with updates ${\displaystyle i=5}$, ${\displaystyle w(x)=1}$ and ${\displaystyle c(x)=x^{6}+1}$. Since w(x)=1, we exit the while loop. Since c(x)≠1, it must be a perfect cube. The cube root of ${\displaystyle c(x)}$ is ${\displaystyle x^{2}+1}$, and calling the square-free procedure recursively determines that it is square-free. Therefore, cubing the resulting square-free factorization and combining it with the output to that point gives the square-free decomposition of ${\displaystyle f(x)}$ as Output=${\displaystyle (x+1)(x^{2}+1)^{3}(x+2)^{4}}$.

### Distinct-degree factorization

This algorithm splits a square-free polynomial into a product of polynomials whose irreducible factors all have the same degree. Let ${\displaystyle f(x)\in F_{q}[x]}$ of degree ${\displaystyle n}$ be the polynomial to be factored.

   Algorithm: Distinct-degree factorization(DDF)
Input: A monic square-free polynomial ${\displaystyle f(x)\in F_{q}[x]}$
output: The set of all pairs ${\displaystyle (g,d)}$, where ${\displaystyle g}$ is the product of all monic
irreducible factors of ${\displaystyle f}$ of degree ${\displaystyle d}$, with ${\displaystyle g\neq 1}$.

       i:=1; ${\displaystyle S:=\varnothing }$, ${\displaystyle f^{*}}$:=${\displaystyle f}$;
while ${\displaystyle \deg f^{*}\geq 2i}$ do
${\displaystyle g=\gcd(f^{*},x^{q^{i}}-x)}$
if ${\displaystyle g\neq 1}$, then ${\displaystyle S:=S\cup {(g,i)}}$;
${\displaystyle f^{*}}$:=${\displaystyle {f^{*}}/{g}}$;
i:=i+1;
endwhile;
if ${\displaystyle f^{*}}$ ≠1, then ${\displaystyle S:=S\cup {(f^{*},\deg f^{*})}}$;
return ${\displaystyle S}$.


The algorithm is based on the following fact:

For i≥1 the polynomial ${\displaystyle x^{q^{i}}-x}$ in ${\displaystyle F_{q}[x]}$ is the product of all monic irreducible polynomials in ${\displaystyle F_{q}[x]}$ whose degree divides i.

### Equal degree factorization

This type of algorithm factors a polynomial whose irreducible factors all have the same degree. We concentrate on algorithms for factoring a monic squarefree univariate polynomial ${\displaystyle f}$ over a finite field ${\displaystyle F_{q}}$ of degree ${\displaystyle n}$ with r≥2 irreducible factors ${\displaystyle f_{1},...,f_{r}}$ each of degree ${\displaystyle d}$.

We first describe an algorithm by Cantor and Zassenhaus (1981) and then an algorithm by Shoup (1990). Both algorithms are examples of Equal-degree factorization (EDF) algorithms and both require the field ${\displaystyle F_{q}}$ to have odd characteristic. For more factorization algorithms see e.g. Knuth's book The Art of Computer Programming volume 2.

    Algorithm Cantor-Zassenhaus algorithm.
Input: Integers ${\displaystyle d}$ and ${\displaystyle n}$, a monic squarefree polynomial ${\displaystyle f}$ in ${\displaystyle F_{q}[x]}$ of degree ${\displaystyle n=rd}$ with r ≥ 2 irreducible factors each of degree ${\displaystyle d}$, and the maximum number of iterations t.
Output: The set of monic irreducible factors of ${\displaystyle f}$, or "failure".

    Factors:={${\displaystyle f}$}; k:=1
while k≤t do,
Choose ${\displaystyle h}$ in ${\displaystyle F_{q}[x]}$ with ${\displaystyle \deg h}$ < ${\displaystyle n}$ at random;
${\displaystyle g:=\gcd(h,f)}$;
if g=1, then
g=${\displaystyle h^{(q^{d}-1)/2}-1{\pmod {f}}}$
endif
for each ${\displaystyle u}$ in Factors with ${\displaystyle \deg u>d}$ do
if ${\displaystyle \gcd(g,u)}$≠ 1 and ${\displaystyle \gcd(g,u)}$ ≠u, then
Factors:= Factors \${\displaystyle \{u\}\cup \{(\gcd(g,u),u/\gcd(g,u))\}}$;
endif;
if Size(Factors)=${\displaystyle r}$, then return Factors;
k:=k+1;
endwhile
return 'failure'.


### Factoring method by Victor Shoup

For this algorithm, the input is restricted to polynomials over prime fields ${\displaystyle F_{p}}$ with p>2. Like the Cantor-Zassenhaus algorithm, this algorithm is an equal-degree factorization algorithm, but unlike it, Shoup's algorithm is deterministic.

Let ${\displaystyle g=g_{1},g_{2},\dots ,g_{k}}$, where the ${\displaystyle g_{i}}$ are distinct monic irreducible polynomials of degree ${\displaystyle d}$. Let ${\displaystyle m=\deg g=kd}$, for some k>1 and let R=${\displaystyle F_{p}[x]/g(x)}$ and ${\displaystyle x\equiv X\ {\bmod {g}}}$ ϵR. Finally, let ${\displaystyle p_{i}}$ be the natural homomorphism from the ring ${\displaystyle R}$ onto the field ${\displaystyle F_{p}[x]/g_{i}}$.

According to Victor Shoup,[1] this factoring algorithm uses the same subalgebra ${\displaystyle B}$ of ${\displaystyle R}$ as the Berlekamp's algorithm, called the 'Berlekamp subagebra' and defined as B={αϵR: ${\displaystyle p_{i}}$(α) ϵ ${\displaystyle F_{p}}$ for each i=1,...,k. Let a subset S⊂B be called a separating set if for any 1≤i<j≤k there exit s∈S such that ${\displaystyle P_{i}}$(s)≠${\displaystyle P_{j}}$(s). In Shoup's algorithm, the separating set is constructed in the following way. Let ${\displaystyle h(Y)}$${\displaystyle R[Y]}$, where ${\displaystyle h(Y)=(Y-x)(Y-x^{p})...(Y-x^{p^{d-1}})}$. Suppose ${\displaystyle h(Y)=h_{0}+...+h_{d-1}Y^{d-1}+Y^{d}}$. Then ${\displaystyle \{h_{0},\dots ,h_{d-1}\}}$ is a separating set because the image of ${\displaystyle h(Y)}$ under the homomorphism ${\displaystyle p_{i}}$ equals ${\displaystyle g_{i}(Y)}$, for i=1,2,3...k; since the ${\displaystyle g_{i}}$'s are distinct at least one of the coefficients ${\displaystyle h_{l}}$ will be different for every pair ${\displaystyle (g_{i},g_{j})}$ with ${\displaystyle i\neq j}$.

If ${\displaystyle S=\{h_{0},\dots ,h_{d-1}\}}$ is a separating set one can factor ${\displaystyle g}$ using ${\displaystyle S}$ as follows: Let U⊂${\displaystyle Z_{p}}$[x] be a finite partial factorization of ${\displaystyle g}$ consisting of monic polynomials so that ${\displaystyle \prod _{u\in U}u=g}$. Initialize U={g} and let Refine(U,v) give a partial factorization of ${\displaystyle U}$ using a polynomial v∈${\displaystyle F_{p}}$[x] given by ${\displaystyle \bigcup _{u\in U}\{\gcd(u,v),u/\gcd(u,v)\}-{1}}$. For a complete factorization of ${\displaystyle g}$ one executes the refinement step until |U|=k by using s∈S and ${\displaystyle z=0,1,2,\dots ,p-1}$ and replacing ${\displaystyle U}$ with Refine(U,s+z) and then replacing U with Refine(U,${\displaystyle (s+z)^{(p-1)/2}}$ -1)

## Rabin test of irreducibility

The Rabin's algorithm[2] is based on the following fact:

 Algorithm: Rabin Irreducibility Test
Input:  A monic polynomial ${\displaystyle f\in F_{q}[x]}$ of degree n, and ${\displaystyle p_{1},p_{2},\dots ,p_{k}}$ all distinct prime divisors of n.
Output: Either  "f is irreducible" or "f is reducible".

 for j:=1 to k do
${\displaystyle n_{j}=n/p_{j}}$;
for i:=1 to k do
h:=${\displaystyle x^{q^{n_{i}}}-x{\bmod {f}}}$;
g:=${\displaystyle \gcd(f,h)}$;
if g≠1, then 'f is reducible' and STOP;
endfor;
g:= ${\displaystyle x^{q^{n}}-x{\bmod {f}}}$;
if g=0, then "f is irreducible",
else "f is reducible".


The basic idea of this algorithm is to compute ${\displaystyle x^{q^{n_{i}}}{\bmod {f}}}$ starting from the smallest ${\displaystyle n_{1},n_{2},...n_{k}}$ by repeated squaring or using the Frobenius automorphism, and then to take the correspondent gcd. This needs ${\displaystyle O(nM(n)\log n\log q)}$ operations in ${\displaystyle F_{q}}$, where ${\displaystyle M(n)=n\log n\log \log n}$ gives the costs of multiplication of polynomials of degree n.