基于广义子结式和模运算的多项式组最大公因式计算方法

Computing the Greatest Common Divisor of a Polynomial System with Generalized Subresultants and Modular Arithmetic

求解多项式的最大公因式是计算机代数中的一个基本问题,同时也是结式理论的一个重要应用领域.经典的欧几里得算法在求解一组多项式最大公因式问题时,易发生系数膨胀问题.而模方法可以有效地将整系数多项式的系数规模控制在一定范围内,进而提高计算效率.文章将模方法应用于一组多项式最大公因式的求解问题中,通过建立同态映射下广义子结式和公因式的关系,给出模方法中良好素数的选取准则,利用Landau-Mignotte不等式给出多个多项式公因式系数的上界,从而将两个多项式的模方法理论推广到多个多项式的情形.与基于两个多项式最大公因式递归计算的方法相比,新方法可以一次计算模运算后的多项式的最大公因式,使得求解过程大大简化,计算效率得到有效提高.

Computing the greatest common divisor of polynomials is a fundamental problem in computer algebra and is one of the typical applications of subresultant theory.Euclidean algorithm is a classical method commonly used for computing the gcd of several univariate polynomials,where the phenomenon of coefficient inflation often appears.As a practical solution to this problem,the modular method can effectively control the size of coefficients and is helpful to achieve high computational efficiency.In this paper,a modular method for computing the gcd of several univariate polynomials is proposed.As the most key issue in modular arithmetic,a criteria for selecting good primes is presented by establishing the relationship between the generalized subresultants of a polynomial set and its greatest common divisor under homomorphic mapping.Besides,an upper bound for the coefficients of common factors for several polynomials is derived with the Landau-Mignotte inequality.Compared with the previous approach based on the recursive gcd computation of two polynomials,the new method can compute the gcd of several polynomials with a non-nested loop,which significantly simplifies the computing process and improves the computational efficiency.