Is $x^8 + x^5 + x^3 + x^2 + 1$ an irreducible polynomial or not in GF $2^8$

Question

Is $x^8 + x^5 + x^3 + x^2 + 1$ an irreducible polynomial or not in Galois Field $2^8$? Thanks in advance.

Answer 1

The question is a bit unclear. If you are truly asking whether this polynomial $$ p(x)=x^8+x^5+x^3+x^2+1 $$ is irreducible in the ring $GF(256)[x]$, then the answer is trivially NO! This is because:

• Either it is reducible over $GF(2)$ in which case it is reducible over the extension field also,
• Or it is irreducible over $GF(2)$ in which case $GF(2)[x]/\langle p(x)\rangle$ is a field of 256 elements, and thus isomorphic (or equal to) $GF(256)$. In this case $p(x)$ has 8 distinct zeros in the field, namely the cosets $x^{2^i}+\langle p(x)\rangle$, $i=0,1,2,\ldots,7$. Consequently $p(x)$ would split into linear factors over $GF(256)$.

But this was a bit naughty of me, because I took your phrasing of the question literally. Presumably you would not ask things like: "Is $x^2+1$ irreducible over the complex numbers?", because you know that it factors as $(x+i)(x-i)$ in $\Bbb{C}[x]$. The only sensible guess is that you are inquiring whether $p(x)$ is irreducible over $GF(2)$.

As pointed out in the comments you need to show that $p(x)$ has no factors of degree 4 or lower. The usual suspects are $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$. If you were given this as an exercise, your teacher/book must have produced this at some earlier point (otherwise it would a bit naughty of them - barring introduction of a general algorithm like Berlekamp's).

• Because $p(x)$ has five terms including $1$ we can immediately rule out the linear factors.
• The quadratic factor is a factor of $x^3+1$. But $x^8+x^5=(x^3+1)x^5$, so $$p(x)\equiv x^2\pmod{x^2+x+1}.$$ Thus no irreducible quadratic factor.
• Both the cubic irreducible polynomials are factors of $x^7+1$ (the multiplicative group of the field $GF(8)$ is cyclic of order seven). We see that $x^8\equiv x\pmod{x^7+1}$, so $p(x)\equiv x^5+x^3+x^2+x+1\pmod {x^7+1}$. If this were divisible by $x^3+x+1$ then so would $x^5+x^2=x^2(x^3+1)=x^2(x+1)(x^2+x+1)$ which is absurd. Likewise, if it were divisible by $x^3+x^2+1$, then so would $x^5+x=x(x^4+1)=x(x+1)^4$ again violating uniqueness of factorization.

This leaves the possibility that $p(x)$ could be a product of two irreducible quartics, i.e. a product of two of $f_1(x)=x^4+x+1$, $f_2(x)=x^4+x^3+1$, $f_3(x)=x^4+x^3+x^2+x+1$. Could $f_1(x)$ be a factor? We have $f_1(x)^2=x^8+x^2+1$, so $$ p(x)\equiv x^5+x^3\pmod{f_1(x)}. $$ As in the cubic case this leads to a contradiction as $x^5+x^3=x^3(x+1)^2$ is not divisible by $f_1(x)$.

Because $p(x)$ contains odd degree terms, it is not a square of a polynomial. The only remaining possibility is $$ p(x)=f_2(x)f_3(x). $$ Leaving it to you to rule out this possibility. Either by brute force or by using one of the techniques outlined here.

Answer 2

I'll say at the beginning that I'm not very familiar with this area, I just thought I'd take a shot at this since there hasn't been much. Please correct me if I'm misunderstanding something.

Suppose you have the polynomials

$$ P_0(x) = x^8 + x^5 + x^3 + x^2 + 1$$

$$ P_1(x) = A_7\,x^7 + A_6\,x^6 + A_5\,x^5 + A_4\,x^4 + A_3\,x^3 + A_2\,x^2 + A_1\,x^1 + A_0\,x^0 $$ $$ P_2(x) = B_7\,x^7 + B_6\,x^6 + B_5\,x^5 + B_4\,x^4 + B_3\,x^3 + B_2\,x^2 + B_1\,x^1 + B^0\,x^0 $$

Now, if $P_0(x) \equiv P_1(x)\cdot P_2(x) \pmod{256}$, then $P_0(x) \equiv P_1(x)\cdot P_2(x) \pmod{2}$ since $2 \mid 256$. So we can check:

$$\begin{align} 0 & \equiv A_7\,B_7\pmod{2} \\ 0 & \equiv A_6\,B_7 + A_7\,B_6\pmod{2} \\ 0 & \equiv A_5\,B_7 + A_6\,B_6 + A_7\,B_5\pmod{2} \\ 0 & \equiv A_4\,B_7 + A_5\,B_6 + A_6\,B_5 + A_7\,B_4\pmod{2} \\ 0 & \equiv A_3\,B_7 + A_4\,B_6 + A_5\,B_5 + A_6\,B_4 + A_7\,B_3\pmod{2} \\ 0 & \equiv A_2\,B_7 + A_3\,B_6 + A_4\,B_5 + A_5\,B_4 + A_6\,B_3 + A_7\,B_2\pmod{2} \\ 1 & \equiv A_1\,B_7 + A_2\,B_6 + A_3\,B_5 + A_4\,B_4 + A_5\,B_3 + A_6\,B_2 + A_7\,B_1\pmod{2} \\ 0 & \equiv A_0\,B_7 + A_1\,B_6 + A_2\,B_5 + A_3\,B_4 + A_4\,B_3 + A_5\,B_2 + A_6\,B_1 + A_7\,B_0\pmod{2} \\ 0 & \equiv A_0\,B_6 + A_1\,B_5 + A_2\,B_4 + A_3\,B_3 + A_4\,B_2 + A_5\,B_1 + A_6\,B_0\pmod{2} \\ 1 & \equiv A_0\,B_5 + A_1\,B_4 + A_2\,B_3 + A_3\,B_2 + A_4\,B_1 + A_5\,B_0\pmod{2} \\ 0 & \equiv A_0\,B_4 + A_1\,B_3 + A_2\,B_2 + A_3\,B_1 + A_4\,B_0\pmod{2} \\ 1 & \equiv A_0\,B_3 + A_1\,B_2 + A_2\,B_1 + A_3\,B_0\pmod{2} \\ 1 & \equiv A_0\,B_2 + A_1\,B_1 + A_2\,B_0\pmod{2} \\ 0 & \equiv A_0\,B_1 + A_1\,B_0\pmod{2} \\ 1 & \equiv A_0\,B_0\pmod{2} \\ \end{align}$$

This is fairly simple to check with a computer, my search turned up that it is irreducible.