第90课 - 模运算与快速幂

学习目标

完成本课学习后，你将能够：

理解并熟练运用模运算的基本性质，用于简化大数计算。
掌握快速幂算法的原理与实现，能在 O(log n) 时间复杂度内计算大数幂取模。
学会利用费马小定理计算模素数下的乘法逆元。
能够将这些技术应用于实际问题，如加密算法和组合数计算。

核心概念

1. 模运算（Modular Arithmetic）

模运算就是我们常说的“求余数”。记作 a mod n，表示整数 a 除以整数 n 后得到的余数。例如，17 mod 5 = 2。

核心性质（以下等式在模 n 意义下成立）：

(a + b) mod n = [(a mod n) + (b mod n)] mod n
(a * b) mod n = [(a mod n) * (b mod n)] mod n
(a - b) mod n = [(a mod n) - (b mod n) + n] mod n （注意加 n 是为了保证结果非负）

理解提示：可以把模运算想象成一个循环的钟面（模12）。在钟面上，13点就是1点，25点也是1点。这些性质让我们可以将大数的复杂运算分解为小数的运算，每一步结果都控制在较小的范围内。

2. 快速幂算法（Fast Power）

直接计算 a^n 当 n 很大时（如 n=10^9），结果会大得无法存储。而快速幂算法可以高效地计算 (a^n) mod p。

核心思想：利用指数 n 的二进制表示来分解计算过程。例如，计算 a^13，而 13 的二进制是 1101（即 8 + 4 + 1）。因此：a^13 = a^8 * a^4 * a^1。我们可以通过不断将底数平方，并检查指数二进制位的每一位是否为1，来累乘结果。

a^1 -> (a^1)^2 = a^2 -> (a^2)^2 = a^4 -> (a^4)^2 = a^8
遇到二进制位是1，就将当前的幂累乘到结果中。

优势：时间复杂度从 O(n) 降低到 O(log n)。

3. 费马小定理与逆元

费马小定理：如果 p 是一个质数，且整数 a 不是 p 的倍数，那么：a^(p-1) ≡ 1 (mod p)。

逆元（Modular Multiplicative Inverse）：对于整数 a，其模 p 的逆元 x 满足：a * x ≡ 1 (mod p)。逆元在模意义下相当于“倒数”。

推导：由费马小定理 a^(p-1) ≡ 1 (mod p) 可得：a * a^(p-2) ≡ 1 (mod p)。因此，a 模 p 的逆元就是 a^(p-2) mod p。这里 p 必须是质数。

代码示例

以下代码使用 Python 实现了快速幂和利用费马小定理求逆元。

def fast_power(base, exponent, modulus):
    """
    使用快速幂算法计算 (base^exponent) % modulus
    :param base: 底数
    :param exponent: 指数（非负整数）
    :param modulus: 模数
    :return: (base^exponent) % modulus 的结果
    """
    # 处理模数为1的特殊情况（任何数模1都为0）
    if modulus == 1:
        return 0
    
    result = 1  # 初始化结果为1，因为任何数的0次幂都是1
    base = base % modulus  # 预处理，确保底数小于模数
    
    while exponent > 0:
        # 如果当前指数是奇数（二进制末位为1），则将当前底数累乘到结果中
        if exponent % 2 == 1:
            result = (result * base) % modulus
        
        # 指数右移一位（相当于除以2），准备下一次循环
        exponent = exponent >> 1
        # 底数平方，并对模数取模，为下一次迭代做准备
        base = (base * base) % modulus
    
    return result

def mod_inverse_fermat(a, p):
    """
    利用费马小定理计算 a 模 p 的逆元（p必须为质数，且a不是p的倍数）
    :param a: 需要求逆的数
    :param p: 质数模数
    :return: a 模 p 的逆元
    """
    # 费马小定理：a^(p-1) ≡ 1 (mod p) => a * a^(p-2) ≡ 1 (mod p)
    # 所以逆元是 a^(p-2) mod p
    return fast_power(a, p - 2, p)

# 主程序演示
if __name__ == "__main__":
    # 示例1：快速幂计算 (2^1000000) % 1000000007
    base, exp, mod = 2, 1000000, 1000000007
    result_power = fast_power(base, exp, mod)
    print(f"({base}^{exp}) % {mod} = {result_power}")
    
    # 示例2：计算 3 在模 7 下的逆元
    a, prime_p = 3, 7
    inverse = mod_inverse_fermat(a, prime_p)
    print(f"数字 {a} 在模 {prime_p} 下的逆元是 {inverse}")
    # 验证：3 * 5 = 15, 15 % 7 = 1， 所以逆元正确。

代码输出：

(2^1000000) % 1000000007 = 171798689
数字 3 在模 7 下的逆元是 5

实践练习

练习 1：基础快速幂

编写一个函数 my_pow(base, exp, mod)，计算 (base^exp) % mod。使用快速幂算法实现。

输入：base=3, exp=20, mod=13
预期输出：3
提示：3^20 非常大，但用快速幂和取模可以轻松处理。

练习 2：求解逆元

给定质数 p=11 和一个数字 a=4，计算 a 模 p 的逆元。

要求：使用费马小定理（即调用你写的快速幂函数）。
预期输出：3 （因为 4*3=12，12 mod 11=1）

练习 3：组合数取模（综合应用）

组合数公式 C(n, k) = n! / (k! * (n-k)!)。在模质数 p 的意义下，除法需要转换为乘以逆元。请计算 C(10, 3) mod 7 的值。

步骤提示：
1. 分别计算 10! mod 7， 3! mod 7，和 (10-3)! = 7! mod 7。
2. 计算分母 k! * (n-k)! 的模值，并求其模 p 的逆元。
3. 将分子乘以分母的逆元，再对 p 取模。
预期输出：1 （先算出 C(10,3)=120， 120 mod 7 = 1）

常见错误

误用模运算性质：在减法 (a - b) mod n 时，直接计算 (a mod n - b mod n) 可能得到负数。正确做法：((a mod n) - (b mod n) + n) % n。
快速幂初始值与边界错误：将结果 result 初始值设为 0 而不是 1；或者没有处理指数为 0 的情况。另外，在循环中应先检查指数奇偶性，再进行平方和右移。
费马小定理前提条件：使用费马小定理求逆元时，必须确保模数 p 是质数，且待求逆的数 a 与 p 互质（即 a 不是 p 的倍数）。否则定理不成立，会得到错误结果。
溢出问题（在其他语言中）：在 C++、Java 等语言中，即使应用了模运算性质，在计算 a * a 时仍可能溢出。需要使用更安全的乘法方式，例如 ((long long)a * a) % mod 或实现一个“快速乘”来避免溢出。

小结

本课我们学习了三个紧密关联的重要数学工具：

模运算：是处理大数和周期性问题的基石，其核心性质让我们能化繁为简。
快速幂：是计算大数幂取模的高效算法，通过将指数二分，将时间复杂度优化至对数级别。
费马小定理与逆元：结合快速幂，它为我们提供了在模质数意义下求“倒数”（逆元）的有效方法。

这三者的结合，在密码学（如RSA算法）、组合数学（如计算组合数取模）和计算机科学的其他领域有极其广泛的应用。在下一课《组合数学》中，我们将看到如何直接运用快速幂和逆元来解决组合数计算问题。务必熟练掌握本课的代码实现，它们是你工具箱中的重要组成部分。

练习编辑器

rust