My lecture notes says:
Consider the polynomial $X^3-X+1$ in $\mathbb F_{3}[X]$. We can test irreducibility of $X^3-X+1$ by doing two gcd computations, namely $\gcd(X^3-X, X^3-X+1)$ and $\gcd(X^{3^2}-X, X^3-X+1)$.
Rabin's test for irreducibility:
Let $f(x)$ be a polynomial of degree $n$ over $\mathbb{F}_p$. Then $f$ is irreducible over $\mathbb{F}_p$ if and only if:
- $f(x)$ divides $x^{p^n}-x$, and
- $\gcd\bigl(x^{p^{n/q}}-x,f(x))=1$ for each prime divisor $q$ of $n$.
Now $n=3$, and $2$ is not a (prime) divisor of $3$. So where does the second gcd computation come from?
I thought about how $3 \equiv 6$ in $\mathbb F_{3}[X]$, which would have $2$ as its prime divisor. Is that it, or is there an other explanation?