Square-free Polynomial - Yun's Algorithm

Yun's Algorithm

In this section we describe Yun's algorithm for the square-free decomposition of univariate polynomials over a field of characteristic 0. It proceed by a succession of GCD computations and exact divisions.

The input is thus a non zero polynomial f, and the first step of the algorithm consists in computing the GCD a0 of f and its formal derivative f'.

If


f = a_1 a_2^2 a_3^3 \cdots a_k^k

is the desired factorization, we have thus


a_0 = a_2^1 a_3^2 \cdots a_k^{k-1},

f/a_0 = a_1 a_2 a_3 \cdots a_k

and


f'/a_0 = \sum_{i=1}^k i a_i' a_1 \cdots a_{i-1} a_{i+1} \cdots a_k.

If we set, and, we get that


\gcd(b_1,d_1) = a_1,

b_2=b_1/a_1 = a_2 a_3 \cdots a_n,

and


c_2=d_1/a_1 = \sum_{i=2}^k (k-1) a_i' a_2 \cdots a_{i-1} a_{i+1} \cdots a_k.

Iterating this process until we find all the

This is formalized into an algorithm as follows:


repeat

until
Output

The degree of and is one less than the degree of As is the product of the the sum of the degrees of the is the degree of As the complexity of GCD computations and divisions increase more than linearly with the degree, it follows that the total running time of the "repeat" loop is less than the running time of the first line of the algorithm, and that the total running time of Yun's algorithm is upper bounded by twice the time needed to compute the GCD of and and the quotient of and by their GCD.

Read more about this topic:  Square-free Polynomial