Can this algorithm be fixed?

Question

Consider the following algorithm from page 240 of this pdf:

Irreducibility-Test(f)
1 $n ← \deg(f)$
2 if $X^{p^n} \not\equiv X (\mod f)$
3 $\quad$ then return "no"
4 for the prime divisors $r$ of $n$
5 $\quad$ do if $X^{p^{n/r}} \equiv X (\mod f)$
6 $\quad\quad$ then return "no"
7 return "yes"

Now, this algorithm basically checks if $\deg(f)$ is the smallest positive integer $d$ such that $ f \,\mid\, X^{p^d} - X$. The author says, that this implies irreducibility of $f$ and the algorithm relies on this (lines 4 to 7).

However, the assumed implication isn't right, see the answer to my question.

Is this algorithm simply wrong, or did I get something mixed up? If it is wrong, (how) can it be fixed? If it is correct, where is my misunderstanding?

Answer 1

The algorithm should work out with the change that user120527 suggested in a comment on this question.

If $f$ is irreducible, then if we have $f \,\mid\, P_d:=X^{q^d} - X$ for some $d > 0$, we know that $\deg(f) \,\mid\, d$ since $P_d$ is the squarefree product of all irreducible polynomials of $\mathbb{F}_q[X]$ whose degree divides $d$. Hence, $\deg (f) \leq d$.
This implies that $f \,\not\mid\, P_{n/r}$ for all prime factors $r$ of $n = \deg (f)$, because $\deg(f) > \deg(f)/r = n/r$, meaning that $f$ will pass through to the end in the algorithm above (note that $f \,\not\mid\, P_{n/r} \overset{f\, \text{prime}}\iff \gcd\left(f, P_{n/r}) \neq 1 \right)$.

Conversely, if $f$ is reducible, then we have $f = gh$ where $g$ is irreducible and $h$ is nontrivial. Assuming that the algorithm didn't cancel at line 2, we hence know that $g \,\mid\, f \,\mid\, P_{\deg(f)}$, so that $$ \deg (g) \,\mid\, \deg (f) $$ Now, since $h$ is nontrivial we know $\deg (g) < \deg (f)$, so that with the above, there is a prime factor $r$ of $\deg(f)$ such that $\deg (g) \,\mid\, \deg(f)/r = n/r$ and then, $$ g \,\mid\, P_{n/r} \iff \gcd\left(g, P_{n/r}\right) \neq 1 \implies \gcd\left(f, P_{n/r}\right) \neq 1 $$ and $f$ will fail the test in line 5 of the changed algorithm here:

Irreducibility-Test(f)
1 $n ← \deg(f)$
2 if $X^{p^n} \not\equiv X (\mod f)$
3 $\quad$ then return "no"
4 for the prime divisors $r$ of $n$
5 $\quad$ do if $\;\mathbf{\,\textbf{gcd}\left(f,\, X^{p^{n/r}} - X \right) \neq 1}$
6 $\quad\quad$ then return "no"
7 return "yes"