什么是检查两个给定数字互质的最快方法是什么？ [英] What is the fastest way to check if two given numbers are coprime?

问题描述

一种方法是，计算它们的 GCD 并检查它是否是1。

One way is to calculate their gcd and check if it is 1.

有没有一些更快捷的方式？

Is there some faster way?

推荐答案

欧几里德算法（单位计算 GCD ）是非常快的。当从均匀随机抽取两个号码[1，N] ，步骤，计算平均数的 GCD 是 O（log n）的。需要对每个步骤的平均计算时间是在二次的位数。

The Euclidean algorithm (computes gcd) is very fast. When two numbers are drawn uniformly at random from [1, n], the average number of steps to compute their gcd is O(log n). The average computation time required for each step is quadratic in the number of digits.

有执行稍微更好（即，每一个步骤是在次二次的位数）的替代品，但它们只对非常大的整数。参见，例如，在Schönhage的算法和次二次整数GCD计算。

There are alternatives that perform somewhat better (i.e., each step is subquadratic in the number of digits), but they are only effective on very large integers. See, for example, On Schönhage's algorithm and subquadratic integer gcd computation.

这篇关于什么是检查两个给定数字互质的最快方法是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！