Deterministic test of irreducibility of polynomials over ${\mathbb{F}}_p$

Let $f(x)\in {\mathbb{F}}_p[x]$ be a polynomial over ${\mathbb{F}}_p$. We say that $f$ is irreducible if there do not exist polynomials $g,h$ of lower degree than $f$ such that $f \equiv gh \pmod p$.

Let $\mathcal{F}\supseteq {\mathbb{F}}_p$ be the algebraic closure of ${\mathbb{F}}_p$. Let $\alpha \in \mathcal{F}$ be a root of $f$, i.e. $f(\alpha) = 0$. If $f$ is an irreducible polynomial of degree $k$ then ${\mathbb{F}}_p[\alpha] = {\mathbb{F}}_{p^k}$.

``Fermat's Little Theorem for ${\mathbb{F}}_{p^k}$'' states that for all $\alpha\in{\mathbb{F}}_{p^k}$, if $\alpha\neq 0$ then $\alpha^{p^k-1}=1$ (equality in the field ${\mathbb{F}}_{p^k}$). Therefore $x-\alpha$ divides $\mathop{\rm g.c.d.\,}\nolimits (f,x^{p^k-1}-1)$ and since $f$ is irreducible, this implies that $f$ divides $x^{p^k-1}-1$. Moreover, $f$ does not divide $x^{p^{\ell}-1}-1$ for any $\ell<k$.

Remark 0.2   Above we sketched the ``only if'' part.

Combining the preceding two exercises we obtain a polynomial time algorithm for testing irreducibility of polynomials over ${\mathbb{F}}_p$.