# 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

$P(x)=Q(x)R(x)$ $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.

## Irreducible polynomials

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

For prime power $q$ and an integer 2≤ $n$ , let $F_{q}$ be a finite field with $q$ elements, and $F_{q^{n}}$ be its extension of degree $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

$x^{7}-1$ =$(x-1)(x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1)$ $|K^{*}|$ =$p^{2}-1=(p-1)(p+1)$ $|K*|=p^{3}-1$ 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 $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 $F_{q}$ of order $q=p^{m}$ with $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) $\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 · $z(x)^{i}$ ; i←i+1
w(x)←y(x); c(x)←c(x)/y(x) }
if c(x)≠1 then {
$c(x)\leftarrow c(x)^{1/p}$ Output←Output · $Square-freeFF(c(x))^{p}$ }
else {
$f(x)\leftarrow f(x)^{1/p}$ Output←Output · $Square-freeFF(f(x))^{p}$ }}
end


### Distinct-degree factorization

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

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

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


The algorithm is based on the following fact:

### 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 $f$ over a finite field $F_{q}$ of degree $n$ with r≥2 irreducible factors $f_{1},...,f_{r}$ each of degree $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 $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 $d$ and $n$ , a monic squarefree polynomial $f$ in $F_{q}[x]$ of degree $n=rd$ with r ≥ 2 irreducible factors each of degree $d$ , and the maximum number of iterations t.
Output: The set of monic irreducible factors of $f$ , or "failure".

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

## Rabin test of irreducibility

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

 Algorithm: Rabin Irreducibility Test
Input:  A monic polynomial $f\in F_{q}[x]$ of degree n, and $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
$n_{j}=n/p_{j}$ ;
for i:=1 to k do
h:=$x^{q^{n_{i}}}-x{\bmod {f}}$ ;
g:=$\gcd(f,h)$ ;
if g≠1, then 'f is reducible' and STOP;
endfor;
g:= $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 $x^{q^{n_{i}}}{\bmod {f}}$ starting from the smallest $n_{1},n_{2},...n_{k}$ by repeated squaring or using the Frobenius automorphism, and then to take the correspondent gcd. This needs $O(nM(n)\log n\log q)$ operations in $F_{q}$ , where $M(n)=n\log n\log \log n$ gives the costs of multiplication of polynomials of degree n.