数论基础（二）模运算¶
章节概述¶
模运算是数论中的核心概念，在现代密码学、计算机科学和算法竞赛中有着广泛的应用。本章将详细介绍模运算的基本概念、性质以及如何求模逆元。
学习目标¶
- 理解模运算和同余的概念
- 掌握模运算的基本性质
- 学会使用快速幂算法进行模幂运算
- 理解模逆元的概念和存在条件
- 掌握求模逆元的方法（扩展欧几里得算法、费马小定理）
- 了解费马小定理及其应用
（一）模运算的基本概念¶
同余的定义¶
对于整数 a、b 和正整数 m，如果 m | (a - b)，则称 a 与 b 模 m 同余，记作：
等价表述： - a 和 b 除以 m 的余数相同 - a - b 是 m 的倍数
模运算的表示¶
在编程中，模运算通常用 % 运算符表示：
注意：数学中的同余关系 ≡ 与编程中的取模运算 % 略有区别 - 同余关系是一种等价关系 - 取模运算返回的是余数（通常在 [0, m-1] 范围内）
模运算的性质¶
1. 等价关系的三个性质¶
自反性：
对称性：
传递性：
2. 运算性质¶
加法性质：
减法性质：
乘法性质：
幂运算性质：
重要提醒： - 除法性质不成立！不能随意进行除法运算 - 这就是为什么我们需要模逆元
（二）模运算的实现¶
模加法¶
def mod_add(a, b, m):
"""
模加法：(a + b) mod m
参数:
a, b: 整数
m: 模数（正整数）
返回:
int: (a + b) mod m
示例:
>>> mod_add(5, 7, 10)
2
>>> mod_add(15, 8, 10)
3
"""
return (a + b) % m
模减法¶
def mod_sub(a, b, m):
"""
模减法：(a - b) mod m
参数:
a, b: 整数
m: 模数（正整数）
返回:
int: (a - b) mod m（结果为正数）
示例:
>>> mod_sub(5, 7, 10)
8
>>> mod_sub(7, 5, 10)
2
"""
return (a - b) % m
模乘法¶
def mod_mul(a, b, m):
"""
模乘法：(a × b) mod m
参数:
a, b: 整数
m: 模数（正整数）
返回:
int: (a × b) mod m
示例:
>>> mod_mul(5, 7, 10)
5
>>> mod_mul(123, 456, 1000)
88
"""
return (a * b) % m
快速幂算法（模幂运算）¶
问题：计算 a^b mod m，其中 b 可能很大
朴素方法：O(b) 时间复杂度，太慢
快速幂方法：O(log b) 时间复杂度
原理： - 利用二进制分解：a^b = a^(b₀×2⁰ + b₁×2¹ + ... + bₖ×2ᵏ) - 利用平方运算：a^(2ⁿ) = (a^(2ⁿ⁻¹))²
def mod_pow(a, b, m):
"""
快速幂算法：计算 a^b mod m
参数:
a: 底数
b: 指数（非负整数）
m: 模数（正整数）
返回:
int: a^b mod m
时间复杂度: O(log b)
示例:
>>> mod_pow(2, 10, 1000)
24
>>> mod_pow(3, 100, 1000000007)
976371285
"""
result = 1
a = a % m # 处理 a >= m 的情况
while b > 0:
# 如果 b 的当前位是 1
if b % 2 == 1:
result = (result * a) % m
# 平方
a = (a * a) % m
# 右移一位
b = b // 2
return result
递归版本：
def mod_pow_recursive(a, b, m):
"""
快速幂算法（递归版本）
参数:
a: 底数
b: 指数（非负整数）
m: 模数（正整数）
返回:
int: a^b mod m
"""
if b == 0:
return 1 % m
if b == 1:
return a % m
# 如果 b 是偶数
if b % 2 == 0:
half = mod_pow_recursive(a, b // 2, m)
return (half * half) % m
# 如果 b 是奇数
else:
return (a * mod_pow_recursive(a, b - 1, m)) % m
应用场景： - RSA 加密算法 - 大数取模运算 - 离散对数问题 - 各种密码学协议
（三）模逆元¶
模逆元的定义¶
对于整数 a 和正整数 m，如果存在整数 x，使得：
则称 x 为 a 模 m 的逆元，记作 a^(-1) (mod m)。存在的条件¶
定理：a 模 m 有逆元的充分必要条件是 gcd(a, m) = 1。
证明： - 必要性：如果 a × x ≡ 1 (mod m)，则 a × x - 1 = k × m，即 a × x - k × m = 1，说明 gcd(a, m) = 1 - 充分性：如果 gcd(a, m) = 1，根据扩展欧几里得算法，存在 x, y 使得 a × x + m × y = 1，即 a × x ≡ 1 (mod m)
互质的定义¶
两个整数 a 和 m 互质，当且仅当 gcd(a, m) = 1。
求模逆元的方法¶
方法一：扩展欧几里得算法¶
原理：利用扩展欧几里得算法求出 x, y 使得 a × x + m × y = gcd(a, m)，如果 gcd(a, m) = 1，则 x 就是逆元。
def mod_inverse(a, m):
"""
使用扩展欧几里得算法求 a 模 m 的逆元
参数:
a: 整数
m: 模数（正整数）
返回:
int: a 模 m 的逆元（在 [0, m-1] 范围内）
如果逆元不存在，返回 None
时间复杂度: O(log min(a, m))
示例:
>>> mod_inverse(3, 7)
5 # 因为 3 × 5 = 15 ≡ 1 (mod 7)
>>> mod_inverse(10, 17)
12 # 因为 10 × 12 = 120 ≡ 1 (mod 17)
>>> mod_inverse(6, 9)
None # 因为 gcd(6, 9) = 3 ≠ 1，逆元不存在
"""
gcd_val, x, y = extended_gcd(a, m)
if gcd_val != 1:
return None # 逆元不存在
# 确保 x 在 [0, m-1] 范围内
return x % m
验证函数：
def verify_inverse(a, inv, m):
"""
验证 inv 是否是 a 模 m 的逆元
参数:
a: 整数
inv: 候选逆元
m: 模数
返回:
bool: 如果是逆元返回 True，否则返回 False
"""
return (a * inv) % m == 1
方法二：费马小定理（仅当 m 为质数时）¶
费马小定理：如果 p 是质数，且 a 不是 p 的倍数，则：
推论：
def mod_inverse_fermat(a, p):
"""
使用费马小定理求模逆元（仅当 p 是质数时有效）
参数:
a: 整数（a 不是 p 的倍数）
p: 质数
返回:
int: a 模 p 的逆元
如果 p 不是质数或 a 是 p 的倍数，返回 None
时间复杂度: O(log p)
示例:
>>> mod_inverse_fermat(3, 7)
5
>>> mod_inverse_fermat(10, 17)
12
"""
# 检查 p 是否为质数
if not is_prime(p):
return None
# 检查 a 是否与 p 互质
if a % p == 0:
return None
# 使用费马小定理
return mod_pow(a, p - 2, p)
方法三：欧拉定理（扩展）¶
欧拉定理：如果 gcd(a, m) = 1，则：
其中 φ(m) 是欧拉函数。
推论：
def mod_inverse_euler(a, m):
"""
使用欧拉定理求模逆元
参数:
a: 整数（与 m 互质）
m: 模数（正整数）
返回:
int: a 模 m 的逆元
如果逆元不存在，返回 None
时间复杂度: O(φ(m) log m)
示例:
>>> mod_inverse_euler(3, 7)
5
"""
# 检查是否互质
if gcd(a, m) != 1:
return None
# 计算 φ(m)
phi = euler_phi(m)
# 使用欧拉定理
return mod_pow(a, phi - 1, m)
方法四：线性递推求逆元（预处理）¶
应用场景：需要求多个数对同一质数的逆元
条件：模数 m 必须是质数
def linear_inverse(n, p):
"""
线性递推求 1 到 n 模 p 的所有逆元（p 必须是质数）
参数:
n: 最大数
p: 质数模数
返回:
list: inv[i] 表示 i 模 p 的逆元
时间复杂度: O(n)
示例:
>>> inv = linear_inverse(10, 17)
>>> print(inv[3])
6
"""
if not is_prime(p):
return None
inv = [0] * (n + 1)
inv[1] = 1
for i in range(2, n + 1):
inv[i] = p - (p // i) * inv[p % i] % p
return inv
公式说明：
证明： - p = k × i + r，其中 k = p/i，r = p mod i - k × i + r ≡ 0 (mod p) - r ≡ -k × i (mod p) - inv[i] × i ≡ 1 (mod p) - inv[r] × r ≡ 1 (mod p) - inv[r] × (-k × i) ≡ 1 (mod p) - inv[i] ≡ -k × inv[r] (mod p)
（四）模除法¶
模除法的定义¶
在模运算中，除法需要转换为乘以逆元：
前提条件：b 与 m 互质（即 b 的逆元存在）
模除法的实现¶
def mod_div(a, b, m):
"""
模除法：计算 (a ÷ b) mod m
参数:
a: 被除数
b: 除数
m: 模数（正整数）
返回:
int: (a ÷ b) mod m
如果 b 模 m 的逆元不存在，返回 None
示例:
>>> mod_div(6, 3, 7)
2
>>> mod_div(10, 3, 7)
5 # 因为 10 ÷ 3 ≡ 10 × 5 ≡ 50 ≡ 1 (mod 7)
"""
inv_b = mod_inverse(b, m)
if inv_b is None:
return None # 逆元不存在
return (a * inv_b) % m
（五）实战应用¶
应用1：计算组合数¶
问题：计算 C(n, k) mod p，其中 p 是质数
def factorial_mod(n, p):
"""
计算 n! mod p
参数:
n: 正整数
p: 质数模数
返回:
int: n! mod p
"""
result = 1
for i in range(2, n + 1):
result = (result * i) % p
return result
def combination_mod(n, k, p):
"""
计算组合数 C(n, k) mod p
参数:
n, k: 非负整数
p: 质数模数
返回:
int: C(n, k) mod p
示例:
>>> combination_mod(10, 3, 1000000007)
120
"""
if k < 0 or k > n:
return 0
# C(n, k) = n! / (k! × (n-k)!)
fact_n = factorial_mod(n, p)
fact_k = factorial_mod(k, p)
fact_nk = factorial_mod(n - k, p)
# 使用逆元进行除法
inv_fact_k = mod_inverse_fermat(fact_k, p)
inv_fact_nk = mod_inverse_fermat(fact_nk, p)
return (fact_n * inv_fact_k % p) * inv_fact_nk % p
应用2：大数运算¶
问题：计算非常大的数的运算结果
def large_multiplication(a, b, mod):
"""
计算大数乘积 a × b mod mod
参数:
a, b: 大整数
mod: 模数
返回:
int: a × b mod mod
"""
return mod_pow(a, b, mod)
应用3：模运算性质验证¶
def verify_modular_properties():
"""
验证模运算的性质
"""
a, b, c, m = 15, 7, 9, 10
# 加法性质
assert mod_add(a, b, m) == (a + b) % m
print("✓ 加法性质验证通过")
# 减法性质
assert mod_sub(a, b, m) == (a - b) % m
print("✓ 减法性质验证通过")
# 乘法性质
assert mod_mul(a, b, m) == (a * b) % m
print("✓ 乘法性质验证通过")
# 幂运算性质
assert mod_pow(a, 3, m) == (a ** 3) % m
print("✓ 幂运算性质验证通过")
# 同余传递性
if (a - b) % m == 0 and (b - c) % m == 0:
assert (a - c) % m == 0
print("✓ 传递性验证通过")
print("\n所有性质验证通过！")
# 运行验证
verify_modular_properties()
实战练习¶
练习1：快速幂的递归实现¶
任务：用递归方式实现快速幂算法
def mod_pow_recursive(a, b, m):
"""
用递归方式实现快速幂
提示：
- 如果 b == 0，返回 1
- 如果 b 是偶数，返回 mod_pow_recursive(a, b//2, m)^2 mod m
- 如果 b 是奇数，返回 a × mod_pow_recursive(a, b-1, m) mod m
"""
# 你的代码
pass
练习2：判断同余¶
任务：判断两个数是否模 m 同余
def are_congruent(a, b, m):
"""
判断 a 和 b 是否模 m 同余
参数:
a, b: 整数
m: 模数
返回:
bool: 如果同余返回 True，否则返回 False
示例:
>>> are_congruent(15, 5, 10)
True
>>> are_congruent(15, 6, 10)
False
"""
# 你的代码
pass
练习3：模方程求解¶
任务：求解 x，使得 a × x ≡ b (mod m)
def solve_modular_equation(a, b, m):
"""
求解方程 a × x ≡ b (mod m)
参数:
a, b: 整数
m: 模数
返回:
int: x 的值（在 [0, m-1] 范围内）
如果无解返回 None
提示：使用模逆元
示例:
>>> solve_modular_equation(3, 5, 7)
4 # 因为 3 × 4 = 12 ≡ 5 (mod 7)
"""
# 你的代码
pass
章节小结¶
本章介绍了模运算的核心概念：
- 模运算的基本概念：理解同余的概念和模运算的性质
- 快速幂算法：掌握快速幂算法，时间复杂度 O(log n)
- 模逆元：理解模逆元的概念、存在条件和求法
- 费马小定理：掌握费马小定理及其在求模逆元中的应用
- 模除法：学会用逆元实现模除法
模运算是现代密码学的基础，请务必熟练掌握。
下一步¶
继续学习第三章：同余方程，学习如何求解各种类型的同余方程。
重点提醒： - 模运算中不能直接进行除法，必须用逆元 - 快速幂算法是核心，务必掌握 - 费马小定理仅在模数为质数时适用