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
Canonical name	SquarefreeFactorization
Date of creation	2013-03-22 14:54:20
Last modified on	2013-03-22 14:54:20
Owner	mathwizard (128)
Last modified by	mathwizard (128)
Numerical id	5
Author	mathwizard (128)
Entry type	Algorithm
Classification	msc 11Y99
Classification	msc 11C99
Classification	msc 13P05
Classification	msc 13M10
Related topic	CantorZassenhausSplit