squarefree factorization


Given a polynomialPlanetmathPlanetmath Aβˆˆπ”½p⁒[X], where p is a prime and 𝔽p is the field with p elements, we want to find a decomposition

A=∏i=1nAii

with squarefreeMathworldPlanetmath polynomials Ai, 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 Ai to be the productPlanetmathPlanetmath of all irreduciblePlanetmathPlanetmath divisorsMathworldPlanetmathPlanetmath P of A with vP⁒(A)=i, where vP⁒(A) is the number such that PvP⁒(A) divides A but PvP⁒(A)+1 does not, so such a decomposition exists.

If A is in the desired form, we have for the derivative Aβ€² of A:

Aβ€²=βˆ‘i=1n∏jβ‰ ii⁒Ajj⁒Ai′⁒Aii-1. (1)

Now let T:=gcd⁑(A,Aβ€²). For every irreducible polynomial P dividing T we can determine vP⁒(T) in the following way: P must divide Am for some value of m (then it does not divide any other Ai). Then for all iβ‰ m the vP of the ith summand in equation (1) is at least m and for the mth summand it is m-1 (Amβ€² is not divisible by P since Am is squarefree) if p∀m and 0 if p|m (because of the factor m in that summand). So we find vP⁒(T)=m-1 if p∀m and vP⁒(T)=m if p|m (equality holds because T|A). So we obtain

T=gcd⁑(A,Aβ€²)=∏p∀iAii-1⁒∏p|iAii.

Now we define two sequencesMathworldPlanetmath (Ti) and (Vi) by T1=T and

V1=AT=∏p∀iAi.

Then set Vk+1=gcd⁑(Tk,Vk) if p∀k and Vk+1=Vk if p|k and set Tk+1=TkVk+1. By inductionMathworldPlanetmath one finds

Vk =∏iβ‰₯k,p∀iAi;
Tk =∏iβ‰₯k-1,p∀iAii-k⁒∏p|iAii.

So for p∀k it follows Ak=VkVk+1, so for p∀k we can continue as long as Vk is non-constant. When Vk is constant, we have

Tk-1=∏p|iAii.

Assume Ai⁒(X)=ak⁒Xk+…+a1⁒X+a0, then with i=l⁒p

Ail⁒p=akl⁒p⁒Xk⁒l⁒p+…+a1l⁒p⁒Xl⁒p+a0l⁒p=ak⁒Xk⁒l⁒p+…+a1⁒Xl⁒p+a0,

so we can set Y:=Xp and have Tk-1=Up⁒(X)=U⁒(Y). Now we can decompose U by using the algorithmMathworldPlanetmath recursively.

In practice one can easily compute T using Euclid’s algorithm. Then one computes the sequences (Vi) and (Ti) to get the Ak. 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 factorizationMathworldPlanetmath
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