CIS 428 Introduction to Cryptography

Barbara Nostrand, Ph.D.

Electrical Engineering and Computer Science


Irreducible Polynomials in GF(28)

If provided with an irreducible polynomial,  how can you prove that it is indeed irreducible? 

For E.g.  :  the polynomial x8 + x4 + x3 + x + 1 (Hex:  x'11B')

There are several of ways to prove irreducibility.  The first is to try as factors all polynomials of degree up to n/2: 

The second is to try as factors all irreducible polynomials of degree up to n/2.  For n=8 these are: 

     x
     x + 1
     x2 + x + 1
     x3 + x + 1
     x3 + x2 + 1
     x4 + x + 1
     x4 + x3 + 1
     x4 + x3 + x2 + x + 1

You can short-cut this by using the fact that f(x) is a divisor of x51 + 1.  That eliminates all the 3rd and 4th degree polynomials in the above list.  That's because the 3rd degree ones divide x7 + 1,  and 7 is not a divisor of 51; and the 4th degree ones divide either x15 + 1 or x5 + 1,  and neither of these is a divisor of 51.  You can also see by inspection that x is not a factor,  and x + 1 is not a factor because the polynomial has an odd number of nonzero terms.  Thus you only have to try x2 + x + 1 as a factor by division. 

Another way to prove irreducibility is to count the number of distinct irreducible factors.  Create the square matrix Q of coefficients of even powers of α reduced modulo the polynomial: α(2*i),  0 ≤ i ≤ 7 (which you have already computed):

       [1 0 0 0 0 0 0 0]  <-->  α0
       [0 0 1 0 0 0 0 0]  <-->  α2
       [0 0 0 0 1 0 0 0]  <-->  α4
   Q = [0 0 0 0 0 0 1 0]  <-->  α6
       [1 1 0 1 1 0 0 0]  <-->  α8
       [0 0 1 1 0 1 1 0]  <-->  α10
       [1 1 0 1 0 1 0 1]  <-->  α12
       [0 1 0 1 1 0 0 1]  <-->  α14
Then the number of distinct irreducible factors of Q is the same as the dimension of the nullspace of
           [0 0 0 0 0 0 0 0]
           [0 1 1 0 0 0 0 0]
           [0 0 1 0 1 0 0 0]
   Q + I = [0 0 0 1 0 0 1 0].
           [1 1 0 1 0 0 0 0]
           [0 0 1 1 0 0 1 0]
           [1 1 0 1 0 1 1 1]
           [0 1 0 1 1 0 0 0]
This is a standard thing to do in linear algebra.  It turns out that the left nullspace has dimension 1,  generated by the vector: 
   [1 0 0 0 0 0 0 0].
That implies that f(x) has exactly 1 irreducible factor.  All that remains is to show that f(x) is not a perfect power of some polynomial of lower degree. If it were, the power would have to be 2,  4,  or 8,  so f(x) would be a perfect square.  That is false,  since f(x) has a term with an odd exponent.  Thus f(x) is itself irreducible.  Another approach is to realize that the period of f(x) is the least common multiple of the periods of its irreducible-power factors.  Thus any factor of f(x) would have to have a period that divides 51 = 3*17.  To get an LCM of 51,  at least one of the irreducible factors of f(x) must have period 17 or 51.  Irreducible polynomials of period 17 or 51 have degree 8,  because 17 and 51 are factors of 28 - 1 = 255,  and no lower power of 2 will do.  Thus f(x) must have an irreducible factor of degree 8,  so f(x) must itself be irreducible. 

Take whichever approach suits your taste. 


Last modified: 2008 MAR 24
bnostran@syr.edu