Let $K = \mathbb{F}_3[T]/(T^3-T+1)$, what would be an irreducible polynomial in $K[X]$ of degree $13$? Let $K = \mathbb{F}_3[T]/(T^3-T+1)$. I'm trying to find an explicit polynomial $f \in K[X]$ that is irreducible of degree $13$. My first attempt was to note that since $T^3-T+1$ is irreducible over $\mathbb{F}_3$, since it has no roots, we know that $K \cong \mathbb{F}_{3^3} = \mathbb{F}_{27}$. Now I was thinking of the Artin-Schreier polynomial $X^{13} - X + 1 \in \mathbb{F}_{13}[X]$ that is irreducible. However, I'm not sure how that is going to help us in this case. Is there a general strategy to come up with irreducible polynomials of certain degree in finite fields?
 A: My go to -technique for tasks like this is to look for roots of unity of a suitable order. Behold.
Let $\alpha=T+\langle T^3-T+1\rangle\in K$ be a zero of the defining cubic $p(T)=T^3-T+1$. By applying the Frobenius automorphism twice we see that the other zeros of $p(T)$ are $\alpha^3=\alpha-1$ and $\alpha^9=\alpha+1$.
Because $\alpha^2\notin \Bbb{F}_3$ we can deduce that $\alpha^2\neq1$. But the multiplicative group $K^*$ has order $26$, so $(\alpha^2)^{13}=\alpha^{26}=1$ by Lagrange.
$13$ is a prime, so we can deduce that $\alpha^2$ is a root of unity of order $13$. Note: all the squares in $K\setminus\Bbb{F}_3$ have this property for the same reason.
Let us consider the polynomial
$$
f(x)=x^{13}-\alpha^2\in K[x].
$$
I claim that $f(x)$ is irreducible over $K$, and thus a very simply answer to your query.
Assume that $\beta$ is a zero of $f(x)$ in some extension field $L$ of $K$. We see that $\beta^{13}=\alpha^2$, and this implies that $\beta$ is a root of unity of order $13^2$.
We can assume that $L=K(\beta)$. If $|L|=q=3^m$, it follows that $13^2\mid q-1$.
The next step is always the same. We determine $m$ by finding the smallest exponent $m>0$ such that $3^m\equiv1\pmod{13^2}$. Because $\ell=3$ is the smallest positive exponent such that $13\mid 3^\ell-1$, we know that $m$ must be a multiple of $3$ (this follows also from the fact that $K\subset L$). Because $3^3\not\equiv1\pmod{13^2}$ the theory of primitive roots (modulo the power of an odd prime) actually already tells us that $m=39$ is the smallest exponent that works. We have $3^3=1+2\cdot13$, and raising that equation to power $13$, using the binomial formula on the right and the fact that $13\mid\binom{13}k$ for all $k=1,2,\ldots,12$, gives that $3^{39}\equiv1$. No proper factor of $39$ works because $3^{13}\equiv3\pmod{13}$ by Little Fermat.
This implies that $L=\Bbb{F}_{3^{39}}$. The reason is that the multiplicative groups of finite fields are always cyclic. As $13^2\mid |L^*|$ we can tell that $L$ has a root of unity of order $13^2$. Hence all such roots are in $L$, and no smaller field will do.
So $L$ is a degree $13$ extension of $K$. But $[K(\beta):K]$ is the degree of the minimal polynomial of $\beta$ over $K$. We can thus conclude that the minimal polynomial $m(x)$ of $\beta$ over $K$ has degree $13$. On the other hand, $\beta$ is a zero of $f(x)$, so $m(x)\mid f(x)$. The conclusion is that $m(x)=f(x)$, and hence $f(x)$ is irreducible.
A: Yes, there is a general trick. Notice that every element of the field $\mathbb{F}_{p^n}$ satisfies the relation $f_n(a) = a^{p^n} - a = 0$. In particular the minimal polynomial of a primitive element $a \in \mathbb{F}_{p^n}$ must divide this polynomial. Thus to find a polynomial of degree $n$ irreducible we must find an irreducible degree $n$ factor of the polynomial $f_n(x) \in \mathbb{F}_p[x]$.
Of course, in your case it is also likely to be helpful that there are no nontrivial intermediate fields of $\mathbb{F}_{p^{13}}/\mathbb{F}_p$.
