| 余数 r | 商 q | 乘数 t |
|---|
模运算时钟
9 点过五个小时是 2 点,因为 9 + 5 = 14,而 14 比 12 多 2。这就是模运算:在一个过了 n 就从 0 重新开始的钟面上计数。选择一种运算,输入 n、a 和 b,计算器就会给出答案并写出每一步,从除法的余数到反复平方法和扩展欧几里得算法,同时钟面会显示答案是如何得到的。 选择一种运算,然后输入模数 n 以及数 a 和 b;可以使用最多 30 位的整数,负数也可以,n 最大可到 10^18。钟面上有 n 个位置,0 在顶部,指针指向答案。加法和减法画成 b 步的螺旋,每转满一圈就多一环;乘法画成以 a 为步长的跳跃;幂画成弦 a, a², a³ …,它们最终闭合成一个循环;逆元和除法画成落在 1 或 a 上的倍数。步骤用数字展示同样的计算。模数不超过 20 时会显示该运算的表格;点击一个格子即可使用其中的数。“示例”会填入一道经典问题。
它是如何运作的
- 选择一种运算:a mod n、加法、减法、乘法、除法、幂或 a 的逆元。
- 输入模数 n 以及数 a 和 b,或选择一个示例,例如 7^2026 的末位数字或一条简单的 RSA 消息。
- 阅读答案和步骤,跟随钟面上的路径;模数不超过 20 时,点击表格中的格子即可试用其中的数。
a mod n 是什么意思
a mod n 是 a 除以 n 的余数:17 mod 5 = 2,因为 17 = 3 × 5 + 2。余数总在 0 到 n − 1 之间,负数也不例外:−7 mod 3 = 2,因为 −7 = −3 × 3 + 2。在钟面上,这意味着从 0 往回走 7 步。余数相同的两个数是同余的,记作 17 ≡ 2 (mod 5),这一记号由卡尔·弗里德里希·高斯于 1801 年引入。和、差、积可以在任何一步取模 n,这样数就始终保持较小。
模运算用在哪里
时钟和日历按模 12、模 24 和模 7 运作:星期三之后 100 天是星期五,因为 100 mod 7 = 2。校验码用它来发现输入错误,从 ISBN-10 号码(mod 11)到银行卡号(mod 10)和 IBAN(mod 97)都是如此。密码按模 26 移动字母,而仿射密码解密时需要模 26 的逆元。保护着互联网很大一部分的 RSA 把消息 m 加密为 m^e mod n,并用另一个幂解密:取 n = 3233,65^17 mod 3233 = 2790,而 2790^413 mod 3233 = 65。
常见问题
负数的 a mod n 怎么算?
加上或减去 n 的倍数,直到这个数落在 0 到 n − 1 之间。对于 −7 mod 3:−7 + 9 = 2,所以答案是 2。有些编程语言对 −7 % 3 给出的却是 −1,因为它们把商向零取整;在数学中,余数从不为负。
什么是模逆元?
a 模 n 的逆元是满足 a × x ≡ 1 (mod n) 的数 x。7 模 26 的逆元是 15,因为 7 × 15 = 105 = 4 × 26 + 1。只有当 a 与 n 没有公因数时逆元才存在,扩展欧几里得算法可以求出它。模 n 下除以 a,就是乘以 a 的逆元。
像 7^2026 这样的幂怎样模 n 计算?
用反复平方法:把 7 一次又一次地平方,每次都取模 n,得到 7^1、7^2、7^4、7^8 等等,然后把构成 2026 二进制表示的那些项相乘。这只需要 10 次平方和 7 次乘法,而不是 2,025 次乘法,并且中间的数永远不会超过 n²。7^2026 的末位数字是 9。
为什么钟面上显示 0 而不是 12?
在模运算中,余数从 0 到 n − 1,所以在有 12 个位置的钟面上,正午是 0。12 ≡ 0 (mod 12);普通的钟只是在数学写 0 的地方印上了 12。
数可以有多大?
a 和 b 最多可以有 30 位,也可以是负数,模数最大可到 10^18。计算器在你的浏览器中用精确的整数运算,因此即使是 RSA 规模的示例也能得到精确答案,而且不会向任何地方发送任何数据。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
前往编辑器