Rabin test to prove poly is irreducible over $\mathbb{F}_2$

Question

I need to prove that $x^4+x+1$ is irreducible over $\mathbb{F}_2$. For this I need to use the Rabin test (Miller-Rabin)

Note that $\deg(f(x)) = 4$

How can I continue with the proof?

Answer 1

Of course we can prove very easily that $x^4+x+1$ is irreducible over $\mathbb{F}_2$ without Rabin's test. But if you have to use Rabin's test, then you should just follow the test. The Rabin test first asks you to verify that $f(x)=x^4+x+1$ divides $x^{2^4}-x$. This is indeed the case because of $$ x^{16}-x=(x^4 + x^3 + x^2 + x + 1)(x^4 + x^3 + 1)(x^4 + x + 1)(x^2 + x + 1)(x + 1)x. $$ Now follow the next steps for $d=1,2$ computing the greatest common divisors $\gcd(f(x),x^{2^d}-x)$. If they are equal to $1$, you are done.

Answer 2

You are over-complicating things. $$p(x)=x^4+x+1$$ clearly has no linear factor in $\mathbb{F}_2[x]$ (since its has no root in $\mathbb{F}_2$) hence to prove its irreducibility we just have to rule out the presence of quadratic factors. There is only one quadratic irreducible polynomial over $\mathbb{F}_2$, namely $x^2+x+1$, hence $$ x^2+x+1 \nmid p(x)\quad\Longrightarrow\quad p(x)\;\text{is irreducible}$$ and in $\mathbb{F}_2[x]$ $$\begin{eqnarray*} x^4+x+1 &\equiv& x(x+1)(x^2-x+1)+1\\ &\equiv& x(x+1)(x^2+x+1)+1\\ &\equiv& \color{red}{1}\pmod{x^2+x+1}.\end{eqnarray*}$$