9.2 模逆、快速幂与中国剩余定理

模运算保留加法和乘法，却不能随意做除法。能否“除以 a”，取决于 a 在当前模数下是否有乘法逆元。

本课中的变量均为整数，模数为正；讨论乘法逆元时取 m≥2，模快速幂和同余合并代码也明确处理 m=1。

同余可做加减乘

若：

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)

设 d=gcd(a,m)。有解恰好当 d|b；此时模 m 有恰好 d 个不同解。将方程与模数同除以 d，新系数与新模数互质，再用逆元求解。例如 14x≡8 (mod 30) 化成 7x≡4 (mod 15)，所以 x≡7 (mod 15)，在模 30 下对应 7 和 22。

模快速幂

计算 a^e mod m 不应先生成巨大 a^e。平方乘法按指数二进制展开，下面是 Python 3 实现：

def pow_mod(a, e, m):
    if e < 0 or m <= 0:
        raise ValueError("require an integer exponent e >= 0 and modulus m > 0")
    result, base = 1 % m, a % m
    while e:
        if e & 1:
            result = result * base % m
        base = base * base % m
        e //= 2
    return result

print(pow_mod(7, 181, 13))  # 7
print(pow_mod(9, 0, 1))    # 0

循环保持 result × base^e ≡ a^原指数 (mod m)。模乘次数为 O(log(e+1))，单次大整数乘除的成本另计。初始值用 1 % m，使零指数和模数 1 也得到标准余数。实现还要考虑：

• 指数是否允许负数；
• 模数是否为正；
• 乘法是否溢出；
• 密码学场景是否需要常数时间，避免分支和内存访问泄漏指数位。

教学代码不应直接用于密钥运算。

Python 3.8 起，内置 pow(a, -1, m) 支持互质整数的模逆，例如 pow(17, -1, 43) 为 38。它不代表负指数总有定义，也不使上面的教学循环变成常数时间实现。

Fermat 与 Euler 定理

若 p 为质数且 p∤a：

a^(p-1)≡1 (mod p)

Euler 定理推广为：若 n≥1 且 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 小定理给出质数的必要性质，却不是充分判据：合数也可能对某些或全部互质底数表现类似。

中国剩余定理

取 k≥1 个大于 1 的模数 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) 意义下唯一。标准“两两互质”版本只是更简洁的特例。

把 x=a+mk 代入第二式，得到 mk≡b-a (mod n)。先除以 g=gcd(m,n)，再求 m/g 在模 n/g 下的逆元。下面的 Python 3.8+ 实现返回“最小非负余数、合并模数”，不相容则返回 None：

from math import gcd

def merge_crt(a, m, b, n):
    if m <= 0 or n <= 0:
        raise ValueError("moduli must be positive integers")
    g = gcd(m, n)
    if (b - a) % g:
        return None
    reduced = n // g
    k = 0 if reduced == 1 else ((b - a) // g * pow(m // g, -1, reduced)) % reduced
    modulus = m * reduced
    return (a + m * k) % modulus, modulus

x, modulus = merge_crt(2, 3, 3, 5)
print(merge_crt(x, modulus, 2, 7))  # (23, 105)
print(merge_crt(2, 4, 6, 8))       # (6, 8)
print(merge_crt(1, 4, 2, 6))       # None

当 n/g=1 时第二个条件已经被第一个包含，代码无需在这个退化模数下求逆。这里只合并整数约束，没有调度器或密码设备参与。

工程应用与边界

• 多周期调度的相位对齐；
• 把大整数运算拆到多个互质模数再重建；
• RSA 私钥运算中的 CRT 加速；
• 剩余数系统与纠错编码。

CRT 分解不自动提供安全性。密码实现还需防范故障注入、侧信道，并校验计算结果，应使用审计过的库。

完成检查

1. 求 17⁻¹ mod 43；
2. 解 14x≡8 (mod 30)；
3. 手工计算 7^181 mod 13；
4. 用 CRT 解三个两两互质同余；
5. 构造一个非互质且无解的同余组；
6. 说明模快速幂为何仍可能在固定宽整数乘法处溢出。

参考资料

• MIT Mathematics for Computer Science

• Python: pow