# Square-free factorization of polynomials over finite fields

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.

$\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.