# Quick way to check if a polynomial of degree $> 3$ is irreducible?

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?

-
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

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.