New Algorithms for Polynomial Square-Free Decomposition over the Integers

Abstract

Previously-known algorithms for polynomial square-free decomposition rely on greatest common divisor (gcd) computations over the same coefficient domain where the decomposition is to be performed. In particular, gcd of the given polynomial and its first derivative (with respect to some variable) is obtained to begin with. Application of modular homomorphism and p-adic construction (multivariate case) or the Chinese remainder algorithm (univariate case) results in new square-free decomposition algorithms which, generally speaking, take less time than a single gcd between the given polynomial and its first derivative. The key idea is to obtain one or several “correct” homomorphic images of the desired square-free decomposition first. This provides information as to how many different square-free factors there are, their multiplicities and their homomorphic images. Since the multiplicities are known, only the square-free factors need be constructed. Thus, these new algorithms are relatively insensitive to the multiplicities of the square-free factors.