5.3. 5.3 Factoring polynomials over finite fields

One of the problems that we often have to solve when performing symbolic computation is the factorisation problem. Factoring an algebraic expression means writing it as a product of simpler expressions. Experience shows that this can be very helpful in the solution of a large variety of algebraic problems. In this section, we consider a class of factorisation algorithms that can be used to factor polynomials in one variable over finite fields.

The input of the polynomial factorisation problem is a polynomial . Our aim is to compute a factorisation

of where the polynomials are pairwise relatively prime and irreducible over , and the exponents are positive integers. By Theorem 5.4, determines the polynomials and the exponents essentially uniquely.

Example 5.3 Let and let

Then it is easy to compute modulo 23 that

None of the factors , , has a root in , and so they are necessarily irreducible in .

The factorisation algorithms are important computational tools, and so they are implemented in most of the computer algebra systems (Mathematica, Maple, etc). These algorithms are often used in the area of error-correcting codes and in cryptography.

Our aim in this section is to present some of the basic ideas and building blocks that can be used to factor polynomials over finite fields. We will place an emphasis on the existence of polynomial time algorithms. The discussion of the currently best known methods is, however, outside the scope of this book.

5.3.1. 5.3.1 Square-free factorisation

The factorisation problem in the previous section can efficiently be reduced to the special case when the polynomial to be factored is square-free; that is, in (5.3), for all . The basis of this reduction is Lemma 5.13 and the following simple result. Recall that the derivative of a polynomial is denoted by .

Lemma 5.34 Let be a polynomial. If , then there exists a polynomial such that .

Proof. Suppose that . Then . If the coefficient is zero in then either or . Hence, if then can be written as . Let ; then choosing , we have , and so .

If , then, using the previous lemma, a factorisation of into square-free factors can be obtained from that of the polynomial , which has smaller degree. On the other hand, if , then, by Lemma 5.13, the polynomial is already square-free and we only have to factor into square-free factors. The division of polynomials and computing the greatest common divisor can be performed in polynomial time, by Theorem 5.12. In order to compute the polynomial , we need the solutions, in , of equations of the form with . If , then is a solution of such an equation, which, using fast exponentiation (repeated squaring, see 33.6.1), can be obtained in polynomial time.

One of the two reduction steps can always be performed if is divisible by a square of a polynomial with positive degree.

Usually a polynomial can be written as a product of square-free factors in many different ways. For the sake of uniqueness, we define the square-free factorisation of a polynomial as the factorisation

where are integers, and the polynomials are relatively prime and square-free. Hence we collect together the irreducible factors of with the same multiplicity. The following algorithm computes a square-free factorisation of . Besides the observations we made in this section, we also use Lemma 5.14. This lemma, combined with Lemma 5.13, guarantees that the product of the irreducible factors with multiplicity one of a polynomial over a finite field is .

Square-Free-Factorisation( )

  1     2     3     4     5  
                        WHILE
                      
                        6    
                        DO
                      
                     
                        IF
                      
                        7       
                        THEN
                      
                        8             9       
                        ELSE
                      
                       10            11          
                        IF
                      
                       12             
                        THEN
                      
                       13            14  
                        RETURN
                      
                      
                  

The degree of the polynomial decreases after each execution of the main loop, and the subroutines used in this algorithm run in polynomial time. Thus the method above can be performed in polynomial time.

5.3.2. 5.3.2 Distinct degree factorisation

Suppose that is a square-free polynomial. Now we factor as

where, for , the polynomial is a product of irreducible polynomials with degree . Though this step is not actually necessary for the solution of the factorisation problem, it is worth considering, as several of the known methods can efficiently exploit the structure of the polynomials . The following fact serves as the starting point of the distinct degree factorisation.

Theorem 5.35 The polynomial is the product of all the irreducible polynomials , each of which is taken with multiplicity , that have leading coefficient and whose degree divides .

Proof. As , all the irreducible factors of this polynomial occur with multiplicity one. If is irreducible and divides , then, by Theorem 5.24, the degree of divides .

Conversely, let be an irreducible polynomial with degree such that . Then, by Theorem 5.27, has a root in , which implies .

The theorem offers an efficient method for computing the polynomials . First we separate from , and then, step by step, we separate the product of the factors with higher degrees.

Distinct-Degree-Factorisation( )

  1     2  
                        FOR
                      
                      
                     
                        TO
                      
                        3    
                        DO
                      
                        4          5  
                        RETURN
                      
                      
                  

If, in this algorithm, the polynomial is constant, then we may stop, as the further steps will not give new factors. As the polynomial may have large degree, computing must be performed with particular care. The important idea here is that the residue can be computed using fast exponentiation.

The algorithm outlined above is suitable for testing whether a polynomial is irreducible, which is one of the important problems that we encounter when constructing finite fields. The algorithm presented here for distinct degree factorisation can solve this problem efficiently. For, it is obvious that a polynomial with degree is irreducible, if, in the factorisation (5.4), we have .

The following algorithm for testing whether a polynomial is irreducible is somewhat more efficient than the one sketched in the previous paragraph and handles correctly also the inputs that are not square-free.

Irreducibility-Test( )

  1     2  
                        IF
                      
                        3    
                        THEN
                      
                     
                        RETURN
                      “no”   4  
                        FOR
                      the prime divisors  of    5    
                        DO
                      
                     
                        IF
                      
                        6       
                        THEN
                      
                     
                        RETURN
                      “no”   7  
                        RETURN
                      “yes” 

In lines 2 and 5, we check whether is the smallest among the positive integers for which divides . By Theorem 5.35, this is equivalent to the irreducibility of . If survives the test in line 2, then, by Theorem 5.35, we know that is square-free and must divide . Using at most fast exponentiations modulo , we can thus decide if is irreducible.

Theorem 5.36 If the field is given and is an integer, then the field can be constructed using a randomised Las Vegas algorithm which runs in time polynomial in and .

Proof. The algorithm is the following.

Finite-Field-Construction( )

  1  
                        FOR
                      
                      to    2    
                        DO
                      
                      a random element (uniformly distributed) of    3     4  
                        IF
                      
                     
                        Irreducibility-Test
                      
                      “yes”   5    
                        THEN
                      
                     
                        RETURN
                      
                        6    
                        ELSE
                      
                     
                        RETURN
                      “fail” 

In lines 1–3, we choose a uniformly distributed random polynomial with leading coefficient and degree . Then, in line 4, we efficiently check if is irreducible. By Theorem 5.31, the polynomial is irreducible with a reasonably high probability.

5.3.3. 5.3.3 The Cantor-Zassenhaus algorithm

In this section we consider the special case of the factorisation problem in which is odd and the polynomial is of the form

where the are pairwise relatively prime irreducible polynomials in with the same degree , and we also assume that . Our motivation for investigating this special case is that a square-free distinct degree factorisation reduces the general factorisation problem to such a simpler problem. If is even, then Berlekamp's method, presented in Subsection 5.3.4, gives a deterministic polynomial time solution. There is a variation of the method discussed in the present section that works also for even ; see Problem 5-2.

Lemma 5.37 Suppose that is odd. Then there are pairs such that exactly one of and is equal to .

Proof. Suppose that is a primitive element in ; that is, , but for . Then , and further, as , but , we obtain that . Therefore , and so half of the element give , while the other half give . If then clearly . Thus there are pairs such that , but , and, obviously, we have the same number of pairs for which the converse is valid. Thus the number of pairs that satisfy the condition is .

Theorem 5.38 Suppose that is odd and the polynomial is of the form (5.5) and has degree . Choose a uniformly distributed random polynomial with degree less than . (That is, choose pairwise independent, uniformly distributed scalars , and consider the polynomial .) Then, with probability at least , the greatest common divisor

is a proper divisor of .

Proof. The element corresponds to an element of the residue class field . By the Chinese remainder theorem (Theorem 5.15), choosing the polynomial uniformly implies that the residues of modulo the factors are independent and uniformly distributed random polynomials. By Lemma 5.37, the probability that exactly one of the residues of the polynomial modulo and is zero is precisely . In this case the greatest common divisor in the theorem is indeed a divisor of . For, if , but this congruence is not valid modulo , then the polynomial is divisible by the factor , but not divisible by , and so its greatest common divisor with is a proper divisor of . The function

is strictly increasing in , and it takes its smallest possible value if is the smallest odd prime-power, namely 3. The minimum is, thus, .

The previous theorem suggests the following randomised Las Vegas polynomial time algorithm for factoring a polynomial of the form (5.5) to a product of two factors.

Cantor-Zassenhaus-Odd( )

  1     2  
                        FOR
                      
                      to    3    
                        DO
                      
                      a random element (uniformly distributed) of    4     5     6  
                        IF
                      
                        7    
                        THEN
                      
                     
                        RETURN
                      
                        8    
                        ELSE
                      
                     
                        RETURN
                      “fail” 

If one of the polynomials in the output is not irreducible, then, as it is of the form (5.5), it can be fed, as input, back into the algorithm. This way we obtain a polynomial time randomised algorithm for factoring .

In the computation of the greatest common divisor, the residue should be computed using fast exponentiation.

Now we can conclude that the general factorisation problem (5.3) over a field with odd order can be solved using a randomised polynomial time algorithm.

5.3.4. 5.3.4 Berlekamp's algorithm

Here we will describe an algorithm that reduces the problem of factoring polynomials to the problem of searching through the underlying field or its prime field. We assume that

where the are pairwise non-associate, irreducible polynomials in , and also that . The Chinese remainder theorem (Theorem 5.15) gives an isomorphism between the rings and

The isomorphism is given by the following map:

where . The most important technical tools in Berlekamp's algorithm are the -th and -th power maps in the residue class ring . Taking -th and -th powers on both sides of the isomorphism above given by the Chinese remainder theorem, we obtain the following maps:

The Berlekamp subalgebra of the polynomial is the subring of the residue class ring consisting of the fixed points of the -th power map. Further, the absolute Berlekamp subalgebra of consists of the fixed points of the -th power map. In symbols,

It is easy to see that . The term subalgebra is used here, because both types of Berlekamp subalgebras are subrings in the residue class ring (that is they are closed under addition and multiplication modulo ), and, in addition, is also linear subspace over , that is, it is closed under multiplication by the elements of . The absolute Berlekamp subalgebra is only closed under multiplication by the elements of the prime field .

The Berlekamp subalgebra is a subspace, as the map is an -linear map of into itself, by Lemma 5.23 and Theorem 5.19. Hence a basis of can be computed as a solution of a homogeneous system of linear equations over , as follows.

For all , compute the polynomial with degree at most that satisfies . For each , such a polynomial can be determined by fast exponentiation using multiplications of polynomials and divisions with remainder. Set . The class of a polynomial with degree less than lies in the Berlekamp subalgebra if and only if

which, considering the coefficient of for , leads to the following system of homogeneous linear equations in variables:

Similarly, computing a basis of the absolute Berlekamp subalgebra over can be carried out by solving a system of homogeneous linear equations in variables over the prime field , as follows. We represent the elements of in the usual way, namely using polynomials with degree less than in . We perform the operations modulo , where is an irreducible polynomial with degree over the prime field . Then the polynomial of degree less than can be written in the form

where . Let, for all and for all , be the unique polynomial with degree at most for which . The polynomial is of the form . The criterion for being a member of the absolute Berlekamp subalgebra of with is

which, considering the coefficients of the monomials , is equivalent to the following system of equations:

This is indeed a homogeneous system of linear equations in the variables . Systems of linear equations over fields can be solved in polynomial time (see Section 31.4), the operations in the ring can be performed in polynomial time, and the fast exponentiation also runs in polynomial time. Thus the following theorem is valid.

Theorem 5.39 Let . Then it is possible to compute the Berlekamp subalgebras and , in the sense that an -basis of and -basis of can be obtained, using polynomial time deterministic algorithms.

By (5.6) and (5.7),

and

The following theorem shows that the elements of the Berlekamp subalgebra can be characterised by their Chinese remainders.

Theorem 5.40

and

Proof. Using the Chinese remainder theorem, and equations (5.8), (5.9), we are only required to prove that

and

where is an irreducible polynomial, is an arbitrary polynomial and is a positive integer. In both of the cases, the direction is a simple consequence of Theorem 5.19. As , the implication concerning the absolute Berlekamp subalgebra follows from that concerning the Berlekamp subalgebra, and so it suffices to consider the latter.

The residue class ring is a field, and so the polynomial has at most roots in . However, we already obtain distinct roots from Theorem 5.19, namely the elements of (the constant polynomials modulo ). Thus

Hence, if , then is of the form where . Let be an arbitrary positive integer. Then

If we choose large enough so that holds, then, by the congruence above, also holds.

An element of or is said to be non-trivial if there is no element such that . By the previous theorem and the Chinese remainder theorem, this holds if and only if there are such that . Clearly a necessary condition is that , that is, must have at least two irreducible factors.

Lemma 5.41 Let be a non-trivial element of the Berlekamp subalgebra . Then there is an element such that the polynomial is a proper divisor of . If , then there exists such an element in the prime field .

Proof. Let and be integers such that , , and . Then, choosing , the polynomial is divisible by , but not divisible by . If, in addition, , then also .

Assume that we have a basis of at hand. At most one of the basis elements can be trivial, as a trivial element is a scalar multiple of 1. If is not a power of an irreducible polynomial, then there will surely be a non-trivial basis element , and so, using the idea in the previous lemma, can be factored two factors.

Theorem 5.42 A polynomial can be factored with a deterministic algorithm whose running time is polynomial in , , and .

Proof. It suffices to show that can be factored to two factors within the given time bound. The method can then be repeated.

Berlekamp-Deterministic

  1   a basis of    2  
                        IF
                      
                        3    
                        THEN
                      
                      a non-trivial element of    4       
                        FOR
                      
                        5          
                        DO
                      
                        6             
                        IF
                      
                        7                
                        THEN
                      
                     
                        RETURN
                      
                        8    
                        ELSE
                      
                     
                        RETURN
                      “a power of an irreducible”  

In the first stage, in line 1, we determine a basis of the absolute Berlekamp subalgebra. The cost of this is polynomial in and . In the second stage (lines 2–8), after taking a non-trivial basis element , we compute the greatest common divisors for all . The cost of this is polynomial in and .

If there is no non-trivial basis-element, then is 1-dimensional and is the -th power of the irreducible polynomial where and can, for instance, be determined using the ideas presented in Section 5.3.1.

The time bound in the previous theorem is not polynomial in the input size, as it contains instead of . However, if is small compared to the other parameters (for instance in coding theory we often have ), then the running time of the algorithm will be polynomial in the input size.

Corollary 5.43 Suppose that can be bounded by a polynomial function of and . Then the irreducible factorisation of can be obtained in polynomial time.

The previous two results are due to E. R. Berlekamp. The most important open problem in the area discussed here is the existence of a deterministic polynomial time method for factoring polynomials. The question is mostly of theoretical interest, since the randomised polynomial time methods, such as the a Cantor -Zassenhaus algorithm, are very efficient in practice.

5.3.4.1.  Berlekamp's randomised algorithm

We can obtain a good randomised algorithm using Berlekamp subalgebras. Suppose that is odd, and, as before, is the polynomial to be factored.

Let be a random element in the Berlekamp subalgebra . An argument, similar to the one in the analysis of the Cantor-Zassenhaus algorithm shows that, provided has at least two irreducible factors, the greatest common divisor is a proper divisor of with probability at least 4/9. Now we present a variation of this idea that uses less random bits: instead of choosing a random element from , we only choose a random element from .

Lemma 5.44 Suppose that is odd and let and be two distinct elements of . Then there are at least elements such that exactly one of the elements and is .

Proof. Using the argument at the beginning of the proof of Lemma 5.37, one can easily see that there are elements in the set whose -th power is . It is also quite easy to check, for a given element , that there is a unique such that . Indeed, the required is the solution of a linear equation.

By the above, there are elements such that

For such a , one of the elements and is equal to and the other is equal to .

Theorem 5.45 Suppose that is odd and the polynomial has at least two irreducible factors in . Let be a non-trivial element in the Berlekamp subalgebra . If we choose a uniformly distributed random element , then, with probability at least , the greatest common divisor is a proper divisor of the polynomial .

Proof. Let , where the factors are pairwise distinct irreducible polynomials. The element is a non-trivial element of the Berlekamp subalgebra, and so there are indices and elements such that and . Using Lemma 5.44 with and , we find, for a random element , that the probability that exactly one of the elements and is zero is at least . If, for instance, , but , then but , that is, the polynomial is divisible by , but not divisible by . Thus the greatest common divisor is a proper divisor of .

The quantity is a strictly increasing function in , and so it takes its smallest value for the smallest odd prime-power, namely 3. The minimum is 1/3.

The previous theorem gives the following algorithm for factoring a polynomial to two factors.

Berlekamp-Randomised

  1   a basis of    2  
                           IF
                         
                           3    
                           THEN
                         
                         a non-trivial elements of    4        a random element (uniformly distributed) of    5          6       
                           IF
                         
                           7          
                           THEN
                         
                        
                           RETURN
                         
                           8          
                           ELSE
                         
                        
                           RETURN
                         “fail”   9    
                           ELSE
                         
                        
                           RETURN
                         “a power of an irreducible” 

Exercises

5.3-1 Let be an irreducible polynomial, and let be an element of the field . Give a polynomial time algorithm for computing .

Hint. Use the result of Exercise 5.1-6

5.3-2 Let . Using the Distinct-Degree-Factorisation algorithm, determine the factorisation (5.4) of .

5.3-3 Follow the steps of the Cantor-Zassenhaus algorithm to factor the polynomial .

5.3-4 Let . Show that coincides with the absolute Berlekamp subalgebra of , that is, .

5.3-5 Let . Using Berlekamp's algorithm, determine the irreducible factors of : first find a non-trivial element in the Berlekamp subalgebra , then use it to factor .