On the Complexity of Computing the Greatest Common Divisor of Several Univariate Polynomials
On the Complexity of Computing the Greatest Common Divisor of Several Univariate Polynomials
复制标题
论计算多个单变量多项式最大公约数的复杂性
DOI：
10.1007/3-540-59175-3_100
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
L. González
中科院分区：
文献类型：
--
作者：
L. González
本文给出了一个确定性算法，在考虑整数系数时，在已知的最佳复杂性界下，计算整数域上系数的多个一元多项式的最大公约数。更确切地说，如果n是要计算其最大公约数的t+1个整数多项式的次数的界限，并且M是这些多项式的大小的界限，则通过涉及大小为O（n4M）的整数的O（tn3）算术运算来计算这样的最大公约数（这与t无关）。
This paper is devoted to present a deterministic algorithm computing the greatest common divisor of several univariate polynomials with coefficients in an integral domain with the best known complexity bound when integer coefficients are considered. More precisely, if n is a bound for the degree of the t+1 integer polynomials whose greatest common divisor is to be computed and M is a bound for the size of those polynomials then such greatest common divisor is computed by means of O(tn3) arithmetic operations involving integers whose size is in O(n4M) (which is independent of t).