结果
不取模
整圈数
gcd(a, n)

    进一步了解模运算

    模运算时钟

    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 时会显示该运算的表格;点击一个格子即可使用其中的数。“示例”会填入一道经典问题。

    它是如何运作的

    1. 选择一种运算:a mod n、加法、减法、乘法、除法、幂或 a 的逆元。
    2. 输入模数 n 以及数 a 和 b,或选择一个示例,例如 7^2026 的末位数字或一条简单的 RSA 消息。
    3. 阅读答案和步骤,跟随钟面上的路径;模数不超过 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 — 无需安装,无需信用卡即可启动。

    前往编辑器