How to prove a polynominal is irreducible over GF(2)?

Question

How do you prove a polynomial is irreducible over GF(2)?

Answer 1

There is a general result for all finite fields:

Let $\mathbf F_q$ be a finite field with $q$ elements ($q=p^r$ for some prime $p$). In $\mathbf F_q[X]$, the polynomial $X^{q^n}-X$ is the product of all irreducible monic polynomials of degree dividing $n$

As a consequence, in $\mathbf F_q[X]$, there exist s irreducible polynomials of every degree.

One also deduces the

Irreducibility criterion: A polynomial $P\in\mathbf F_q[X]$ with degree $n$ is irreducible if and only if

1. $P$ divides $X^{q^n}-X$;

2. $P$ is coprime with all $X^{q^r}-X$, $\;r=\dfrac nd$, where $d$ is a prime divisor of $n$.