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
is the desired factorization, we have thus
and
If we set, and, we get that
and
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