Fast computation of GCDs
Fast computation of GCDs
复制标题
GCD 的快速计算
DOI：
10.1145/800125.804045
复制
发表时间：
1973
期刊：
影响因子：
--
通讯作者：
R. Moenck
中科院分区：
文献类型：
--
作者：
R. Moenck
将Schönhage提出的整数最大公约数（GCD）算法推广到所有具有快速乘法算法的欧氏区域。证明了如果两个N精度元素相乘的时间复杂度为O（NlogaN），则它们的GCD的计算时间复杂度为O（Nloga +1N）.因此，一个新的更快的算法多元多项式GCD的可以推导出新的界限有理函数操作。
An integer greatest common divisor (GCD) algorithm due to Schönhage is generalized to hold in all euclidean domains which possess a fast multiplication algorithm. It is shown that if two N precision elements can be multiplied in O(N loga N), then their GCD can be computed in O(N loga+1 N). As a consequence, a new faster algorithm for multivariate polynomial GCD's can be derived and with that new bounds for rational function manipulation.