密码学数学基础 - 整数关系 | Alice and Bobの神秘小屋

在我们踏上密码学数学基础的冒险之旅后，第一站就是整数关系的世界。这个领域虽然看似简单，但却是构建整个密码学大厦的基石。无论是最基本的整除关系，还是更复杂的同余关系，它们都在为我们揭示数字之间的神秘联系。

本章将带你深入了解整数关系的核心概念，包括整除、素数、最大公约数和最小公倍数等。我们将通过生动的例子和直观的解释，帮助你掌握这些基本工具，为后续的密码学学习打下坚实的基础。

别看我说的很高大上，放轻松，这一章真的非常简单口牙。😁

整除关系与素数 😋

在整数的世界里，整除关系是最基本的关系之一。我们说一个整数 $ a $ 整除另一个整数 $ b $，记作 $ a \mid b $，如果存在一个整数 $ k $ 使得 $ b = ak $。换句话说，$ b $ 可以被 $ a $ 整除，没有余数。例如，$ 3 \mid 12 $ 因为 $ 12 = 3 \times 4 $，但 $ 5 \nmid 12 $ 因为 $ 12 $ 不能被 $ 5 $ 整除。

素数是大于 1 的整数，除了 1 和它本身之外没有其他正整数因数。素数在密码学中扮演着重要的角色，因为许多加密算法都依赖于大素数的性质。例如，RSA 加密算法就是基于两个大素数的乘积来实现安全性的。

最大公约数与最小公倍数 😛

最大公约数（GCD）是指两个或多个整数的公共约数中最大的一个。比如，$ \text{gcd}(12, 15) = 3 $，因为 3 是 12 和 15 的最大公共约数。

最小公倍数（LCM）则是指两个或多个整数的公共倍数中最小的一个。例如，$ \text{lcm}(4, 6) = 12 $，因为 12 是 4 和 6 的最小公共倍数。

如何求解最大公约数与最小公倍数 🤨

计算最大公约数的一种高效方法是辗转相除法（Euclidean Algorithm）。
这个算法基于一个重要的性质①：对于两个整数 $ a $ 和 $ b $，如果 $ a > b $，那么

$\text{gcd}(a, b) = \text{gcd}(b, a \mod b)$

通过不断地将较大的数替换为较小的数和它们的余数，我们可以快速找到最大公约数。

再根据最大公约数和最小公倍数的性质②：

$\text{lcm}(a, b) = \frac{|a \times b|}{\text{gcd}(a, b)}$

求出最小公倍数。

裴蜀定理与扩展欧几里得算法 🥰

裴蜀定理（Bézout’s Identity）是整数关系中的一个重要定理，它告诉我们对于任意两个整数 $ a $ 和 $ b $，存在整数 $ x $ 和 $ y $，使得性质③：

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

扩展欧几里得算法（Extended Euclidean Algorithm）就是基于裴蜀定理的一种算法，它不仅可以计算最大公约数，还可以找到满足裴蜀定理的整数 $ x $ 和 $ y $。

结论①②③证明 🤓👆

由于本章节的定理和算法都比较基础，我们来简单证明一下吧。

结论①证明 😑

带余除法分解

假设 $ a = bq + r $，其中 $ q $ 是商，$ r $ 是余数，且 $ 0 \leq r < b $。我们记$ r $为 $ a \mod b $。

证明$gcd(a,b)$是$b$和$r$的公约数

设 $ d = \text{gcd}(a, b) $，则 $ d \mid a $ 和 $ d \mid b $。
因为 $ d $ 整除 $ a $ 和 $ bq $，$ d $ 也必须整除 $ r = a - bq $，即 $ d \mid r $。
所以，$ d $ 是 $ b $ 和 $ r $ 的公因数，那么一定小于等于最大公因数$ \text{gcd}(b, r) $，故 $ \text{gcd}(a, b) \leq \text{gcd}(b, r) $。

证明$gcd(b,r)$是$a$和$b$的公约数

设 $ d’ = \text{gcd}(b, r) $，则 $ d’ \mid b $ 和 $ d’ \mid r $。
因为 $ d’ $ 整除 $ b $ 和 $ r $，$ d’ $ 也必须整除 $ a = bq + r $，即 $ d’ \mid a $。
所以，$ d’ $ 是 $ a $ 和 $ b $ 的公因数，那么一定小于等于最大公因数$ \text{gcd}(a, b) $，故 $ \text{gcd}(b, r) \leq \text{gcd}(a, b) $。