中国剩余算法在多元多项式最大公因式提取中的应用

The Application of Chinese Remainder Algorithm in the Acquisition of the GreatestCommon Divisor from Multivariate Polynomial

本文研究了利用中国剩余算法提取多元整系数多项式的最大公因式的算法,首先将多项式通过同态映射进行逐元化简,直至化为一元多项式,并对一元多项式提取最大公因式,然后利用中国剩余算法对一元最大公因式进行逐元反复提升,最后可得到多元多项式的最大公因式。大量的算例表明该算法是求解多元整系数多项式最大公因式的一种有效算法。

The application of Chinese Remainder Algorithm to determine the greatest common divisor of multivariate polynomials is studied Using homostasis mapping, a multivariate polynondal is simplified step by step until only one main variable is left, and the greatest common divisor of the single variable polynomial is obtained by the extended Euclid Algorithm. Then, using the Chinese Remainder Algorithm raises the greatest common divisor from one vari- able to the original multivariate until the real greatest common divisor is gotten. It is an efficient algorithm to solve the greatest coanon divisor of multivariate polynomials.