扩展欧几里得算法计算器

扩展欧几里得算法计算器可以计算两个整数的最大公约数 (GCD)，并求出贝祖系数——即满足 gcd(a, b) = s·a + t·b 的整数 s 和 t。除了计算 GCD，此工具还提供完整的动画分步除法表、回代过程和模反元素计算，非常适合数论课程、密码学研究和竞赛编程。

什么是扩展欧几里得算法？

扩展欧几里得算法 (EEA) 是欧几里得经典 GCD 算法的扩展。基本算法通过连续除法寻找 gcd(a, b)，而扩展版本则同步追踪两个整数序列，记录每一步的余数如何表示为原始输入的线性组合。

算法原理

扩展欧几里得算法在每个除法步骤中维护三组值 — (r, s, t)：

1. 初始化：r₀ = |a|, r₁ = |b|, s₀ = 1, s₁ = 0, t₀ = 0, t₁ = 1
2. 每一步：计算商 q = ⌊rₙ₋₁ / rₙ⌋，然后更新 rₙ₊₁ = rₙ₋₁ − q·rₙ, sₙ₊₁ = sₙ₋₁ − q·sₙ, tₙ₊₁ = tₙ₋₁ − q·tₙ
3. 当余数 = 0 时停止；前一个余数即为 gcd(a, b)
4. 对应的 s 和 t 值即为贝祖系数

分步示例：gcd(252, 105)

结果：gcd(252, 105) = 21，贝祖等式为：21 = 1 × 252 + (−2) × 105。您可以使用上面的计算器亲自尝试以获取精确系数。

扩展欧几里得算法的应用

1. 模反元素（密码学）

最重要的应用是计算模反元素。如果 gcd(a, m) = 1，则贝祖系数 s 满足：

模反元素在 RSA 加密（计算私钥指数 d）、Diffie-Hellman 密钥交换和椭圆曲线密码学中至关重要。

2. 求解线性丢番图方程

方程 ax + by = c 有整数解当且仅当 gcd(a, b) 能整除 c。如果是这样，一个特解为 x₀ = s·(c/d), y₀ = t·(c/d)，其中 d = gcd(a, b)，s, t 是贝祖系数。

3. 中国剩余定理

扩展欧几里得算法用于中国剩余定理的构造性证明和计算——通过计算模数的模反元素来寻找满足 x ≡ a₁ (mod m₁) 和 x ≡ a₂ (mod m₂) 的 x。

4. 分数约简和最小公倍数

gcd(a, b) = 1 确认 a/b 已经是最简形式。最小公倍数计算公式为 lcm(a, b) = |a·b| / gcd(a, b)。

贝祖系数不是唯一的

贝祖系数 s 和 t 并不唯一。如果 (s, t) 是一个解，那么对于任何整数 k，(s + k·(b/d), t − k·(a/d)) 也是一个解，其中 d = gcd(a, b)。本算法返回满足 |s| ≤ |b/d| 且 |t| ≤ |a/d| 的解。

时间复杂度

扩展欧几里得算法的运行时间为 O(log min(a, b)) 次迭代——与基本欧几里得算法相同。根据拉梅定理 (Lamé's theorem)，步骤数永远不会超过较小输入数字位数的 5 倍。这使得它即使对于密码学应用中使用的大整数也极其高效。

常见问题解答

什么是扩展欧几里得算法？

扩展欧几里得算法扩展了欧几里得 GCD 算法，不仅可以计算最大公约数，还能计算满足 gcd(a, b) = s·a + t·b 的贝祖系数 s 和 t。它在除法过程中追踪每个余数如何表示为 a 和 b 的线性组合。

什么是贝祖系数？

贝祖系数是根据贝祖等式（数论中的一个定理）保证存在的整数 s 和 t。它们满足 gcd(a, b) = s·a + t·b，并通过扩展欧几里得算法高效计算。它们被用于模反元素计算、求解丢番图方程和中国剩余定理。

如何使用扩展欧几里得算法求模反元素？

如果 gcd(a, b) = 1（a 和 b 互质），则贝祖系数 s 满足 s·a ≡ 1 (mod b)。a 模 b 的模反元素即为 s mod b（调整为正数）。此计算器直接在结果中显示该值。

什么时候模反元素不存在？

a 模 m 的模反元素存在当且仅当 gcd(a, m) = 1。如果 gcd(a, m) > 1，则不存在整数 x 满足 a·x ≡ 1 (mod m)。

扩展欧几里得算法的时间复杂度是多少？

O(log min(a, b)) 次除法，与基本欧几里得算法相同。根据拉梅定理，步骤数受限于较小输入数字位数的 5 倍，因此非常高效。

更多资源

• 扩展欧几里得算法 - 维基百科
• 贝祖等式 - 维基百科
• 模反元素 - 维基百科