扩展欧几里得定理详解：从贝祖等式到密码学基石

⚡ 什么是扩展欧几里得定理？

在初等数论中，欧几里得算法（Euclidean Algorithm）是一种用于计算两个整数 a 和 b 的最大公约数（Greatest Common Divisor, GCD）的高效方法。然而，仅仅知道最大公约数往往是不够的。在许多数学问题和计算机算法应用中，我们不仅需要知道 gcd(a, b) 是多少，还需要找到满足特定线性组合关系的整数系数。

扩展欧几里得定理（Extended Euclidean Algorithm, 简称 ExGCD）正是解决这一问题的利器。该定理指出：对于不完全为 0 的非负整数 a，b，gcd(a, b) 必然存在整数 x 和 y，使得：

这个等式被称为贝祖等式（Bézout's identity）。扩展欧几里得算法的核心任务，就是在求出 gcd(a, b) 的同时，计算出满足该等式的一组整数解 x 和 y。这不仅是数论的基础，更是解决线性同余方程和计算模逆元的关键工具。

⚙️ 数学原理与推导逻辑

理解扩展欧几里得算法的关键在于递归的思想。我们假设已经找到了 gcd(b, a mod b) 对应的解 x' 和 y'，即：

bx' + (a mod b)y' = gcd(b, a mod b)

根据欧几里得算法的原理，gcd(a, b) = gcd(b, a mod b)。同时，我们知道 a mod b = a - ⌊a/b⌋ b。将这些代入上式：

bx' + (a - ⌊a/b⌋ b)y' = gcd(a, b)

整理各项，将含 a 和 b 的项分别归类：

ay' + b(x' - ⌊a/b⌋y') = gcd(a, b)

对比贝祖等式 ax + by = gcd(a, b)，我们可以得出递归关系的解：

• x = y'
• y = x' - ⌊a/b⌋ y'

递归的终止条件是当 b = 0 时。此时 gcd(a, 0) = a，显然有 a1 + 00 = a，所以此时 x = 1，y = 0。通过从底层向上回溯，即可求得原始方程的解。

💻 代码实现与示例

以下是使用 C++ 和 Python 实现的扩展欧几里得算法。代码严格遵循上述数学推导，并处理了边界情况。

#include <iostream>
// 返回 gcd(a, b)，并通过引用返回 x 和 y
long long exgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = exgcd(b, a % b, y, x);
    y -= a / b  x;
    return d;
}
int main() {
    long long a = 35, b = 15;
    long long x, y;
    long long g = exgcd(a, b, x, y);
    std::cout << "gcd(" << a << ", " << b << ") = " << g << std::endl;
    std::cout << x << "  " << a << " + " << y << "  " << b << " = " << g << std::endl;
    return 0;
}

def exgcd(a, b):
    if b == 0:
        return a, 1, 0
    else:
        d, x1, y1 = exgcd(b, a % b)
        x = y1
        y = x1 - (a // b)  y1
        return d, x, y
a = 35
b = 15
g, x, y = exgcd(a, b)
print(f"gcd({a}, {b}) = {g}")
print(f"{x}  {a} + {y}  {b} = {g}")

import java.util.;
public class ExGCD {
    // 使用数组封装返回值：[gcd, x, y]
    public static long[] exgcd(long a, long b) {
        if (b == 0) {
            return new long[]{a, 1, 0};
        }
        long[] res = exgcd(b, a % b);
        long d = res[0];
        long x1 = res[1];
        long y1 = res[2];
        long x = y1;
        long y = x1 - (a / b)  y1;
        return new long[]{d, x, y};
    }
    public static void main(String[] args) {
        long[] res = exgcd(35, 15);
        System.out.println("gcd = " + res[0]);
        System.out.println("x = " + res[1] + ", y = " + res[2]);
    }
}

执行示例解析

验证：35 (1) + 15 (-2) = 35 - 30 = 5。结果正确。

🔐 核心应用场景：从理论到实践

扩展欧几里得算法不仅仅是数论中的一个数学定理，它是现代密码学和计算机科学中许多关键算法的基石。以下是其最主要的应用领域。

🌐 网友们还关心：扩展欧几里得在现实中的其他身影

除了上述经典的密码学应用，扩展欧几里得算法还在以下领域发挥着重要作用：

• 故障诊断：在无线通信中，用于解码某些类型的纠错码。
• 积分系统：在某些经济模型中，用于解决资源分配的整数约束问题。
• 图形学：在光栅化算法中，用于计算像素点的分布。

📜 历史与发展脉络

欧几里得算法最早出现在欧几里得的《几何原本》（第7卷，命题I和II）中，大约公元前300年。然而，扩展欧几里得算法的出现要晚得多。

❓ 常见疑问解答 (FAQ)

扩展欧几里得定理不仅是数论中的一个优美结论，更是连接纯数学与计算机科学的桥梁。从简单的最大公约数计算到复杂的 RSA 加密解密，它的身影无处不在。掌握这一算法，对于深入理解现代信息安全体系具有重要意义。