Open Clock

什么是模运算

模运算（Modular Arithmetic）是整数算术的一个分支，其核心思想是：当整数除以一个固定的正整数（称为模数，modulus）时，只关心余数而忽略商。

记法：a mod n = r，表示 a 除以 n 的余数为 r，其中 0 ≤ r < n。

例如：17 mod 5 = 2（因为 17 = 3 × 5 + 2）

同余的定义

如果两个整数 a 和 b 除以 n 的余数相同，即 n 整除 (a - b)，则称 a 和 b 对模 n 同余，记作：

a ≡ b (mod n)

等价条件：a ≡ b (mod n) 当且仅当 n | (a - b)，即 n 整除 a - b。

例如：17 ≡ 2 (mod 5)，因为 5 | (17 - 2) = 15。

同余的基本性质

若 a ≡ b (mod n) 且 c ≡ d (mod n)，则：

• 加法：a + c ≡ b + d (mod n)
• 减法：a - c ≡ b - d (mod n)
• 乘法：a × c ≡ b × d (mod n)
• 幂运算：a^k ≡ b^k (mod n)，对任意正整数 k

注意：除法不一定成立！a × c ≡ b × c (mod n) 不能推出 a ≡ b (mod n)，除非 gcd(c, n) = 1。

剩余类与完全剩余系

对模 n，所有整数按余数分成 n 个剩余类：[0], [1], [2], ..., [n-1]。

每个剩余类中的任意一个元素称为该类的代表元。

从每个剩余类中取一个代表元组成的集合称为完全剩余系。最常用的是最小非负完全剩余系 {0, 1, 2, ..., n-1}。

模逆元

如果 gcd(a, n) = 1，则存在整数 x 使得 a × x ≡ 1 (mod n)，x 称为 a 在模 n 下的模逆元，记作 a^-1 mod n。

求模逆元的方法：扩展欧几里得算法。例如求 3 的模 7 逆元：3 × 5 = 15 ≡ 1 (mod 7)，所以 3^-1 ≡ 5 (mod 7)。

中国剩余定理（CRT）

设 m₁, m₂, ..., m_k 两两互素，则同余方程组：

x ≡ a₁ (mod m₁)
x ≡ a₂ (mod m₂)
...
x ≡ a_k (mod m_k)

在模 M = m₁m₂...m_k 下有唯一解。

密码学应用：RSA 解密中利用 CRT 将一个模 N 的运算分解为两个模 p 和模 q 的运算，加速约 4 倍。

密码学中的重要性

模运算是现代密码学的数学基础：

• RSA：基于大整数分解难题，核心运算为模幂运算 c = m^e mod n
• Diffie-Hellman：基于离散对数问题，运算为 g^a mod p
• 椭圆曲线密码：点加法运算在有限域上进行模运算
• AES：字节运算在 GF(2⁸) 有限域中进行

快速模幂算法

计算 a^b mod n 时，朴素方法（先算幂再取模）对大数不现实。快速模幂（平方-乘算法）将复杂度从 O(b) 降到 O(log b)。

算法思路：将指数 b 表示为二进制，逐位处理：

result = 1
while b > 0:
    if b is odd: result = (result * a) mod n
    a = (a * a) mod n
    b = b // 2

例如：计算 3¹³ mod 7。13 = 1101(二进制)，只需 3 次平方和 3 次乘法。