Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What's the easiest way to check if a polynomial of degree > 3 is irreducible in $\mathbb{Z}_2[x]$?

I want to find out if $x^7+x^6+1$ is irreducible in $\mathbb{Z}_2[x]$.

If a quadratic polynomial factors, it must be a product of two linear factors, and if a cubic polynomial factors, then it must be a product of a linear and a quadratic (or three linear) and it must have a root in $\mathbb{Z}_2[x]$. Easily verified.

If I had a polynomial of degree 5 I would test if I could find any factors by assuming for ex: $(x^3 + Ax^2 + Bx + C) (x^2 + Dx + E)$ and if we find a factor we know that it's reducible.

But if I have degree 7, I would we have to test a lot of combos, $x*x^6$, $x^4*x^3$, $x^3*x^3*x ...$ Is there an easier way to determine if it's irreducible?

share|improve this question
    
In $\mathbb{Z}_2$ do you mean $\mathbb{Z}/2\mathbb{Z}$ (integers ring modulo 2)? –  Zachi Evenor Jun 10 '12 at 13:38
    
@ZachiEvenor yes –  Sup3rgnu Jun 10 '12 at 13:52

1 Answer 1

up vote 4 down vote accepted

There are some methods and tricks. For example here you could by repeated squaring check that the remainder of $x^{128}$ modulo your polynomial is equal to $x$. As the polynomial $x^{128}+x$ is known to be the product of all the irreducible polynomials of degrees that are factors of seven, it follows that your polynomial is, indeed, irreducible (because it obviously is not a product of linear polynomials). But for this to work so smoothly it is crucial that seven is a prime.

Another thing you could try is to test divisibility by low-dimensional irreducible polynomials. If you play with these enough, you quickly learn that up to degree 3 all the irreducible polynomials of $\mathbb{Z}_2[x]$ are $x$, $x+1$, $x^2+x+1$, $x^3+x+1$ and $x^3+x^2+1$. If your degree 7 polynomial $p(x)=x^7+x^6+1$ were a product of two lower degree polynomials, it would have one irreducible factor that is at most cubic, and hence appear on that list.

We can immediately rule out $x$ and $x+1$ as factors, because $p(x)$ has no zeros in the prime field. We can rule out $x^2+x+1$, because that is a factor of $x^3-1$, and hence also of $x^6-1=x^6+1$. So it can not divide $p(x)$, because then it would have to be a factor of $p(x)-(x^6+1)=x^7$ also, but that is clearly not the case. Eliminating the candidate cubic factors depends on a similar trick (based on the theory of finite fields) that the irreducible cubics are factors of $x^8+x$, and hence also of $x^7+1$. So if either of them divided your $p(x)$, it would also have to be a factor of $p(x)-(x^7+1)=x^6$, which is, again, obviously not the case.

Conclusion. $p(x)$ is irreducible.

share|improve this answer
    
Thanks for the explanation! –  Sup3rgnu Jun 10 '12 at 13:50
    
You're welcome. Sorry about sweeping a lot of details under the rug (in particular re the first method). The answer is long enough as it is. As the degree of the polynomial to be tested grows, settling irreducibility becomes progressively more difficult. Hardly a surprise. –  Jyrki Lahtonen Jun 10 '12 at 13:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.