Irreducibility of a polynomial in $\mathbb{F}_4$ 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 
 A: 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).
A: 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.
A: 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.
