with squarefree polynomials , which are pairwise coprime. Since we are in a field, we can assume that is monic. Since has a unique factorization we can take to be the product of all irreducible divisors of with , where is the number such that divides but does not, so such a decomposition exists.
If is in the desired form, we have for the derivative of :
Now let . For every irreducible polynomial dividing we can determine in the following way: must divide for some value of (then it does not divide any other ). Then for all the of the th summand in equation (1) is at least and for the th summand it is ( is not divisible by since is squarefree) if and 0 if (because of the factor in that summand). So we find if and if (equality holds because ). So we obtain
Now we define two sequences and by and
Then set if and if and set . By induction one finds
So for it follows , so for we can continue as long as is non-constant. When is constant, we have
Assume , then with
so we can set and have . Now we can decompose by using the algorithm recursively.
In practice one can easily compute using Euclid’s algorithm. Then one computes the sequences and to get the . 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.
|Date of creation||2013-03-22 14:54:20|
|Last modified on||2013-03-22 14:54:20|
|Last modified by||mathwizard (128)|