# 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.

-
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