This page uses content from Wikipedia and is licensed under CC BY-SA.

In mathematics and computer algebra the factorization of a polynomial consists of decomposing it into a product of irreducible factors. This decomposition is theoretically possible and is unique for polynomials with coefficients in any field, but rather strong restrictions on the field of the coefficients are needed to allow the computation of the factorization by means of an algorithm. In practice, algorithms have been designed only for polynomials with coefficients in a finite field, in the field of rationals or in a finitely generated field extension of one of them.

The case of the **factorization of univariate polynomials over a finite field**, which is the subject of this article, is especially important, because all the algorithms (including the case of multivariate polynomials over the rational numbers), which are sufficiently efficient to be implemented, reduce the problem to this case (see Polynomial factorization). It is also interesting for various applications of finite fields, such as coding theory (cyclic redundancy codes and BCH codes), cryptography (public key cryptography by the means of elliptic curves), and computational number theory.

As the reduction of the factorization of multivariate polynomials to that of univariate polynomials does not have any specificity in the case of coefficients in a finite field, only polynomials with one variable are considered in this article.

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 or Galois field is a field with a finite order (number of elements). The order of a finite field is always a prime or a power of prime. For each prime power *q* = *p ^{r}*, there exists exactly one finite field with

Let *F* be a finite field. As for general fields, a non-constant polynomial *f* in *F*[*x*] is said to be irreducible over *F* if it is not the product of two polynomials of positive degree. A polynomial of positive degree that is not irreducible over *F* is called *reducible over* *F*.

Irreducible polynomials allow us to construct the finite fields of non-prime order. In fact, for a prime power *q*, let **F**_{q} be the finite field with *q* elements, unique up to an isomorphism. A polynomial *f* of degree *n* greater than one, which is irreducible over **F**_{q}, defines a field extension of degree *n* which is isomorphic to the field with *q*^{n} elements: the elements of this extension are the polynomials of degree lower than *n*; addition, subtraction and multiplication by an element of **F**_{q} are those of the polynomials; the product of two elements is the remainder of the division by *f* of their product as polynomials; the inverse of an element may be computed by the extended GCD algorithm (see Arithmetic of algebraic extensions).

It follows that, to compute in a finite field of non prime order, one needs to generate an irreducible polynomial. For this, the common method is to take a polynomial at random and test it for irreducibility. For sake of efficiency of the multiplication in the field, it is usual to search for polynomials of the shape *x*^{n} + *ax* + *b*.^{[citation needed]}

Irreducible polynomials over finite fields are also useful for Pseudorandom number generators using feedback shift registers and discrete logarithm over **F**_{2n}.

The number of irreducible monic polynomials of degree *n* over **F**_{p} (for *p* prime) is equal to the necklace counting function *N*_{p}(*n*).^{[citation needed]}

The polynomial *P* = *x*^{4} + 1 is irreducible over **Q** but not over any finite field.

- On any field extension of
**F**_{2},*P*= (*x*+1)^{4}. - On every other finite field, at least one of −1, 2 and −2 is a square, because the product of two non-squares is a square and so we have

- If then
- If then
- If then

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 Euclidean division (division with remainder) can be performed within the same time bounds. The cost of a polynomial greatest common divisor 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}* mod

In the algorithms that follow, the complexities are expressed in terms of number of arithmetic operations in **F**_{q}, using classical algorithms for the arithmetic of polynomials.

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

An important exception is Berlekamp's algorithm, which combines stages 2 and 3.

The Berlekamp's algorithm is historically important as being the first factorization algorithm, which works well in practice. However, it contains a loop on the elements of the ground field, which implies that it is practicable only over small finite fields. For a fixed ground field, its time complexity is polynomial, but, for general ground fields, the complexity is exponential in the size of the ground field.

The algorithm determines a square-free factorization for polynomials whose coefficients come from the finite field **F**_{q} of order *q* = *p ^{m}* with

This algorithm uses the fact that, if the derivative of a polynomial is zero, then it is a polynomial in *x*^{p}, which is, if the coefficients belong to **F**_{p}, the *p*th power of the polynomial obtained by substituting *x* by *x*^{1/p}. If the coefficients do not belong to **F**_{p}, the *p*-th root of a polynomial with zero derivative is obtained by the same substitution on *x*, completed by applying the inverse of the Frobenius automorphism to the coefficients.

This algorithm works also over a field of characteristic zero, with the only difference that it never enters in the blocks of instructions where *p*th roots are computed. However, in this case, Yun's algorithm is much more efficient because it computes the greatest common divisors of polynomials of lower degrees. A consequence is that, when factoring a polynomial over the integers, the algorithm which follows is not used: one compute first the square-free factorization over the integers, and to factor the resulting polynomials, one chooses a *p* such that they remain square-free modulo *p*.

Algorithm:SFF(Square-Free Factorization)Input: A monic polynomialfinF_{q}[x] whereq=p^{m}Output: Square-free factorization offR← 1 # Makewbe the product (without multiplicity) of all factors offthat have # multiplicity not divisible bypc←gcd(f,f′)w←f/c# Step 1: Identify all factors inwi←1whilew≠ 1doy←gcd(w,c)fac←w/yR←R·fac^{i}w←y;c←c/y;i←i+1end while#cis now the product (with multiplicity) of the remaining factors off# Step 2: Identify all remaining factors using recursion # Note that these are the factors offthat have multiplicity divisible bypifc≠ 1thenc←c^{1/p}R←R·SFF(c)^{p}end ifOutput(R)

The idea is to identify the product of all irreducible factors of *f* with the same multiplicity. This is done in two steps. The first step uses the formal derivative of *f* to find all the factors with multiplicity not divisible by *p*. The second step identifies the remaining factors. As all of the remaining factors have multiplicity divisible by *p*, meaning they are powers of *p*, one can simply take the *p*-th square root and apply recursion.

Let

to be factored over the field with three elements.

The algorithm computes first

Since the derivative is non-zero we have *w* = *f*/*c* = *x*^{2} + 2 and we enter the while loop. After one loop we have *y* = *x* + 2, *z* = *x* + 1 and *R* = *x* + 1 with updates *i* = 2, *w* = *x* + 2 and *c* = *x*^{8} + *x*^{7} + *x*^{6} + *x*^{2}+*x*+1. The second time through the loop gives *y* = *x* + 2, *z* = 1, *R* = *x* + 1, with updates *i* = 3, *w* = *x* + 2 and *c* = *x*^{7} + 2*x*^{6} + *x* + 2. The third time through the loop also does not change *R*. For the fourth time through the loop we get *y* = 1, *z* = *x* + 2, *R* = (*x* + 1)(*x* + 2)^{4}, with updates *i* = 5, *w* = 1 and *c* = *x*^{6} + 1. Since *w* = 1, we exit the while loop. Since *c* ≠ 1, it must be a perfect cube. The cube root of *c*, obtained by replacing *x*^{3} by *x* is *x*^{2} + 1, and calling the square-free procedure recursively determines that it is square-free. Therefore, cubing it and combining it with the value of *R* to that point gives the square-free decomposition

This algorithm splits a square-free polynomial into a product of polynomials whose irreducible factors all have the same degree. Let *f* ∈ **F**_{q}[*x*] of degree *n* be the polynomial to be factored.

AlgorithmDistinct-degree factorization(DDF)Input: A monic square-free polynomialf∈F_{q}[x]Output: The set of all pairs (g,d), such thatfhas an irreducible factor of degreedandgis the product of all monic irreducible factors offof degreed.Beginwhiledoifg≠ 1,then;f*:=f*/g;end ifi:=i+1;end while;iff*≠ 1,then;ifS= ∅then return{(f, 1)}else returnSEnd

The correctness of the algorithm is based on the following:

Lemma.Fori≥ 1 the polynomial

is the product of all monic irreducible polynomials in

F_{q}[x] whose degree dividesi.

At first glance, this is not efficient since it involves computing the GCD of polynomials of a degree which is exponential in the degree of the input polynomial. However

may be replaced by

Therefore, we have to compute:

there are two methods:

Method I.Start from the value of

computed at the preceding step and to compute its

q-th power modulo the newf*, using exponentiation by squaring method. This needs

arithmetic operations in

F_{q}at each step, and thus

arithmetic operations for the whole algorithm.

Method II.Using the fact that theq-th power is a linear map overF_{q}we may compute its matrix with

operations. Then at each iteration of the loop, compute the product of a matrix by a vector (with

O(deg(f)^{2}) operations). This induces a total number of operations inF_{q}which is

Thus this second method is more efficient and is usually preferred. Moreover, the matrix that is computed in this method is used, by most algorithms, for equal-degree factorization (see below); thus using it for the distinct-degree factorization saves further computing time.

In this section, we consider the factorization of a monic squarefree univariate polynomial *f*, of degree *n*, over a finite field **F**_{q}, which has *r* ≥ 2 pairwise distinct irreducible factors each of degree *d*.

We first describe an algorithm by Cantor and Zassenhaus (1981) and then a variant that has a slightly better complexity. Both are probabilistic algorithms whose running time depends on random choices (Las Vegas algorithms), and have a good average running time. In next section we describe an algorithm by Shoup (1990), which is also an equal-degree factorization algorithm, but is deterministic. All these algorithms require an odd order *q* for the field of coefficients. For more factorization algorithms see e.g. Knuth's book The Art of Computer Programming volume 2.

Algorithm Cantor–Zassenhaus algorithm. Input: A finite fieldF_{q}of odd orderq. A monic square free polynomialfinF_{q}[x] of degreen=rd, which hasr≥ 2 irreducible factors each of degreedOutput: The set of monic irreducible factors off.

Factors:={f}; while Size(Factors) <rdo, ChoosehinF_{q}[x] with deg(h) <nat random; for eachuin Factors with deg(u) >ddo if gcd(g,u) ≠ 1 and gcd(g,u) ≠u, then Factors:= Factors; endif; endwhile return Factors.

The correctness of this algorithm relies on the fact that the ring **F**_{q}[*x*]/*f* is a direct product of the fields **F**_{q}[*x*]/*f _{i}* where

This implies that the polynomial gcd(*g*, *u*) is the product of the factors of *g* for which the component of *g* is zero.

It has been shown that the average number of iterations of the while loop of the algorithm is less than , giving an average number of arithmetic operations in **F**_{q} which is .^{[1]}

In the typical case where *d*log(*q*) > *n*, this complexity may be reduced to

by choosing *h* in the kernel of the linear map

and replacing the instruction

by

The proof of validity is the same as above, replacing the direct product of the fields **F**_{q}[*x*]/*f _{i}* by the direct product of their subfields with

Like the algorithms of the preceding section, Victor Shoup's algorithm is an equal-degree factorization algorithm.^{[2]} Unlike them, it is a deterministic algorithm. However, it is less efficient, in practice, that the algorithms of preceding section. For Shoup's algorithm, the input is restricted to polynomials over prime fields **F**_{p}.

The worst case time complexity of Shoup's algorithm has a factor Although exponential, this complexity is much better that previous deterministic algorithms (Berlekamp's algorithm) which have *p* as a factor. However, there are very few polynomials for which the computing time is exponential, and the average time complexity of the algorithm is polynomial in where *d* is the degree of the polynomial, and *p* is the number of elements of the ground field.

Let *g* = *g*_{1} ... *g _{k}* be the desired factorization, where the

Like in the preceding algorithm, this algorithm uses the same subalgebra *B* of *R* as the Berlekamp's algorithm, sometimes called the "Berlekamp subagebra" and defined as

A subset *S* of *B* is said a separating set if, for every 1 ≤ *i* < *j* ≤ *k* there exists *s* ∈ *S* such that . In the preceding algorithm, a separating set is constructed by choosing at random the elements of *S*. In Shoup's algorithm, the separating set is constructed in the following way. Let *s* in *R*[*Y*] be such that

Then is a separating set because for *i* =1, ..., *k* (the two monic polynomials have the same roots). As the *g _{i}* are pairwise distinct, for every pair of distinct indexes (

Having a separating set, Shoup's algorithm proceeds as the last algorithm of the preceding section, simply by replacing the instruction "choose at random *h* in the kernel of the linear map " by "choose *h* + *i* with *h* in *S* and *i* in {1, ..., *k*−1}".

As described in previous sections, for the factorization over finite fields, there are randomized algorithms of polynomial time complexity (for example Cantor-Zassenhaus algorithm). There are also deterministic algorithms with a polynomial average complexity (for example Shoup's algorithm).

The existence of a deterministic algorithm with a polynomial worst-case complexity is still an open problem.

Like distinct-degree factorization algorithm, Rabin's algorithm^{[3]} is based on the Lemma stated above. Distinct-degree factorization algorithm tests every *d* not greater than half the degree of the input polynomial. Rabin's algorithm takes advantage that the factors are not needed for considering fewer *d*. Otherwise, it is similar to distinct-degree factorization algorithm. It is based on the following fact.

Let *p*_{1}, ..., *p _{k}*, be all the prime divisors of

AlgorithmRabin Irreducibility TestInput: A monic polynomialfinF_{q}[x] of degreen,p_{1}, ...,pall distinct prime divisors of_{k}n.Output: Either "fis irreducible" or "fis reducible".Beginforj= 1 tokdo;fori= 1 tokdo;g:= gcd(f,h);ifg≠ 1,then return'f is reducible'and STOP;end for; ;ifg= 0,then return"f is irreducible",else return"fis reducible"end.

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. Using the elementary polynomial arithmetic, the computation of the matrix of the Frobenius automorphism needs operations in **F**_{q}, the computation of

needs *O*(*n*^{3}) further operations, and the algorithm itself needs *O*(*kn*^{2}) operations, giving a total of operations in **F**_{q}. Using fast arithmetic (complexity for multiplication and division, and for GCD computation), the computation of the by repeated squaring is , and the algorithm itself is , giving a total of operations in **F**_{q}.

- 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. Journal of Symbolic Computation, Volume 31, Issues 1-2, January 2001, 3--17.
- 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, Keith O.; Czapor, Stephen R.; Labahn, George (1992). Algorithms for computer algebra. Boston, MA: Kluwer Academic Publishers. pp. xxii+585. ISBN 0-7923-9259-0.

- Some irreducible polynomials [www.math.umn.edu]
- Field and Galois Theory :[www.jmilne.org]
- Galois Field:[designtheory.org]
- Factoring polynomials over finite fields: [www.science.unitn.it]

**^**Flajolet, Philippe; Steayaert, Jean-Marc (1982),*A branching process arising in dynamic hashing, trie searching and polynomial factorization*, Lecture Notes in Comput. Sci.,**140**, Springer, pp. 239–251**^**Victor Shoup, On the deterministic complexity of factoring polynomials over finite fields, Information Processing Letters 33:261-267, 1990**^**Rabin, Michael (1980). "Probabilistic algorithms in finite fields".*SIAM Journal on Computing*.**9**(2): 273–280. CiteSeerX 10.1.1.17.5653 . doi:10.1137/0209024.