# Can this algorithm be fixed?

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?

• The linked source has non-congruence in line 2 (which makes more sense). – Andreas Blass Nov 21 '18 at 15:12
• Perhaps replacing line 5 by "do if $gcd(x^{p^{n/r}}-x,f)\neq 1$" would suffice ? Just a silly thought... – user120527 Nov 21 '18 at 15:22
• @user120527 I think I don't completely get the reasoning behind your suggestion (completely on me, probably). From my understanding, lines 4-6 work to sort out reducible polynomials, but not necessarily all of them - with your line change, irreducible polynomials still 'reach the end', but I don't quite see how all reducible ones would be sorted out. – polynomial_donut Nov 21 '18 at 19:05
• This algorithm gives the wrong answer if and only if $f$ is a square-free product of lower degree irreducible polynomials $f(x)=p_1(x)p_2(x)\cdots p_k(x)$, $p_i$ irreducible for all $i$, such that $n$ is the least common multiple of the degree os the factors $p_i(x)$. – Jyrki Lahtonen Nov 22 '18 at 6:28
• Anyway, as Eric Wofsey's answer explains, any product of a linear, an irreducible quadratic and an irreducible cubic will pass this test $n=3+2+1=6=lcm\{3,2,1\}$. Similarly a product of distinct irreducible polynomials of degrees $5,2,2,1$ will pass the test as $5+2+2+1=10=lcm\{5,2,2,1\}$. I don't see a remedy other than to calculate $\gcd(f,x^{p^{n/r}}-x)$ in step 5 rather than simply check non-divisibility. – Jyrki Lahtonen Nov 22 '18 at 6:45

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"