是否有比欧几里得更快的算法来查找 GCD

Question

有没有比欧几里得算法更快的算法来查找两个数字的gcd是否为1？

Answer 1

二进制 GCD 算法的性能往往优于欧几里得算法。 这个想法是用减法代替除法和使用

gcd(a,b) = gcd(a, b-a)

如果 a 是奇数，B 是偶数，则

gcd(a,b) = gcd(a,b/2)

可以作为简单的位操作实现。

如果您正在寻找更快的东西，这里和这里有算法可以并行运行二进制算法。