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 $P(x)$ over the field $K[x]$ of degree $n$ is a polynomial $Q(x)$ over the field $K[x]$ of degree less than $n$ which can be multiplied by another polynomial $R(x)$ over a field $K[x]$ of degree less than $n$ to yield $P(x)$ i.e. a polynomial $Q(x)$ such that

$P(x)=Q(x)R(x)$

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

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

so both $(x+1)$ and $(x-1)$ are factors of $x^{2}-1$ over the field $R[x]$.

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 $p^{r}$, there exists exactly one finite field with $p^{r}$ elements (up to isomorphism). This field is denoted $GF(p^{r})$ or $\mathbb {F} _{p^{r}}$ (also written as $F_{p^{r}}$ when there are typesetting limitations). $GF(p)$ is called the prime field of order $p$, and is the field of residual classes modulo $p$, where the $p$ elements are denoted $0,1,...p-1$. a=b in $GF(p)$ means the same as $a\equiv b{\bmod {p}}$.

Note: $GF(p)$ is a common notation of finite field with $p$ elements, where $G$ stands for Galois and $F$ stands for a Field. The F in $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 $n$ can be done in $O(n^{2})$ operations in $F_{q}$ using "classical" arithmetic, or in $O(n\log n\log \log n)$ operations in $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 $n$ can be taken as $O(n^{2})$ operations in $F_{q}$ using classical methods, or as $O(n\log ^{2}n\log \log n)$ operations in $F_{q}$ using fast methods. For polynomials $h$, $g$ of degree at most $n$, the exponentiation $h^{q}modg$ can be done by means of the classical repeated squaring method, with $O(\log q)$ polynomial products, i.e. $O(n^{2}\log q)$ operations in $F_{q}$ using classical methods, or $O(n\log q\log n\log \log n)$ operations in $F_{q}$ using fast methods.

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.

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

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

$P(x)=x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1$ is irreducible over $k=F_{p}$ for prime $p\equiv 3{\bmod {7}}$ or $p\equiv 5{\bmod {7}}$. Note that

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

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

If $P(x)$ had an irreducible quadratic factor $q(x)$ in $k[x]$, then $P(x)=0$ would have a root in a quadratic extension $K$ of $k$. Since $[K:k]=2$, the field $K$ has $p^{2}$ elements, and

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

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

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

By Lagrange, the order of any element of $K^{*}$ is a divisor of $p^{3}-1$, but 7 divides neither $3^{3}-1\equiv 26\equiv 5\mod 7$ nor $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 $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

Example

Let $f(x)\in F_{3}[x]$ be defined by $f(x)=x^{11}+2x^{9}+2x^{8}+x^{6}+x^{5}+2x^{3}+2x^{2}+1$ and $c(x)=\gcd(f(x),f'(x))=x^{9}+2x^{6}+x^{3}+2$. Since g(x)≠0 we have $w(x)=x^{2}+2$ and we enter the while loop. After one loop we have $y(x)=x+2$, $z(x)=x+1$ and Output=$x+1$ with updates $i=2$, $w(x)=x+2$ and $c(x)=x^{8}+x^{7}+x^{6}+x^{2}+x+1$. The second time through the loop gives $y(x)=x+2$, $z(x)=1$, Output=$x+1$, with updates $i=3$, $w(x)=x+2$ and $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 $y(x)=1$, $z(x)=x+2$, Output=$(x+1)(x+2)^{4}$, with updates $i=5$, $w(x)=1$ and $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 $c(x)$ is $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 $f(x)$ as Output=$(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 $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:

For i≥1 the polynomial $x^{q^{i}}-x$ in $F_{q}[x]$ is the product of all monic irreducible polynomials in $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 $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.

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

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

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

Rabin test of irreducibility

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

Let $p_{1},p_{2},\dots ,p_{k},$ be all the prime divisor of $n$, and denote $n/p_{i}=n_{i}$, for 1≤i≤k polynomial $f$ in $F_{q}[x]$of degree $n$ is irreducible in $F_{q}[x]$ if and only if $gcd(f,x^{q^{n/p_{i}}}-x)=1$, for 1≤i≤k, and $f$ divides $x^{q^{n}}-x$.

 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.

Example

Let $q\equiv 1{\bmod {4}}$ and $n=2^{k}$. Take $a\in F_{q}$ to be any quadratic nonresidue. Then $x^{2^{k}}-a$ is irreducible over $F_{q}$ for all 0≤$k$. For instance:

i. if $q\equiv p\equiv 3{\bmod {8}}$ is prime, then take $a=2$;

ii. if $q\equiv p\equiv 5{\bmod {1}}2$ is a prime, then take $a=3$;

iii. if $q\equiv p\equiv 2{\bmod {5}}$ is a prime, then take $a=5$;

See also

• Berlekamp's algorithm
• Cantor–Zassenhaus algorithm
• Polynomial factorization

References

• KEMPFERT,H (1969)On the Factorization of Polynomials Department of Mathematics, The Ohio State University,Columbus,Ohio 43210
• Shoup,Victor (1996) Smoothness and Factoring Polynomials over Finite Fields Computer Science Department University of Toronto
• Von Zur Gathen, J., Panario, D. (2001)Factoring Polynomials Over Finite Fields: A Survey . Fachbereich Mathematik-Informatik, Universitat Paderborn. Department of Computer Science, University of Toronto.
• Gao Shuhong, Panario Daniel,Test and Construction of Irreducible Polynomials over Finite Fields Department of mathematical Sciences, Clemson University, South Carolina, 29634-1907, USA. and Department of computer science University of Toronto, Canada M5S-1A4
• Shoup, Victor (1989) New Algorithms for Finding Irreducible Polynomials over Finite Fields Computer Science Department University of Wisconsin-Madison
• Geddes, K.O. (1990)Algorithms for Computer Algebra

External links

• Some irreducible polynomials http://www.math.umn.edu/~garrett/m/algebra/notes/07.pdf
• Field and Galois Theory :http://www.jmilne.org/math/CourseNotes/FT.pdf
• Galois Field:http://designtheory.org/library/encyc/topics/gf.pdf
• Factoring polynomials over finite fields: http://www.science.unitn.it/~degraaf/compalg/polfact.pdf