squarefree factorization

Given a polynomial $A\\in\\mathbb{F}_{p}[X]$ , where $p$ is a prime and $\\mathbb{F}_{p}$ is the field with $p$ elements, we want to find a decomposition

A=\\prod_{i=1}^{n}A_{i}^{i}

with squarefree polynomials $A_{i}$ , which are pairwise coprime. Since we are in a field, we can assume that $A$ is monic.Since $A$ has a unique factorization we can take $A_{i}$ to be the product of all irreducible divisors $P$ of $A$ with $v_{P}(A)=i$ , where $v_{P}(A)$ is the number such that $P^{v_{P}(A)}$ divides $A$ but $P^{v_{P}(A)+1}$ does not, so such a decomposition exists.

If $A$ is in the desired form, we have for the derivative $A^{\\prime}$ of $A$ :

A^{\\prime}=\\sum_{i=1}^{n}\\prod_{j\eq i}iA_{j}^{j}A_{i}^{\\prime}A_{i}^{i-1}.

(1)

Now let $T:=\\gcd(A,A^{\\prime})$ . For every irreducible polynomial $P$ dividing $T$ we can determine $v_{P}(T)$ in the following way: $P$ must divide $A_{m}$ for some value of $m$ (then it does not divide any other $A_{i}$ ). Then for all $i\eq m$ the $v_{P}$ of the $i$ th summand in equation (1) is at least $m$ and for the $m$ th summand it is $m-1$ ( $A_{m}^{\\prime}$ is not divisible by $P$ since $A_{m}$ is squarefree) if $p\mid m$ and 0 if $p|m$ (because of the factor $m$ in that summand). So we find $v_{P}(T)=m-1$ if $p\mid m$ and $v_{P}(T)=m$ if $p|m$ (equality holds because $T|A$ ). So we obtain

T=\\gcd(A,A^{\\prime})=\\prod_{p\mid i}A_{i}^{i-1}\\prod_{p|i}A_{i}^{i}.

Now we define two sequences $(T_{i})$ and $(V_{i})$ by $T_{1}=T$ and

V_{1}=\\frac{A}{T}=\\prod_{p\mid i}A_{i}.

Then set $V_{k+1}=\\gcd(T_{k},V_{k})$ if $p\mid k$ and $V_{k+1}=V_{k}$ if $p|k$ and set $T_{k+1}=\\frac{T_{k}}{V_{k+1}}$ . By induction one finds

	$\\displaystyle V_{k}$	$\\displaystyle=\\prod_{i\\geq k,p\mid i}A_{i};$
	$\\displaystyle T_{k}$	$\\displaystyle=\\prod_{i\\geq k-1,p\mid i}A_{i}^{i-k}\\prod_{p\|i}A_{i}^{i}.$

So for $p\mid k$ it follows $A_{k}=\\frac{V_{k}}{V_{k+1}}$ , so for $p\mid k$ we can continue as long as $V_{k}$ is non-constant. When $V_{k}$ is constant, we have

T_{k-1}=\\prod_{p|i}A_{i}^{i}.

Assume $A_{i}(X)=a_{k}X^{k}+\\dots+a_{1}X+a_{0}$ , then with $i=lp$

A_{i}^{lp}=a_{k}^{lp}X^{klp}+\\dots+a_{1}^{lp}X^{lp}+a_{0}^{lp}=a_{k}X^{klp}+..%.+a_{1}X^{lp}+a_{0},

so we can set $Y:=X^{p}$ and have $T_{k-1}=U^{p}(X)=U(Y)$ . Now we can decompose $U$ by using the algorithm recursively.

In practice one can easily compute $T$ using Euclid’s algorithm. Then one computes the sequences $(V_{i})$ and $(T_{i})$ to get the $A_{k}$ . The algorithm is needed as a first step when one wants to find the prime decomposition of a polynomial, because it reduces the problem to the problem of factoring a squarefree polynomial.