3 · 模运算与数论基础

这一节是抽象代数与数论的交汇，也是 RSA、密钥交换、求逆元的直接工具箱。如果说群、环、域讲的是「结构」，这里讲的就是「怎么真算」。

一、同余（Congruence）

$a\equiv b\pmod n$ 表示 a 与 b 除以 n 余数相同（n 整除 a−b）。同余可以像等式一样加减乘（但不能随便除）。时钟就是模 12 的算术。

二、最大公约数与扩展欧几里得

欧几里得算法求 $\gcd(a,b)$：反复用大数模小数，直到余为 0。

**扩展欧几里得（exgcd）**顺便求出整数 $s,t$ 使：

这是求模逆元的核心工具：若 $\gcd(a,n)=1$，则 $as+nt=1$，两边模 n 得 $as\equiv1$，所以 $a^{-1}=s\bmod n$。

三、费马小定理与欧拉定理

费马小定理（p 质，$\gcd(a,p)=1$）：

这给了第二种求逆元的方法（快速幂）。

欧拉定理（推广到合数模）：$a^{\varphi(n)}\equiv1\pmod n$，其中 $\varphi(n)$ 是与 n 互质的数的个数。RSA 的正确性就靠它。

四、快速幂（平方乘）

计算 $a^k\bmod n$ 不能真乘 k 次。把 k 写成二进制，边平方边乘，$O(\log k)$ 步完成。这是所有公钥密码的计算基石。

五、中国剩余定理（CRT）

若模数两两互质，一组同余方程 $x\equiv a_i\pmod{n_i}$ 有唯一解（模 $\prod n_i$）。应用：RSA 解密用 CRT 加速 4 倍；ZK 里大数拆小数并行算。

六、RSA 一眼看透（全是上面的工具）

1. 取两大质 $p,q$，$N=pq$，$\varphi(N)=(p-1)(q-1)$。
2. 选 e，用 exgcd 求 $d=e^{-1}\bmod\varphi(N)$。
3. 加密 $c=m^e\bmod N$，解密 $m=c^d\bmod N$。正确性由欧拉定理保证。安全性靠「大数分解难」。

七、数字例题（步步算）

用扩展欧几里得求 $3^{-1}\bmod7$：解 $3s+7t=1$。试 $s=5,t=-2$：$15-14=1$ ✓。所以 $3^{-1}=5\bmod7$。用费马验证：$3^{7-2}=3^5=243=34\times7+5\equiv5$ ✓，两法一致。

八、Python 代码

def exgcd(a, b):
    if b == 0: return a, 1, 0
    g, x, y = exgcd(b, a % b)
    return g, y, x - (a // b) * y

def inv_exgcd(a, n):
    g, x, _ = exgcd(a, n)
    return x % n if g == 1 else None

print("3^-1 mod 7 (exgcd) =", inv_exgcd(3, 7))     # 5
print("3^-1 mod 7 (费马) =", pow(3, 7-2, 7))       # 5

# 迷你 RSA
p, q = 61, 53
N = p*q; phi = (p-1)*(q-1)
e = 17; d = inv_exgcd(e, phi)
m = 42
c = pow(m, e, N)
print("密文 =", c, " 解密 =", pow(c, d, N))     # 42

九、动手想一想

1. 为什么求逆元要求 $\gcd(a,n)=1$？
2. RSA 里为什么公开 N 不暴露 $\varphi(N)$？
3. 快速幂把 $a^{1000}$ 从 1000 次乘法降到大约几步？

答案：(1) 不互质时 a 在模 n 下是零因子，无逆元。(2) 知道 $\varphi(N)=(p-1)(q-1)$ 等于能分解 N，也就能算出私钥 d。(3) $\log_2 1000\approx10$ 步。

小结：同余、扩展欧几里得、费马/欧拉定理、快速幂这几件工具凑在一起，就能完整讲清 RSA 的加解密与求逆元。这是公钥密码学最日常的计算层。