Proving $f = x^8+x^7+x^3+x+1$ to be irreducible over $\mathbf{F}_2$.

Question

I am taking all the irreducible polynomials over $\mathbf{F}_2$ of degree 1 to 4 inclusive and using the long division to determine whether the given $f$ is divisible by anyone of them and it is not so.

What are the other ways?

Answer 1

This can be done quickly by the Euclidean algorithm. If $f$ is reducible it has an irreducible factor of degree $\le 4,\,$ so either it has a factor in common with $\, x^{16}-x\,$ (which is divisible by every irreducible of degree dividing $4$) or, it has cubic factor, hence a factor in common with $\,x^8-x,\,$ hence a factor in common with $\, g =x^7-1,\,$ since $\,x\nmid f.\,$

The latter case is impossible, since $\,f\ {\rm mod}\ g = f - (x+1)(x^7\!-1) = x^3,\,$ thus $\,(f,g) = (f\ {\rm mod}\ g,\,g) = (x^3,g) = 1\,$ by $\,(x,g)= (x,x^7\!-1) = (x,-1)= 1.$

For the first case, by $\,x\nmid f,\,$ it suffices to show that $\,f\,$ is coprime to $\,g = x^{15}\!-1.$

Division $ $ yields $\ \ g\ {\rm mod}\ f = x^6\!+x^4\!+x^2 = x^2 h^2,\ \ h = x^2\!+x+1 $

Hence $\ \ (g,f) = (g\ {\rm mod} f,\, f) = (x^2 h^2,f)$ so it suffices to show $(h,f) = 1,\ $ since $\,x\nmid f$.

Indeed $\,(h,f) = (h,\, f\ {\rm mod}\ h) = (h,x\!-\!1) = (h(1),x\!-\!1)=(1,x\!-\!1)=1$.