Factoring multivariate polynomials over the integers
Factoring multivariate polynomials over the integers
复制标题
DOI：
10.1145/1086814.1086819
复制
发表时间：
1973-12
影响因子：
2
通讯作者：
Paul S. Wang;L. Rothschild
中科院分区：
文献类型：
--
作者：
Paul S. Wang;L. Rothschild
本文给出了一个求多元整系数多项式不可约因子的算法。该算法首先对除一个变量外的所有变量进行替换。然后通过已知的方法分解该单变量多项式，该方法使用Berlekamp算法来分解有限域上的单变量多项式。在此分解完成后，多元因子恢复从一元的一种亨塞尔算法。在某些特殊情况下，本文提出了一些能大大提高计算速度的方法.
This paper gives an algorithm for finding the irreducible factors of any multivariate polynomial with integer coefficients. The algorithm begins by making substitutions for all but one of the variable. This univariate polynomial is then factored by a known method, which uses an algorithm of Berlekamp for factoring univariate polynomials over finite fields. After this factorization is done, the multivariate factors are recovered from the univariate ones by a kind of Hensel algorithm. A number of ideas are given which greatly speed the computation in some special cases.