欧几里德算法

欧几里得算法，通常被称为欧几里得算法，是一种确定最大公约数 (GCD) 的有效方法，即可以均匀且无余数地整除两个整数（数字）的最大数字。 它最初由希腊数学家欧几里得在公元前 300 年的著作《几何原本》中描述，因此得名。 作为仍在使用的最早的算法之一，算法是根据预定原则执行计算的循序渐进的过程。 它是多种数论和密码学计算的组成部分，可用于简化分数。 欧几里得算法有几个理论上和现实中的用途。 它用于在模算术中进行除法以及简化分数。 该算法被用于通过分解非常大的合数以及保护互联网通信的密码协议来破解这些密码系统的两种策略中。

可以使用欧几里得方法发现两个正整数的最大公约数。 可以均匀地除以两个数字的最大整数称为 GCD。 分解两个整数并将公共素数相乘是找到 GCD 的一种简单方法。

GCD 的基本欧几里得算法

以下事实构成了算法的基础。

• 如果我们通过从较大的整数中减去较小的整数来降低较大的整数，则 GCD 保持不变。 因此，如果我们不断扣除两个数字中较大的一个，我们就会得到 GCD。
• 现在，如果我们除以较小的数字而不是减去它，那么当我们达到最终结果 0 时，该过程就会停止。

下面提供了使用欧几里得方法计算 GCD 的递归函数

输出

GCD(10, 15) = 5
GCD(35, 10) = 5
GCD(31, 2) = 1
.................................
Process executed in 1.11 seconds
Press any key to continue.

时间复杂度：O (Log min(a, b))

辅助空间：O (Log (min(a,b))

扩展欧几里得算法

此外，扩展欧几里得方法发现整数系数 x 和 y，使得 axe + by = gcd(a, b) 为真。

递归调用 gcd(b%a, a) 的结果被扩展欧几里得算法用于更新 gcd(a, b) 的结果。 令 x1 和 y1 为递归导出的 x 和 y 值。 使用下面显示的方程更新 x 和 y。

下面显示了上述策略的应用

输出

gcd(35, 15) = 5
..........................
Process executed in 1.11 seconds
Press any key to continue.

时间复杂度：O (log N)

辅助空间：O (log N)

扩展算法如何工作？

扩展算法有什么用？

当 a 和 b 互质（或 gcd 为 1）时，扩展欧几里得方法非常有用。 由于 y 是“b 模 a”的模乘法逆元，x 是“a 模 b”的逆元， 例如，RSA 公钥加密方法中的一个关键步骤是计算模乘法逆元。