欧拉定理和费马小定理：数论的基石与密码学的灵魂

欧拉定理：广义的模幂规律

1.1 定义与前提条件

欧拉定理（Euler's Theorem）是数论中的一个核心定理，它描述了当两个正整数互质时，幂运算在模运算下的周期性规律。要理解欧拉定理，首先需要引入欧拉函数 φ(n) 的概念。

1.2 深度解析与示例

让我们通过一个具体的例子来验证欧拉定理。假设 n = 15，我们需要计算 φ(15)。

• 首先对 15 进行质因数分解：15 = 3 × 5。
• 根据欧拉函数的积性性质：φ(15) = φ(3) × φ(5)。
• 因为 3 和 5 都是质数，所以 φ(3) = 3-1 = 2，φ(5) = 5-1 = 4。
• 因此，φ(15) = 2 × 4 = 8。
• 选取与 15 互质的 a，例如 a = 2。
• 计算 2⁸ = 256。
• 验证模运算：256 ÷ 15 = 17 ... 1。余数确实为 1。

这个定理的强大之处在于它将复杂的幂运算简化了。在计算大数的模幂时，我们可以利用欧拉定理将指数对 φ(n) 取模，从而极大地减少计算量。

费马小定理：质数特有的简洁之美

2.1 定理表述

费马小定理（Fermat's Little Theorem）是欧拉定理在模数为质数时的特例。法国数学家皮埃尔·德·费马在17世纪发现了这一规律，它揭示了质数在模运算中的特殊地位。

2.2 为什么它是欧拉定理的特例？

这是一个非常关键的理解点。根据欧拉函数的性质，对于任意质数 p，小于 p 且与 p 互质的正整数有 p-1 个（即 1, 2, ..., p-1）。因此，φ(p) = p - 1。

将 φ(p) = p - 1 代入欧拉定理公式 a^φ(n) ≡ 1 (mod n)，即可直接得到 a^p-1 ≡ 1 (mod p)。由此可见，费马小定理并不孤立，它是欧拉定理在特定条件下的自然延伸。

2.3 反素性测试（伪素数检测）

费马小定理的一个重要应用是素性测试。虽然满足 a^p-1 ≡ 1 (mod p) 的数 p 不一定是质数（这样的数被称为伪素数），但它提供了一个快速的初步筛选工具。

历史沿革与现代应用

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
def euler_phi(n):
    result = n
    p = 2
    while p  p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p
            result -= result // p
        p += 1
    if n > 1:
        result -= result // n
    return result
验证欧拉定理
a = 7
n = 15
if gcd(a, n) == 1:
    phi_n = euler_phi(n)
    print(f"phi({n}) = {phi_n}")
    # 计算 a^phi(n) % n
    # 使用 pow(a, b, m) 进行高效的模幂运算
    res = pow(a, phi_n, n)
    print(f"{a}^{phi_n} mod {n} = {res}")
    print("欧拉定理验证:", "成功" if res == 1 else "失败")

常见误区与注意事项