Test for polynomial reducibility with binary coefficients I'm learning about Galois Fields, in particular $GF(2^8)$, as they are applied to things like the AES algorithm and Reed-Solomon codes.  Each of these rely on an irreducible 8th degree polynomial with binary coefficients to serve as a modulus for generating the particular field instance.  For example AES uses $x^8+x^4+x^3+x^1+x^0$.
Is there a test I can apply to an 8th degree polynomial with binary coefficients I am presented with to determine whether or not it is irreducible?
 A: A non-irreducible polynomial $p(x)$ of degree eight has an irreducible factor of degree $\le 4$. This suggest the following test. Check divisibility by all of $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$ and $x^4+x^3+x^2+x+1$. That list contains all the irreducible polynomials of degree $\le 4$ with coefficients in $GF(2)$. If your polynomial is not divisible by any of these, it is irreducible.
That is a little bit of work. Of course testing divisibility by either $x$ or $x+1$ is trivial. A polynomial is divisible by $x$, iff its constant term is zero. And a binary polynomial is divisible by $x+1$, iff it has an even number of terms. The remaining six are a bit trickier. Often checking for divisibility by $x^2+x+1$ is aided by the observation that $x^3+1=(x+1)(x^2+x+1)$ is divisible, hence so are all binomials of the form $x^\ell+x^{\ell+3}$. This allows you to replace a high degree term with a lower degree term. Similarly the cubic irreducible ones are both factors of $x^7+1$, but that won't be nearly as useful in the calculations.
