Determine whether a polynomial is irreducible Consider the polynomial $P=X^5-X-1\in\Bbb{F}_3[X]$. I want to show that $P$ is irreducible. We can easily check it has no roots, so the only way it could not be irreducible is by being a product of two polynomials of degree $2$ and $3$ respectively. So I determine all the irreducible polynomials of degree $2$ in $\Bbb{F}_3[X]$. These are $$X^2+1;{~~} X^2+X-1 {~~}\text{and}{~~}X^2-X-1.$$
Finally I check using the Euclidean division algorithm that none of those polynomials divides $P$, which concludes the proof.
My question is this:  is there a more efficient way to do this? I had to first determine all the polynomials of a given degree ($2$) and then apply Euclidean algorithm to each of them. That is quite some work, and we're still considering polynomials of relatively small degree, and fields of small cardinal. I can't imagine applying the same reasoning to determine whether $Q=X^9-X^2-1\in\Bbb{F}_{17}[X]$ is irreducible.
So, is there a more efficient method to determine irreducibility, at least in the case of polynomials of small degree over small fields?
 A: I post this to give this question an answer. The idea has already been stated by Jyrki Lahtonen as a comment.
After the root check, it suffices to see that $P$ does not have an irreducible factor of degree $2$. Such a factor would also be a divisor of $X^9 - X$, as $X^{q^n} - X$ is the product of all irreducible polynomials over $\mathbb{F}_q$ whose degree divides $n$.
So you can finish your exercise in a faster way by computing $\gcd(P,X^9-X) = 1$ with the Euclidean algorithm.
The process can still be optimized a bit.

*

*As $X^9 - X = X(X^8 - 1)$, it suffices to compute $\gcd(P,X^8 - 1)$.

*As a little bonus over the comment of Jyrki Lahtonen, let us discuss this extra optimization if you knowing the theory of cyclotomic polynomials. Let $\Phi_n$ be the $n$-th cyclotomic polynomial. We have the factorization $X^8 - 1 = \Phi_8 \Phi_4 \Phi_2 \Phi_1$. The degrees are $\deg\Phi_8 = 4$, $\deg\Phi_4 = 2$, $\deg\Phi_2 = \deg\Phi_1 = 1$ (in general, $\deg\Phi_n$ is the Euler Phi-function of $n$). So an irreducible factor of $X^8 - 1$ divides either $\Phi_8 = X^4 + 1$ or $\Phi_4 = X^2 + 1$. So it suffices to compute
$$
\gcd(P,X^4 + 1)\quad\text{and}\quad\gcd(P,X^2+1)\text{.}
$$
