贝祖等式

贝祖等式在最大公约数与模逆元中的基础作用说明

#status / growing #type / concept

[!info] related notes

相关概念: 辗转相除法, 模逆元, 非对称密码学（Asymmetric-Encryption）

贝祖等式 (Bézout’s Identity)

贝祖等式（也称贝祖定理、Bézout’s Lemma）是数论中的一个重要定理。

它描述了两个整数的最大公约数（GCD）与这两个整数的线性组合之间的关系。

定理内容：对于任意两个整数 $a$ and $b$（不全为 0），存在整数 $x$ 和 $y$，使得：

$$ ax + by = \gcd(a, b) $$

注意：这里的 $x$ 和 $y$ 被称为 贝祖系数，它们不一定是正数，通常是一正一负。

贝祖等式还有一个更深刻的推论： $ax + by$ 的形式所能构成的最小正整数，正是 $\gcd(a, b)$。

换句话说，任何 $ax + by$ 的结果，一定都是 $\gcd(a, b)$ 的倍数。你无法通过整数线性组合凑出一个比 GCD 更小的正整数。

如果 $a$ 和 $b$ 互素（即 $\gcd(a, b) = 1$），那么贝祖等式变为：

$$ ax + by = 1 $$

这意味着存在整数 $x, y$ 使得 $ax + by = 1$。这直接导出了模逆元的存在性：

$$ ax \equiv 1 \pmod b $$

(这里 $x$ 就是 $a$ 关于模 $b$ 的逆元)

在 RSA 密钥生成中，我们选取的公钥指数 $e$ 和欧拉函数 $\phi(n)$ 必须是互素的。

正是因为满足 $\gcd(e, \phi(n)) = 1$，根据贝祖定理，我们确信一定存在整数 $d$ 和 $k$，使得：

$$ e \times d + \phi(n) \times k = 1 $$

如果不满足互素条件（即 GCD > 1），那么等式右边就无法等于 1，也就无法找到满足 $e \times d \equiv 1 \pmod{\phi(n)}$ 的私钥 $d$。

结论：贝祖定理从理论上保证了 RSA 私钥 $d$ 的存在性。

虽然贝祖定理告诉我们 $x, y$ 存在，但它没告诉我们怎么找。寻找 $x, y$ 的方法就是 euclidean-algorithm 的扩展版本——扩展欧几里得算法。

求 $12x + 42y = \gcd(12, 42)$ 的解。

求 GCD：
- $42 = 3 \times 12 + 6$
- $12 = 2 \times 6 + 0$
- $\gcd = 6$。
逆向回代（找 x, y）：
- 从第一步得知：$6 = 42 - 3 \times 12$
- 这其实已经写成了 $ax + by$ 的形式：
- $1 \times 42 + (-3) \times 12 = 6$
结果：
- $x = -3$
- $y = 1$
- 验证：$12(-3) + 42(1) = -36 + 42 = 6$。对的。

贝祖等式的解 $(x, y)$ 并不是唯一的。如果我们找到了一组特解 $(x_0, y_0)$，那么所有的解可以表示为：

$$ x = x_0 + k \frac{b}{\gcd(a, b)} $$

$$ y = y_0 - k \frac{a}{\gcd(a, b)} $$

其中 $k$ 是任意整数。

在 RSA 中，我们通常只需要一个正整数解作为私钥，如果算出来是负数，就加上模数 $\phi(n)$（相当于取不同的 $k$ 值）来变成正数。

相关链接：