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.