How do you factorize a polynom in $\mathbb{Z}_2$? How can you efficiently factorize a polynom (in $\mathbb{Z}_2$) ?
Example in this answer:
$$x^{16}-x=x (x + 1) (x^2 + x + 1) (x^4 + x + 1) (x^4 + x^3 + 1) (x^4 + x^3 + x^2 + x + 1)$$
How do you do this by hand?
 A: Start with the factorization of  $x^{15}-1$ into cyclotomic polynomials:
$$
x^{16}-x = x(x^{15}-1)=x \Phi_1(x) \Phi_3(x) \Phi_5(x) \Phi_{15}(x) 
$$
which gives
$$
x^{16}-x = x(x - 1)(x^2 + x + 1) (x^4 + x^3 + x^2 + x + 1) (x^8 - x^7 + x^5 - x^4 + x^3 - x + 1)
$$
We then need to further factor these mod 2. The last factor is the only one that is reducible. Guessing a factorization into two quartics works.
A: Partial answer:
We know that $x-1 =x+1$, so we have:
\begin{eqnarray}
x^{16}-x &=& x(x^{15}-1)\\
&=& x(x^5-1)\underbrace{(x^{10}+x^5+1)}_{p(x)}\\
&=& x(x-1)(x^4+x^3+x^2+x+1)p(x)\\
\end{eqnarray}
Now we have to factor somehow $p(x)$...
A: Substitute $0$ and $1$ each time till you find all irreducible linear factors. For example $P(x)=x^{16}-x$ has $P(0)=P(1)=0,$ therefore $x$ and $x-1$ are factors of $P.$ Now $P(x)=x(x-1)Q(x)$ for some $Q(x)\in\Bbb{Z}_2[x].$ Use long division to find $Q$ and apply the same method to find linear factors of $Q.$  
Suppose at some point we have no linear factors, then we have to look at irreducible quadratic polynomials of $\Bbb{Z}_2[x].$ There is only one such polynomial and namely it is $x^2+x+1.$ Divide each even degree $(\ge 4)$ factor of $P$ to find all its irreducible quadratic factors.
Again at some point we will ran out of irreducible quadratic factors, then look for irreducible cubic factors (namely) $x^3+x^2+1,$ $ x^3+x+1$ and so on.
Continue this until we have the complete factorization.
EDIT:
To find the irreducible polynomials of degree $n$ in $\Bbb{Z}_2[x],$ we can observe that they are of the form $x^n+h(x)+1,$ where $h(x)$ is a polynomial of $\Bbb{Z}_2[x]$ of degree less than on equal to $n-1$ without a constant term and containing odd number of monomials.
For example irreducible bi-quadratic polynomials are given by $h(x)\in\{x^3+x^2+x, x^3, x\}.$
