# 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\neq 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\neq 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\nmid m$ and 0 if $p|m$ (because of the factor $m$ in that summand). So we find $v_{P}(T)=m-1$ if $p\nmid m$ and $v_{P}(T)=m$ if $p|m$ (equality holds because $T|A$). So we obtain

 $T=\gcd(A,A^{\prime})=\prod_{p\nmid 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\nmid i}A_{i}.$

Then set $V_{k+1}=\gcd(T_{k},V_{k})$ if $p\nmid 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\nmid i}A_{i};$ $\displaystyle T_{k}$ $\displaystyle=\prod_{i\geq k-1,p\nmid i}A_{i}^{i-k}\prod_{p|i}A_{i}^{i}.$

So for $p\nmid k$ it follows $A_{k}=\frac{V_{k}}{V_{k+1}}$, so for $p\nmid 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.

Title squarefree factorization  SquarefreeFactorization 2013-03-22 14:54:20 2013-03-22 14:54:20 mathwizard (128) mathwizard (128) 5 mathwizard (128) Algorithm msc 11Y99 msc 11C99 msc 13P05 msc 13M10 CantorZassenhausSplit