模运算详解

每个人其实都在做模运算:8 点过 10 个小时是 6 点,星期日的下一天是星期一。事实证明,这种过了 n 步就从 0 重新开始的计数有一套完整的算术,有自己的规则和惊喜,并在数论和保护互联网的密码学中占据核心地位。

一个有十二个位置、标着 0 到 11 的钟面,以及一条从 9 到 2 绕表盘一圈的螺旋路径
一个有十二个位置、标着 0 到 11 的钟面,以及一条从 9 到 2 绕表盘一圈的螺旋路径

余数与同余

用 a 除以 n,只保留余数:这就是 a mod n,一个 0 到 n − 1 之间的数。26 mod 7 = 5,因为 26 = 3 × 7 + 5。余数相同的数在模 n 下表现相同,所以我们称它们同余:26 ≡ 5 ≡ −2 (mod 7)。卡尔·弗里德里希·高斯在 1801 年的 Disquisitiones Arithmeticae(《算术研究》)中引入了这一记号,它让费马和欧拉早年的观察成为一门独立的算术。在有 n 个位置的钟面上,每个整数都落在它的余数上;转过的整圈都被忽略。

卡尔·弗里德里希·高斯,克里斯蒂安·阿尔布雷希特·延森1840年肖像。他在1801年的《算术研究》中引入了同余记号 a ≡ b (mod n)。
卡尔·弗里德里希·高斯,克里斯蒂安·阿尔布雷希特·延森1840年肖像。他在1801年的《算术研究》中引入了同余记号 a ≡ b (mod n)。

加法、减法和乘法

这三种普通运算照常进行,而且你可以随时取模 n:和的余数等于余数之和的余数,差和积也是如此。要求 37 × 48 的末位数字,只需把末位相乘:7 × 8 = 56,所以末位是 6。正是这一点让模运算对计算机如此有用:无论数有多大,中间值都不会超过 n²。

除法需要逆元

除法是例外。2 × 3 ≡ 2 × 8 (mod 10),因为两者模 10 都是 6,但 3 和 8 并不相同,所以不能直接把 2 约掉。除以 a 就是乘以它的逆元,即满足 a × x ≡ 1 的数 x,而逆元恰好在 a 与 n 没有公因数时存在。扩展欧几里得算法可以求出它:它执行欧几里得求最大公约数的除法步骤,并在每一步记录一个乘数,这样当余数变为 1 时,这个乘数就是逆元。当 n 为素数时,除 0 以外的每个数都有逆元,除法总是可行的。

幂、费马与欧拉

幂会循环。取 3 模 7 的各次幂:3, 2, 6, 4, 5, 1,然后又是 3。这个循环的长度就是 3 的阶。1640 年,皮埃尔·德·费马注意到,对素数 p,只要 p 不整除 a,就有 a^(p − 1) ≡ 1 (mod p),因此每个阶都整除 p − 1。莱昂哈德·欧拉证明了这一点,并把它推广到任意 n,用与 n 互素的值的个数代替 p − 1。巨大的幂用反复平方法计算:a, a², a⁴, a⁸ …,每一项都是前一项的平方并取模 n,然后按指数的二进制位相乘。

皮埃尔·德·费马的肖像
皮埃尔·德·费马的肖像
莱昂哈德·欧拉肖像
莱昂哈德·欧拉肖像

校验码与日历

模运算能发现错误。ISBN-10 的最后一位是这样选取的:使全部十位数字的加权和是 11 的倍数,因此任何一位数字出错、任何两个相邻数字对调,都能被发现。银行卡号使用模 10 的 Luhn 校验,IBAN 使用模 97 的校验。日历按模 7 运行:任何日期是星期几都可以通过几个余数算出来,万年历和末日法则(doomsday rule)就是这样运作的。

密码学

现代密码学建立在易于计算、难以逆转的模幂之上。在 1976 年的迪菲–赫尔曼密钥交换中,两个人通过交换模一个大素数的幂,在公开线路上商定一个共享秘密。RSA 由李维斯特、萨莫尔和阿德曼于 1977 年发表,它把消息 m 加密为 m^e mod n,其中 n 是两个大素数的乘积,并用第二个指数 d 解密,而只有知道这两个素数的人才能算出 d。在教科书的例子中,n = 3233 = 61 × 53,e = 17,d = 413:65 变成 2790,2790 又变回 65。

动手探索

打开模运算时钟,即可对最多 30 位的数计算 a mod n,以及模 n 的和、差、积、幂、逆元和商。每个答案都附有步骤:带余除法、反复平方法得到的各次幂,或扩展欧几里得算法的表格。钟面会画出答案是如何得到的,从加法的螺旋到幂的循环;当 n 较小时,运算表会一次显示所有答案。

常见问题

符号 ≡ 是什么意思?

a ≡ b (mod n) 表示 a 和 b 除以 n 的余数相同,或者等价地说,n 整除 a − b。38 ≡ 2 (mod 12),因为 38 − 2 = 36 是 12 的倍数。

mod 和编程中的 % 运算符一样吗?

对正数来说是一样的。对负数,许多语言(如 C、Java 和 JavaScript)会返回负余数:在这些语言中 −7 % 3 是 −1,而 −7 mod 3 = 2。当 n 为正数时,Python 的 % 遵循数学约定。

一个数模 n 的阶是什么?

使 a^k ≡ 1 (mod n) 成立的最小 k > 0。只有当 a 与 n 没有公因数时它才存在。2 模 7 的阶是 3,因为 2³ = 8 ≡ 1;而 3 模 7 的阶是 6,所以 3 的各次幂会取遍每一个非零余数:3 是模 7 的原根。

模运算是谁发明的?

余数早就有人使用,例如 3 至 5 世纪的中国剩余定理,以及费马和欧拉的工作。1801 年,高斯借助同余记号,把它发展成一门系统的算术。

准备好尝试了吗?

在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

打开模运算时钟