Factorization of Polynomials - Square-free Factorization

Square-free Factorization

If two or more factors of a polynomial are identical to each other, then the polynomial is multiple of the square of this factor. In the case of univariate polynomials, this results in multiple roots. In this case, then the multiple factor is also a factor of the polynomial's derivative (which respect to any of the variables, if several), which itself is a polynomial of lower degree. In the case of univariate polynomials over the rationals (ore more generally over a field of characteristic zero, Yun's algorithm exploits this remark to factorize efficiently the polynomial into factors that are not multiple of a square and are therefore called square-free. To factorize the initial polynomial, it suffices to factorize each square-free factors. This algorithm is therefore the first step of almost all polynomial factorization algorithms.

Yun's algorithm extends easily to the multivariate case by considering a multivariate polynomial as an univariate polynomial over a polynomial ring.

In the case of a polynomial over a finite field, Yun's algorithm applies only if the degree is smaller than the characteristic, because, otherwise, the derivative of a non zero polynomial may be zero (over the field with p elements, the derivative of a polynomial in xp is always zero). Nevertheless a succession of GCD computations, starting from the polynomial and its derivative, allows to compute the square-free decomposition; see Polynomial factorization over finite fields#Square-free factorization.

Most factorization algorithms, including all the most efficient ones, begin by a square-free factorization.