Irreducible PolynomialsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/