# Prove that the $x^8+x^4+x^3+x+1$ is irreducible over $\mathbb{Z}_2[x]$

I am new to this field. I am doing some cryptography course and have encountered $$\text{GF}(2^8)$$ in the famous AES algorithm. Although I do not have a strong relevant math background with this stuff(ring/field), I am really interested in it. My textbook has a question which says to prove that:

$$x^8+x^4+x^3+x+1$$ is irreducible over $$\mathbb{Z}_2[x]$$. I am stuck at this point where I don't have much intuition about proving irreducibility over the whole $$\mathbb{Z}_2[x]$$. Any help will be much appreciated!

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]$$

1. 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.

2. 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.

1. degree irreducible polynomials

\begin{align} & x^3 + x + 1 \\ & x^3 + x^2 + 1 \end{align}

1. 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$$

• @kelalaka Thank you so much for such a detailed and great explanation! I am much grateful to you for your kind help. Commented Mar 2, 2020 at 18:19
• Addition: The question's $\Bbb Z_2$ is this answer's $\operatorname{GF}(2)$. The question's $\text{GF}(2^8)$ can be seen as the answer's $\operatorname{GF}(2)[x]$ restricted to polynomials with degree less than $8$, under the same addition law, and a different multiplication law: $r\cdot s$ in $\text{GF}(2^8)$ is defined to be $(r\cdot s)\bmod(x^8+x^4+x^3+x+1)$ in $\operatorname{GF}(2)[x]$. That modified multiplication is an internal law. It inherits associativity, commutativity, distributivity, neutral (the polynomial $1$). It is such that every element except $0$ has an inverse.
– fgrieu
Commented Mar 3, 2020 at 14:59
• @fgrieu I used to use $\Bbb Z_2$, nowadays I prefer $\operatorname{GF}(2)$ to honor the Galois. I wonder what would have been the science if he didn't die in the duel. Commented Mar 3, 2020 at 16:39