模运算
17 ≡ 5 (mod 12)
17 和 5 除以 12 时拥有相同的余数。
模运算就是在一个圆上做算术。如果两个数相差 n 的倍数，那么它们模 n 同余。钟表就是模 12 运算：5 点钟再过 10 小时是 3 点，而不是 15 点。这个简单想法是现代密码学、哈希函数、纠错码以及数论大量内容的基础。
模 12 的时钟：加法会绕圈返回
检验费马小定理
a^(p−1) ≡ 1 (mod p) when p is prime, p∤a
例如 p=5，a=2：2⁴ = 16 = 3×5 + 1 ≡ 1 (mod 5) ✓
例如 p=7，a=3：3⁶ = 729 = 104×7 + 1 ≡ 1 (mod 7) ✓
RSA 加密中正是用它来证明解密会恢复原始消息。
ℤ/5ℤ，也就是模 5 整数的加法表
每一行和每一列都恰好包含一次 {0,1,2,3,4}。这五个元素在模 5 加法下构成一个封闭群。红色标记的是超过 4 后回绕的和。
| + | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 |
| 1 | 1 | 2 | 3 | 4 | 0 |
| 2 | 2 | 3 | 4 | 0 | 1 |
| 3 | 3 | 4 | 0 | 1 | 2 |
| 4 | 4 | 0 | 1 | 2 | 3 |
模运算速览
模运算定义了同余：若 n 整除 a-b，则 a 与 b 模 n 同余。高斯在 1801 年系统化了这一领域。它构成了所有现代公钥密码体系的基础。RSA 加密依赖费马小定理：当 p 是素数且 a 不被 p 整除时，有 a^(p-1) ≡ 1 (mod p)。哈希函数利用模运算把巨大输入压缩到固定输出。模 n 的整数构成一个完整的环，而当 n 为素数时，它甚至构成一个有限域。
应用领域
数学
✓
物理学
–
工程学
–
生物学
–
计算机科学
✓
统计学
–
金融
–
艺术
–
建筑学
–
音乐
✓
密码学
✓
天文学
–
化学
–
哲学
–
地理学
–
生态学
–
想测试一下你的知识吗？
问题
a = b (mod n)是什么意思？
点击 · 空格键
1 / 10
准备好了吗？
Pi
Memorize pi, e, and 40+ mathematical constants using the numpad path method
立即开始 - 完全免费无需账户，适用于任何设备。
Topic roundups
