1. 简介
扩展欧几里得算法（Extended Euclidean Algorithm，简称EEA）是数论中的重要工具，广泛应用于密码学等领域。它不仅能够计算两个整数的最大公约数（GCD），还能找出这两个数的贝祖系数（Bézout's coefficients），即满足如下等式的整数 x 和 y：
$$ d = \gcd(a, b) = x \cdot a + y \cdot b $$
本文将介绍EEA的两种实现方式：递归版本（Recursive EEA）和迭代版本（Iterative EEA），并结合示例代码帮助理解其原理和应用。
2. 贝祖恒等式（Bézout’s Identity）
贝祖恒等式指出：任意两个整数 a 和 b 的最大公约数 d 可以表示为它们的线性组合。
例如：
$$ \gcd(5, 3) = 1 = -1 \cdot 5 + 2 \cdot 3 $$
贝祖恒等式的意义在于，它为我们提供了从最大公约数反推整数线性组合的可能性。而扩展欧几里得算法正是用于求解这样的贝祖系数 (x, y)。
2.1 前提假设
为了简化讨论，我们通常假设：
a和b都是正整数a > b
这些假设并不影响算法的通用性，因为：
- 如果
a或b为负数，取其绝对值即可 - 如果
a < b，交换两者顺序即可 - 如果
b = 0，则a就是最大公约数，此时贝祖系数为(1, 0)
3. 欧几里得算法（Euclidean Algorithm, EA）
欧几里得算法用于计算两个整数 a 和 b 的最大公约数。其核心思想是基于如下恒等式：
$$ \gcd(a, b) = \gcd(b, a \bmod b) $$
通过不断进行带余除法，直到余数为0，最后一个非零余数就是最大公约数。
例如：
$$ \begin{aligned} 254 &= 5 \cdot 44 + 34 \ 44 &= 1 \cdot 34 + 10 \ 34 &= 3 \cdot 10 + 4 \ 10 &= 2 \cdot 4 + 2 \ 4 &= 2 \cdot 2 + 0 \end{aligned} $$
最终得到最大公约数为 2。
4. 扩展欧几里得算法的递归实现（Recursive EEA）
递归版本的EEA与普通EA类似，但多了一步：在递归回溯过程中，逐步将最大公约数表示为 a 和 b 的线性组合。
4.1 核心思想
在递归过程中，我们不断回代，将每一步的余数用前两个数的线性组合表示，最终得到 d = x \cdot a + y \cdot b。
4.2 Java 实现
public static int[] extendedEuclidean(int a, int b) {
if (b == 0) {
return new int[]{a, 1, 0}; // d = a, x = 1, y = 0
}
int q = a / b;
int r = a % b;
int[] result = extendedEuclidean(b, r);
int d = result[0];
int x = result[1];
int y = result[2];
return new int[]{d, y, x - q * y};
}
4.3 示例
以 a = 254, b = 44 为例：
递归回溯过程中，我们逐步回代，最终得到：
$$ 2 = (-9) \cdot 254 + 52 \cdot 44 $$
5. 扩展欧几里得算法的迭代实现（Iterative EEA）
为了避免递归带来的栈开销，我们也可以用迭代方式实现EEA。
5.1 核心思想
每一步都维护当前余数的贝祖系数，通过线性组合的方式不断更新 x 和 y，直到余数为0。
5.2 Java 实现
public static int[] extendedEuclideanIterative(int a, int b) {
int x0 = 1, x1 = 0;
int y0 = 0, y1 = 1;
while (b != 0) {
int q = a / b;
int r = a % b;
int x = x1 - q * x0;
int y = y1 - q * y0;
a = b;
b = r;
x1 = x0;
x0 = x;
y1 = y0;
y0 = y;
}
return new int[]{a, x0, y0};
}
5.3 示例
继续使用 a = 254, b = 44：
迭代过程中逐步更新贝祖系数，最终得到：
$$ 2 = (-9) \cdot 254 + 52 \cdot 44 $$
✅ 与递归版本结果一致
✅ 避免递归调用，性能更优
5.4 性能优化
由于 x 和 y 的更新是独立的，我们可以只计算其中一个，然后通过公式推导出另一个：
$$ y = \frac{d - x \cdot a}{b} $$
这样可以减少三分之一的计算量。
6. 贝祖系数的唯一性
贝祖系数并不是唯一的。如果 (x, y) 是一对贝祖系数，那么所有满足如下形式的 (x', y') 也是：
$$ x' = x + k \cdot \frac{b}{d}, \quad y' = y - k \cdot \frac{a}{d}, \quad k \in \mathbb{Z} $$
其中 d = \gcd(a, b)。
✅ 只有两组系数满足：
$$ |x| \leq \left| \frac{b}{d} \right|, \quad |y| \leq \left| \frac{a}{d} \right| $$
而扩展欧几里得算法总能找到其中一组。
7. 总结
扩展欧几里得算法不仅能计算最大公约数，还能求出对应的贝祖系数，是现代密码学和数论中的重要工具。我们介绍了其两种实现方式：
| 实现方式 | 优点 | 缺点 |
|---|---|---|
| 递归版本 | 实现简单，逻辑清晰 | 依赖递归调用，可能栈溢出 |
| 迭代版本 | 性能更优，无栈溢出风险 | 代码稍复杂 |
✅ 推荐使用迭代版本，性能更稳定
✅ 优化时可只计算一个系数，另一个通过公式推导获得
扩展欧几里得算法是理解模逆、RSA加密等算法的基础，建议熟练掌握其原理和实现。