Factorization of polynomials over a finite field and irreducibility tests

From formulasearchengine
Jump to navigation Jump to search

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.


A factor of polynomial over the field of degree is a polynomial over the field of degree less than which can be multiplied by another polynomial over a field of degree less than to yield i.e. a polynomial such that

For example, take the polynomial over the field , then

so both and are factors of over the field .

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 , there exists exactly one finite field with elements (up to isomorphism). This field is denoted or (also written as when there are typesetting limitations). is called the prime field of order , and is the field of residual classes modulo , where the elements are denoted . a=b in means the same as .

Note: is a common notation of finite field with elements, where stands for Galois and stands for a Field. The F in 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 can be done in operations in using "classical" arithmetic, or in operations in 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 can be taken as operations in using classical methods, or as operations in using fast methods. For polynomials , of degree at most , the exponentiation can be done by means of the classical repeated squaring method, with polynomial products, i.e. operations in using classical methods, or operations in using fast methods.

Irreducible polynomials

Irreducible polynomials are useful for several applications: Pseudorandom number generators using feedback shift registers, discrete logarithm over and efficient arithmetic in finite fields.

Let be a finite field. A polynomial from that is neither the zero polynomial nor a unit in is said to be irreducible over if, whenever is expressed as a product , with and from , then or is a unit in . A nonzero, non unit element of that is not irreducible over is called reducible over .

For prime power and an integer 2≤ , let be a finite field with elements, and be its extension of degree . 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.


is irreducible over for prime or . Note that


The root of has order 7 or 1 (for any field). The only element of order 1 is the identity element 1. If had a linear factor in , then would have a root in k. Since 1+1+1+1+1+1+1≠0 in , 1 is not a root, so the other possible root must have order 7. But the order of is , which is not divisible by 7, so there is no root in the base field .

If had an irreducible quadratic factor in , then would have a root in a quadratic extension of . Since , the field has elements, and


By Lagrange's theorem, the order of any element of is a divisor of , but 7 divides neither nor , so there is no element in of order 7. That is, there is no quadratic irreducible factor. If had an irreducible cubic factor in , then would have a root in a cubic extension of . Since , the field has elements, and

By Lagrange, the order of any element of is a divisor of , but 7 divides neither nor , 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 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 of order with 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) 
  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));
     while w(x)≠1 do {
           y(x)←gcd(w(x), c(x)); z(x)←w(x)/y(x)
           Output←Output · ; i←i+1 
           w(x)←y(x); c(x)←c(x)/y(x) }
     if c(x)≠1 then {
           Output←Output · }
  else {
           Output←Output · }}


Let be defined by and . Since g(x)≠0 we have and we enter the while loop. After one loop we have , and Output= with updates , and . The second time through the loop gives , , Output=, with updates , and . The third time through the loop also does not change Output. For the fourth time through the loop we get , , Output=, with updates , and . Since w(x)=1, we exit the while loop. Since c(x)≠1, it must be a perfect cube. The cube root of is , 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 as Output=.

Distinct-degree factorization

This algorithm splits a square-free polynomial into a product of polynomials whose irreducible factors all have the same degree. Let of degree be the polynomial to be factored.

   Algorithm: Distinct-degree factorization(DDF)
   Input: A monic square-free polynomial 
   output: The set of all pairs , where  is the product of all monic
   irreducible factors of  of degree , with .
       i:=1; , :=;
       while  do 
           if , then ;
       if  ≠1, then ;
       return .

The algorithm is based on the following fact:

For i≥1 the polynomial in is the product of all monic irreducible polynomials in 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 over a finite field of degree with r≥2 irreducible factors each of degree .

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 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  and , a monic squarefree polynomial  in  of degree  with r ≥ 2 irreducible factors each of degree , and the maximum number of iterations t.
    Output: The set of monic irreducible factors of , or "failure".
    Factors:={}; k:=1
    while k≤t do,
       Choose  in  with  <  at random;
       if g=1, then 
       for each  in Factors with  do
           if ≠ 1 and  ≠u, then
             Factors:= Factors \;
       if Size(Factors)=, then return Factors;
    return 'failure'.

Factoring method by Victor Shoup

For this algorithm, the input is restricted to polynomials over prime fields 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 , where the are distinct monic irreducible polynomials of degree . Let , for some k>1 and let R= and ϵR. Finally, let be the natural homomorphism from the ring onto the field .

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

If is a separating set one can factor using as follows: Let U⊂[x] be a finite partial factorization of consisting of monic polynomials so that . Initialize U={g} and let Refine(U,v) give a partial factorization of using a polynomial v∈[x] given by . For a complete factorization of one executes the refinement step until |U|=k by using s∈S and and replacing with Refine(U,s+z) and then replacing U with Refine(U, -1)

Rabin test of irreducibility

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

Let be all the prime divisor of , and denote , for 1≤i≤k polynomial in of degree is irreducible in if and only if , for 1≤i≤k, and divides .

 Algorithm: Rabin Irreducibility Test
 Input:  A monic polynomial  of degree n, and  all distinct prime divisors of n.
 Output: Either  "f is irreducible" or "f is reducible".
 for j:=1 to k do 
 for i:=1 to k do
     if g≠1, then 'f is reducible' and STOP;
 g:= ;
 if g=0, then "f is irreducible", 
         else "f is reducible".

The basic idea of this algorithm is to compute starting from the smallest by repeated squaring or using the Frobenius automorphism, and then to take the correspondent gcd. This needs operations in , where gives the costs of multiplication of polynomials of degree n.


Let and . Take to be any quadratic nonresidue. Then is irreducible over for all 0≤. For instance:

i. if is prime, then take ;

ii. if is a prime, then take ;

iii. if is a prime, then take ;

See also


  • 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


  1. Victor Shoup, On the deterministic complexity of factoring polynomials over finite fields, Information Processing Letters 33:261-267, 1990
  2. {{#invoke:Citation/CS1|citation |CitationClass=journal }}