Take the 2-minute tour ×  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 add comment  1
Answer  up vote 4 do