密码学数学基础 - 整数关系
在我们踏上密码学数学基础的冒险之旅后，第一站就是整数关系的世界。这个领域虽然看似简单，但却是构建整个密码学大厦的基石。无论是最基本的整除关系，还是更复杂的同余关系，它们都在为我们揭示数字之间的神秘联系。
本章将带你深入了解整数关系的核心概念，包括整除、素数、最大公约数和最小公倍数等。我们将通过生动的例子和直观的解释，帮助你掌握这些基本工具，为后续的密码学学习打下坚实的基础。
别看我说的很高大上，放轻松，这一章真的非常简单口牙。😁
整除关系与素数 😋
在整数的世界里，整除关系是最基本的关系之一。我们说一个整数a aa整除另一个整数b bb，记作a ∣ b a \mid ba∣b，如果存在一个整数k kk使得b = a k b=akb=ak。换句话说，b bb可以被a aa整除，没有余数。例如，3 ∣ 12 3 \mid 123∣12因为12 = 3 × 4 12=3 \times 412=3×4，但5 ∤ 12 5 \nmid 125∤12因为12 1212不能被5 55整除。
素数是大于1的整数，除了1和它本身之外没有其他正整数因数。素数在密码学中扮演着重要的角色，因为许多加密算法都依赖于大素数的性质。例如，RSA加密算法就是基于两个大素数的乘积来实现安全性的。
最大公约数与最小公倍数 😛
最大公约数（GCD）是指两个或多个整数的公共约数中最大的一个。比如，gcd ( 12 , 15 ) = 3 \text{gcd}(12,15)=3gcd(12,15)=3，因为3是12和15的最大公共约数。
最小公倍数（LCM）则是指两个或多个整数的公共倍数中最小的一个。例如，lcm ( 4 , 6 ) = 12 \text{lcm}(4,6)=12lcm(4,6)=12，因为12是4和6的最小公共倍数。
如何求解最大公约数与最小公倍数 🤨
计算最大公约数的一种高效方法是辗转相除法（EuclideanAlgorithm）。
这个算法基于一个重要的性质①：对于两个整数a aa和b bb，如果a > b a>ba>b，那么
gcd ( a , b ) = gcd ( b , a m o d b ) \text{gcd}(a,b)=\text{gcd}(b,a \mod b)gcd(a,b)=gcd(b,amodb)
通过不断地将较大的数替换为较小的数和它们的余数，我们可以快速找到最大公约数。
再根据最大公约数和最小公倍数的性质②：
lcm ( a , b ) = ∣ a × b ∣ gcd ( a , b ) \text{lcm}(a,b)=\frac{|a\times b|}{\text{gcd}(a,b)}lcm(a,b)=gcd(a,b)∣a×b∣
求出最小公倍数。
裴蜀定理与扩展欧几里得算法 🥰
裴蜀定理（Bézout’sIdentity）是整数关系中的一个重要定理，它告诉我们对于任意两个整数a aa和b bb，存在整数x xx和y yy，使得性质③：
a x + b y = gcd ( a , b ) ax+by=\text{gcd}(a,b)ax+by=gcd(a,b)
扩展欧几里得算法（ExtendedEuclideanAlgorithm）就是基于裴蜀定理的一种算法，它不仅可以计算最大公约数，还可以找到满足裴蜀定理的整数x xx和y yy。
结论①②③证明 🤓👆
由于本章节的定理和算法都比较基础，我们来简单证明一下吧。
结论①证明 😑
带余除法分解
假设a = b q + r a=bq+ra=bq+r，其中q qq是商，r rr是余数，且0 ≤ r < b 0 \leq r<b0≤r<b。我们记r rr为a m o d b a\mod bamodb。
证明g c d ( a , b ) gcd(a,b)gcd(a,b)是b bb和r rr的公约数
设d = gcd ( a , b ) d=\text{gcd}(a,b)d=gcd(a,b)，则d ∣ a d\mid ad∣a和d ∣ b d \mid bd∣b。
因为d dd整除a aa和b q bqbq，d dd也必须整除r = a − b q r=a-bqr=a−bq，即d ∣ r d\mid rd∣r。
所以，d dd是b bb和r rr的公因数，那么一定小于等于最大公因数gcd ( b , r ) \text{gcd}(b,r)gcd(b,r)，故gcd ( a , b ) ≤ gcd ( b , r ) \text{gcd}(a,b) \leq \text{gcd}(b,r)gcd(a,b)≤gcd(b,r)。
证明g c d ( b , r ) gcd(b,r)gcd(b,r)是a aa和b bb的公约数
设d ′ = gcd ( b , r ) d'=\text{gcd}(b,r)d′=gcd(b,r)，则d ′ ∣ b d'\mid bd′∣b和d ′ ∣ r d'\mid rd′∣r。
因为d ′ d'd′整除b bb和r rr，d ′ d'd′也必须整除a = b q + r a=bq+ra=bq+r，即d ′ ∣ a d'\mid ad′∣a。
所以，d ′ d'd′是a aa和b bb的公因数，那么一定小于等于最大公因数gcd ( a , b ) \text{gcd}(a,b)gcd(a,b)，故gcd ( b , r ) ≤ gcd ( a , b ) \text{gcd}(b,r) \leq \text{gcd}(a,b)gcd(b,r)≤gcd(a,b)。
总结
综上所述，gcd ( a , b ) = gcd ( b , r ) \text{gcd}(a,b)=\text{gcd}(b,r)gcd(a,b)=gcd(b,r)，证明完毕。
结论②证明 😪
设d = gcd ( a , b ) d=\text{gcd}(a,b)d=gcd(a,b)，则a = d a ′ a=da'a=da′和b = d b ′ b=db'b=db′，其中a ′ a'a′和b ′ b'b′是互质的整数。
因此，lcm ( a , b ) = d × a ′ × b ′ = ∣ d a ′ × d b ′ ∣ d = ∣ a × b ∣ gcd ( a , b ) \text{lcm}(a,b)=d\times a' \times b'=\frac{|da' \times d b'|}{d}=\frac{|a\times b|}{\text{gcd}(a,b)}lcm(a,b)=d×a′×b′=d∣da′×db′∣=gcd(a,b)∣a×b∣，证明完毕。
结论③证明 😨
欧几里得算法（辗转相除法）
设d = gcd ( a , b ) d=\text{gcd}(a,b)d=gcd(a,b)。
用辗转相除法：
a = b q 1 + r 1 ， 0 < r 1 < b b = r 1 q 2 + r 2 ， 0 < r 2 < r 1 \begin{align*} a=bq_1+r_1，0<r_1<b\\ b=r_1q_2+r_2，0<r_2<r_1 \end{align*}a=bq1+r1，0<r1<bb=r1q2+r2，0<r2<r1
不断进行下去，直到余数为0：
r n − 2 = r n − 1 q n + r n ， 0 < r n < r n − 1 r n − 1 = r n q n + 1 + 0 ， r n = d \begin{align*} r_{n-2}=r_{n-1}q_n+r_n，0<r_n<r_{n-1}\\ r_{n-1}=r_nq_{n+1}+0，r_n=d \end{align*}rn−2=rn−1qn+rn，0<rn<rn−1rn−1=rnqn+1+0，rn=d
最后余数为0，说明r n = d = gcd ( a , b ) r_n=d=\text{gcd}(a,b)rn=d=gcd(a,b)。
反向替换求解x xx和y yy
倒数第二步：
d = r n = r n − 2 − r n − 1 q n d=r_n=r_{n-2}-r_{n-1}q_nd=rn=rn−2−rn−1qn
再把r n − 1 r_{n-1}rn−1用上一行表示：
r n − 1 = r n − 3 − r n − 2 q n − 1 r_{n-1}=r_{n-3}-r_{n-2}q_{n-1}rn−1=rn−3−rn−2qn−1
往回带入：
d = A ⋅ r n − 2 + B ⋅ r n − 3 , A , B ∈ Z d=A\cdot r_{n-2}+B\cdot r_{n-3},A,B\in\mathbb{Z}d=A⋅rn−2+B⋅rn−3,A,B∈Z
一直往上带入，最终可以表示为：
d = x ⋅ a + y ⋅ b d=x\cdot a+y\cdot bd=x⋅a+y⋅b
其中x , y ∈ Z x,y\in\mathbb{Z}x,y∈Z
我的个人blog：Alice and Bobの神秘小屋