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?
Best Answer
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.