实现RSA算法：高效寻找大数互质数的最优方法

首先明确核心结论：如果你的目标数是RSA中的φ(n)（即欧拉函数值，由两个大质数p、q计算得φ(n)=(p-1)(q-1)），最大的与φ(n)互质且小于φ(n)的数就是φ(n)-1——因为相邻整数的最大公约数必然为1，这是数学定理，无需任何遍历检查，直接取这个值即可，这是效率最高的方案。

如果你的场景中不能直接取b-1（比如b不是φ(n)，或有额外限制），可以用以下优化方法替代逐个计算GCD：

• 基于质因数分解的快速判断

  1. 先对目标数b做一次质因数分解，得到所有不同的质因数集合{p₁, p₂, ..., pₖ}
  2. 从b-1开始向下遍历每个数a：
     • 检查a是否能被任何一个pᵢ整除（即a % pᵢ == 0）
     • 若所有pᵢ都无法整除a，则gcd(a,b)=1，直接返回a
       这种方法的优势在于质因数分解只需做一次，后续的检查是简单的取模运算，比反复调用欧几里得算法计算GCD更高效，尤其当b的质因数数量较少时。

• 利用RSA场景特性简化
  在RSA密钥生成中，φ(n)=(p-1)(q-1)，其中p、q是大质数。此时φ(n)的质因数就是(p-1)和(q-1)的质因数的并集——而分解(p-1)和(q-1)本来就是流程中的必要步骤，你可以直接复用这些质因数结果，无需额外分解φ(n)，进一步节省计算资源。

内容的提问来源于stack exchange，提问作者rastr__