Square-free factorization of polynomials over finite fields

Question

For any $f\in\mathbb{F}_q[X]$, I want to derive an algorithm which computes a factorization $$f=\prod_{i=1}^kf_i^i\tag{1}$$ with square-free polynomials $f_i$.

---

My Ideas:

• If $f'=0$, we're done ($f\in\mathbb{F}_q$)
• Otherwise consider $$g_1:=\gcd(f,f')$$
• If $g_1=1$ we're done ($f$ is square-free)
• Otherwise $$f_1:=\frac{f}{g_1}$$ is square-free
• Now consider $$g_2:=\gcd(g_1,g_1')$$
• If $g_2=1$ we're done ($f=f_1g_1$ is a square-free factorization)
• Otherwise $$f_2:=\frac{g_1}{g_2}$$ is square-free
• And so on ...

This process yields a square-free factorization $$f=f_1\cdots f_{k-1}g_k\tag{2}$$ after $k<\infty$ steps.

However, (2) is not the factorization (1) I'm searching for. How can I find the factorization (1) and what's the benefit from the factorization (1) in comparison to factorization (2)?

---

EDIT Elsewhere, I've found an algorithm which exactly does what I've described, but returns $$h_i:=\frac{f_i}{f_{i+1}}\;\;\;\;\;(1\le i<k,f_k:=g_k)$$ and states the $h_i$ would fulfill $$f=\prod_{i=1}^kh_i^i$$ I don't see why this should hold.

Answer 1

$\newcommand{\FF}{\mathbb{F}}$ Unfortunately, you've run into trouble in your first step. You cannot conclude from $f^{\prime} = 0$ that $f\in\FF_{q}$.

Consider $f = X^6 + 1\in\FF_{3}[X]$. Then $f^\prime = 6X^5 = 0$, since the characteristic is $3$. Dealing with this problem is the main feature of the positive characteristic case.

Fortunately, there is a way around this. (Assume $q=p^m$ with $p$ prime.) It turns out that if the derivative of $f$ is zero, then $f$ has a $p$-th root. For, suppose $f\in\FF_q[X]$ has zero derivative: $f^\prime = 0$. Then $f$ must have the form $$f = a_0 + a_pX^p + a_{2p}X^{2p} + \cdots + a_{kp}X^{kp},$$ where $a_{kp}\neq 0$, for some $k$. Define $$g = a_0^{1/p} + a_{p}^{1/p}X + a_{2p}^{1/p}X^2 + \cdots + a_{kp}^{1/p}X^k.$$ (Here, for $u\in\FF_{q}$, the element $u^{1/p} = u^{p^{m-1}}$ satisfies $\left( u^{1/p}\right)^p = u$.) Then you can check that $g^p = f$ by using the "Freshman's Dream" $(\alpha + \beta)^{p^i} = \alpha^{p^i} + \beta^{p^i}$, for $\alpha,\beta\in\FF_q$.

So, given $f\in\FF_q[X]$ with $f^\prime = 0$, you can calculate $g\in\FF_q[X]$ with $g^p = f$, and (recursively) apply your square-free factorisation to $g$ and then take the $p$-th power to get the factorisation for $f$ itself.