Irreducible Polynomials

Date: 06/06/2001 at 08:44:02
From: McLoone
Subject: Finite Field Mathematics

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

For E.g. : the polynomial x^8 + x^4 + x^3 + x + 1 (Hex: x'11B')

I want to show that this polynomial is irreducible over GF(2^8).
I have created a table of the 'Powers of Alpha' from the polynomial, 
but at alpha^51, the values begin repeating themselves. Does this 
mean that the algorithm is NOT irreducible?

Date: 06/06/2001 at 15:16:19
From: Doctor Rob
Subject: Re: Finite Field Mathematics

Thanks for writing to Ask Dr. Math, McLoone.

In answer to your question, that does not mean that the polynomial is 
irreducible. What it does mean is that the polynomial is a divisor of 
x^51 + 1. (We say that the polynomial has period 51.)

There are a couple of ways to prove irreducibility. The first is to 
try as factors all irreducible polynomials of degree up to 4:

   x
   x + 1
   x^2 + x + 1
   x^3 + x + 1
   x^3 + x^2 + 1
   x^4 + x + 1
   x^4 + x^3 + 1
   x^4 + x^3 + x^2 + x + 1

You can short-cut this by using the fact that f(x) is a divisor of
x^51 + 1. That eliminates all the 3rd and 4th degree polynomials in 
the above list. That's because the 3rd degree ones divide x^7 + 1, 
and 7 is not a divisor of 51; and the 4th degree ones divide either 
x^15 + 1 or x^5 + 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 x^2 + 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 alpha reduced modulo the polynomial:
alpha^(2*i), 0 <= i <= 7 (which you have already computed):


       [1 0 0 0 0 0 0 0]  <-->  alpha^0
       [0 0 1 0 0 0 0 0]  <-->  alpha^2
       [0 0 0 0 1 0 0 0]  <-->  alpha^4
   Q = [0 0 0 0 0 0 1 0]  <-->  alpha^6
       [1 1 0 1 1 0 0 0]  <-->  alpha^8
       [0 0 1 1 0 1 1 0]  <-->  alpha^10
       [1 1 0 1 0 1 0 1]  <-->  alpha^12
       [0 1 0 1 1 0 0 1]  <-->  alpha^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 2^8 - 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.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/