论文部分内容阅读
求两个正整数a、b的最大公因子gcd(a，b)通常使用经典的Euclid算法．因共需O(1nN)次带余除法，每次带余除法耗时O(1n^2N)，所以Euclid算法耗时O(1n^3N)，这里N=max(a，b)，文献[1，Corollary 2．1]和[2，例5]就是这样粗略估算的．然而，如果在实现算法