Irreducibility of a polynomial in $\mathbb{F}_4$

Question

Let $j$ be a primitively element for the extension $\mathbb{F}_4/\mathbb{F}_2$, let $f(x)=x^4+x^2+jx+1 \in \mathbb{F}_4[x]$ I want to show that f is irreducible over $\mathbb{F}_4$.

I know that $\mathbb{F}_4=\mathbb{F}_2[x]/(x^2+x+1)$, but how do I deal with $f$ in this quotient? Thank you

Answer 1

With paper-and-pencil only I calculated $\gcd(x^{16}+x,f(x))$ as follows by repeated squaring. All the congruences are modulo $f$. Recall that squaring is additive. $$ \begin{aligned} x^4&\equiv x^2+jx+1,\\ x^4+x^2&\equiv jx+1,&\ \text{(a by-product used below)}\\ x^8&\equiv x^4+(j+1)x^2+1\\ &\equiv jx^2+jx\\ x^{16}&\equiv j^2(x^2+x)^2=(j+1)(x^4+x^2)\\ &\equiv (j+1)(jx+1)=x+j+1,\\ x^{16}+x&\equiv j+1. \end{aligned} $$ So $f(x)$ and $x^{16}+x$ have no common factors. Therefore $f$ has no zeros in $\Bbb{F}_{16}$. Consequently $f$ cannot have any linear or quadratic factors in $\Bbb{F}_4[x]$. Hence it is irreducible in that ring.

I think this is a bit faster than the suggested alternatives.

Answer 2

One boring but straightforward way is the Sieve of Eratosthenes for $\mathbb{F}_4[x]$.

The (monic) irreducibles of degree $1$ are $x$, $x+1$, $x+j$, and $x+(1+j)$. (Of course in a field of characteristic $2$, $+$ or $-$ is the same thing.)

Therefore the reducible polynomials of degree $2$ are $$(x)(x)=x^2,\quad (x)(x+1)=x^2+x, \quad\ldots,\quad (x+(1+j))(x+(1+j))=x^2+j$$ Any other polynomial of degree $2$ must be irreducible!

Now you could proceed to "cross out" the reducible polynomials of degree $3$, leaving the irreducibles of degree $3$, and so on... but actually you don't need to. Just like you only have to check up to $\sqrt{n}$ for divisors of an integer $n$ in order to check if $n$ is prime, you only have to check irreducibles of degree $\leq\frac{\deg(f)}{2}$ in order to check if a polynomial $f$ is irreducible (see if you can prove this).

Answer 3

Here’s another method, but perhaps not so well suited to hand computation:

Let $R=\Bbb F_4[\xi]/(\xi^4+\xi^2+j\xi+1)$. If $f$ factors nontrivially as $gh$, then $R\cong\Bbb F_4[s]/(g(s))\oplus\Bbb F_4[t]/(h(t))$, direct sum of two rings of order $4^{\deg g}$ and $4^{\deg h}$, respectively, and in this ring, there aren’t any elements of very high multiplicative order. But in fact (and here is the computation), $\eta=1+\xi$ has multiplicative order $255$ in $R$: you check this by noting that even though $\eta^{255}=1$, you also get $\eta^{255/3}\ne1$, $\eta^{255/5}\ne1$, and $\eta^{255/17}\ne1$. Thus $R$ is $\Bbb F_{256}$, a field, so $f$ is irreducible.