9.2 模逆、快速幂与中国剩余定理
瞭望塔的几只齿轮按不同周期转动，阿花要判断它们何时重新对齐，以及哪些模运算允许逆向求解。
模运算保留加法和乘法，却不能随意做除法。能否“除以 a”，取决于 a 在当前模数下是否有乘法逆元。
同余可做加减乘
若：
a≡b (mod m)
c≡d (mod m)则：
a+c≡b+d (mod m)
a-c≡b-d (mod m)
ac≡bd (mod m)所以可在计算中不断约减余数，避免中间值无限增长。但固定宽整数里先相乘仍可能溢出，超大模乘需要大整数或专门算法。
约去因子有条件
从：
ac≡bc (mod m)不能总推出 a≡b。
例：
2·1≡2·3 (mod 4)两边都余 2，但 1≢3 (mod 4)。
若 gcd(c,m)=1，c 有逆元，才可以安全约去。
模逆
a 模 m 的逆元 a⁻¹ 满足：
aa⁻¹≡1 (mod m)逆元存在，当且仅当：
gcd(a,m)=1由 Bézout：若 ax+my=1，则：
ax≡1 (mod m)所以 x mod m 是逆元。
例：求 3 模 11 的逆：
4·3-1·11=1因此 3⁻¹≡4 (mod 11)。
线性同余：
ax≡b (mod m)有解当且仅当 gcd(a,m)|b。若 gcd 为 1，则解模 m 唯一；否则可能无解或有多个剩余类解。
模快速幂
计算 a^e mod m 不应先生成巨大 a^e。平方—乘法按指数二进制展开：
result=1
base=a mod m
while e>0:
if e 为奇数:
result=result·base mod m
base=base·base mod m
e=floor(e/2)模乘次数 O(log e)。安全实现还要考虑：
- 指数是否允许负数；
- 模数是否为正；
- 乘法是否溢出；
- 密码学场景是否需要常数时间，避免分支和内存访问泄漏指数位。
教学代码不应直接用于密钥运算。
Fermat 与 Euler 定理
若 p 为质数且 p∤a：
a^(p-1)≡1 (mod p)Euler 定理推广为：若 gcd(a,n)=1：
a^φ(n)≡1 (mod n)φ(n) 是 1 到 n 中与 n 互质的剩余类数量。
若 p 质数：
φ(p)=p-1若 p,q 为不同质数：
φ(pq)=(p-1)(q-1)条件 gcd(a,n)=1 不能省略。Fermat 小定理给出质数的必要性质，却不是充分判据：合数也可能对某些或全部互质底数表现类似。
中国剩余定理
若模数 m₁,...,m_k 两两互质，则同余组：
x≡a₁ (mod m₁)
...
x≡a_k (mod m_k)在模：
M=m₁...m_k意义下有唯一解。
构造：
M_i=M/m_i
y_i=M_i⁻¹ mod m_i
x=Σ a_i M_i y_i mod M因为 M_i y_i 在模 m_i 下为 1，在其他模数下为 0，它像选择对应分量的基向量。
例：
x≡2 (mod 3)
x≡3 (mod 5)
x≡2 (mod 7)解为：
x≡23 (mod 105)非互质模数
两个同余：
x≡a (mod m)
x≡b (mod n)有共同解，当且仅当：
a≡b (mod gcd(m,n))若有解，解在模 lcm(m,n) 意义下唯一。标准“两两互质”版本只是更简洁的特例。
工程应用与边界
- 多周期调度的相位对齐；
- 把大整数运算拆到多个互质模数再重建；
- RSA 私钥运算中的 CRT 加速；
- 剩余数系统与纠错编码。
CRT 分解不自动提供安全性。密码实现还需防故障注入、侧信道和错误校验，应使用审计过的库。
完成检查
- 求
17⁻¹ mod 43； - 解
14x≡8 (mod 30)； - 手工计算
7^181 mod 13； - 用 CRT 解三个两两互质同余；
- 构造一个非互质且无解的同余组；
- 说明模快速幂为何仍可能在固定宽整数乘法处溢出。