Factorization of polynomials over finite fields

Remarks

Stage 2 uses that $x^{q^d} - x$ is the product of all monic irreducible polynomials in $\F_q[x]$ whose degree divides $d$. So $h_1 = \gcd(g, x^q - x)$, and $h_d$ is the gcd of $x^{q^d} - x$ with $g$ divided by $h_1 \cdots h_{d-1}$. In stage 1, if $f' = 0$ then $f$ is a $p$-th power, where $p$ is the characteristic, since every element of $\F_q$ is a $p$-th power. Stage 3 is usually done with a randomised method, such as the Cantor–Zassenhaus algorithm; Berlekamp's algorithm is a deterministic alternative to stages 2 and 3. Example: over $\F_2$, $g = x^3 + 1$ is square-free, $\gcd(g, x^2 - x) = x + 1$, so $h_1 = x + 1$ and $h_2 = x^2 + x + 1$. Non-example: $(x + 1)(x^3 + 1) = (x + 1)^2 (x^2 + x + 1)$ is not square-free, so stage 2 does not apply before stage 1.