Definition: A non-constant polynomial is said to be irreducible if it is cannot be factored into a product of two non-constant polynomials. In other words; if $p(x) = q(x)t(x)$ and it is irreducible then either $q(x)$ or $t(x)$ is a constant polynomial.
One way to prove that is $p(x) = x^8+x^4+x^3+x+1$ is irreducible over $\operatorname{GF}(2)[x]$ is checking the divisibility by the lower degree irreducible polynomials. First degree 1, then degree 2, then degree 3, and degree 4 will be enough to determine since a degree 8 can be factored into two polynomials with possible degrees as $1\cdot 7,2\cdot 6, 3\cdot 5$, and $4 \cdot 4$.
Below all the arithmetic is performed on $\operatorname{GF}(2)[x]$
degree polynomials are $x$ and $x+1$. We can check the divisibility by setting $p(0) \stackrel{?}{=} 0$ or $p(1) \stackrel{?}{=} 0$. $p(0) = 1 \neq 0$ and also $p(1) = 1 \neq 0$. Therefore degree one polynomials doesn't divide $p(x)$. This is by the factor theorem and here a nice proof in Math.SE.
degree polynomials, where we have four polynomials;
\begin{align}
& x^2+x+1\\
& x^2+x \\
& x^2+1\\
& x^2\\
\end{align}
Let see why $x^2+1$ is not irreducible;
\begin{align}
(x+1)\,(x+1)&=x\,(x+1)+1\,(x+1)&&\text{by distributivity}\\
&=x^2+1\,x+1\,x+1&&\text{.}\\
&=x^2+(1+1)\,x+1&&\text{.}\\
&=x^2+(0)\,x+1&&\text{since the coefficients are in }\operatorname{GF}(2)\\&=x^2+1
\end{align}
with a quick check that only $x^2+x+1$ is irreducible. To see that $p(x)$ is not divisible by $x^2+x+1$ perform division and look for the remainder. One can use this Sage script
R = PolynomialRing(GF(2),'x')
x = R.gen()
p = x^8+x^4+x^3+x+1
q = x^2 + x + 1
p.quo_rem(q)
the output is $(quo = x^6 + x^5 + x^3, rem = x + 1)$, . i.e cannot divide.
- degree irreducible polynomials
\begin{align}
& x^3 + x + 1 \\
& x^3 + x^2 + 1
\end{align}
- degree irreducible polynomials
\begin{align}
& x^4 + x + 1 \\
& x^4 + x^3 + 1\\
& x^4 + x^3 + x^2 + x + 1
\end{align}
These polynomials are generated with SageMath
degree=4
R = GF(2)['x']
for p in R.polynomials(degree):
if p.is_irreducible():
print(p)
To test all the division use the below
R = PolynomialRing(GF(2),'x')
x = R.gen()
p = x^8+x^4+x^3+x+1
lst = [ x^2 + x + 1, x^3 + x + 1, x^3 + x^2 + 1, x^4 + x + 1 , x^4 + x^3 + 1, x^4 + x^3 + x^2 + x + 1]
for t in lst:
print(p.quo_rem(t))
The output is
(x^6 + x^5 + x^3, x + 1)
(x^5 + x^3 + x^2 + 1, x^2)
(x^5 + x^4 + x^3, x + 1)
(x^4 + x, x^3 + x^2 + 1)
(x^4 + x^3 + x^2 + x + 1, x^3 + x^2)
(x^4 + x^3 + 1, x^3 + x^2)
Therefore $p(x) = x^8+x^4+x^3+x+1$ is irreducible over $\operatorname{GF}(2)[x]$
Note 1: low degree irreducible binary polynomials are important in Cryptography since they reduce the required arithmetic. Gadiel Seroussi, in 1998, made a huge list in Table of Low-Weight Binary Irreducible Polynomials. The list contains binary irreducible polynomials up to 10000 degrees.
Note 2: A014580 from
The On-Line Encyclopedia of Integer Sequences contains a list of binary polynomials, encoded in binary, or evaluated when $x=2$. The $p(2)$ is 283.
2, 3, 7, 11, 13, 19, 25, 31, 37, 41, 47, 55, 59, 61, 67, 73, 87, 91, 97, 103, 109, 115, 117, 131, 137, 143, 145, 157, 167, 171, 185, 191, 193, 203, 211, 213, 229, 239, 241, 247, 253, 283, 285, 299, 301, 313, 319, 333, 351, 355, 357, 361, 369, 375,...
The bolds irreducibles are listed in this answer.
Note 3: A001037 keeps the number of degree-n irreducible polynomials over $\operatorname{GF}(2)$. There are 18 in degree 8 and $p(x)$ among the lowest possible weight.
degree 1 2 3 4 5 6 7 8
count 1, 2, 1, 2, 3, 6, 9, 18
and this can be counted by $$L_q(n) = \frac{1}{2} \sum_{d|n} \mu (\frac{n}{d})q^d$$
