模运算
mó yùn suàn
模运算是一种整数算术系统,其中数在到达模数后会"绕回",就像钟表上的时刻一样。
Formula
a \bmod n = \text{remainder when } a \text{ is divided by } n
Definition
模运算是钟表算术：当你到达模数（就像钟表上的 $12$）时，就会绕回零，"$17 \bmod 5$"问的是 $17$ 除以 $5$ 时的余数是多少。若 $n$ 能整除 $(a - b)$，则两个整数 $a$ 和 $b$ 是同余的（$a \equiv b \pmod{n}$）；模 $n$ 的整数在这种余数运算下构成一个环 $\mathbb{Z}_n = \{0, 1, \ldots, n-1\}$，若 $n$ 是素数，则 $\mathbb{Z}_n$ 是一个域（伽罗瓦域 $GF(p)$）。中国剩余定理指出，若 $\gcd(m,n) = 1$，则 $\mathbb{Z}_{mn} \cong \mathbb{Z}_m \times \mathbb{Z}_n$，费马小定理指出对素数 $p$ 和不能被 $p$ 整除的 $a$，$a^{p-1} \equiv 1 \pmod{p}$。
Example
$17 \bmod 5 = 2$（因为 $17 = 3 \times 5 + 2$）；在钟表上，$7$ 点之后 $10$ 小时是 $5$ 点（$17 \bmod 12 = 5$）。模 $n$ 下的算术运算也是如此：$7 + 8 \equiv 3 \pmod{12}$，$5 \times 7 \equiv 11 \pmod{12}$；在（素数模的）$\mathbb{Z}_7$ 中，每个非零元素都有乘法逆元。RSA 加密正依赖于此：选取素数 $p, q$，令 $n=pq$，用 $c = m^e \bmod n$ 加密，用 $m = c^d \bmod n$ 解密，其中 $ed \equiv 1 \pmod{(p-1)(q-1)}$，其安全性建立在分解 $n$ 的困难性之上。
Key Insight
模运算随处可见：星期几（模 7）、上午下午的循环（模 12/24），以及条形码和信用卡上的校验码，它把一个无穷集合（整数）转变为一个有限环，使数论结果能应用于密码学和编码理论中的有限结构。$\mathbb{Z}_n^*$（模 $n$ 的单位群）的结构不仅是 RSA 的基础，也是椭圆曲线密码学和 AKS 素性检验的整个理论基础，使模运算成为现代计算机安全的根基。