扩展欧拉定理：数论中的降幂利器
探索模运算的深层奥秘，掌握算法竞赛与密码学中的核心工具
什么是扩展欧拉定理？
1.1 定理表述
在数论中，欧拉定理指出，如果两个正整数 a 和 m 互质，那么：
其中 φ(m) 是欧拉函数，表示小于等于 m 且与 m 互质的正整数个数。
而扩展欧拉定理（Extended Euler's Theorem）则去除了 a 和 m 必须互质的限制，适用于所有正整数 a 和 m。其核心公式如下：
如果 b < φ(m)，则直接计算 ab mod m 即可，无需使用降幂公式。
1.2 欧拉函数 φ(m) 的计算
要使用扩展欧拉定理，首先需要计算 φ(m)。欧拉函数的计算公式为：
其中 p 是 m 的所有不同质因数。例如，若 m = 12，其质因数为 2 和 3，则：
φ(12) = 12 × (1 - 1/2) × (1 - 1/3) = 12 × 1/2 × 2/3 = 4
小于等于 12 且与 12 互质的数有：1, 5, 7, 11，共 4 个，验证正确。
扩展欧拉定理的推导思路
扩展欧拉定理的证明相对复杂，主要依赖于数论中的中国剩余定理和模运算的性质。这里提供一个直观的理解路径：
将模数 m 分解为质因数的乘积：m = p1^k1 p2^k2 ... pn^kn。
对于每个质因数幂 p^k，证明 a^b ≡ a^(b mod φ(p^k) + φ(p^k)) (mod p^k)。这一步需要分 a 和 p 互质或不互质两种情况讨论。
利用中国剩余定理，将各个质因数幂下的同余式合并，得到模 m 下的同余式。由于 φ(m) = φ(p1^k1) φ(p2^k2) ...，最终指数部分可以统一为 φ(m)。
a 和 m 不互质的情况。当 a 和 m 有公因数时，aφ(m) ≡ 1 (mod m) 不再成立，但通过增加 φ(m) 到指数中，可以恢复同余关系。
实际应用场景
扩展欧拉定理在算法竞赛、密码学和计算机科学中有广泛的应用，尤其是在处理大数模幂运算时。
3.1 算法竞赛中的大数降幂
在编程竞赛中，经常遇到计算 a^b mod m 的问题，其中 b 是一个非常大的数（例如 b 以字符串形式给出，或者 b 是另一个幂运算的结果）。此时，直接计算 a^b 会导致溢出或超时。
示例： 计算 2^(10^100) mod 1000。
1. 首先计算 φ(1000)。1000 = 2^3 5^3，φ(1000) = 1000 (1-1/2) (1-1/5) = 400。
2. 由于指数 10^100 远大于 400，使用扩展欧拉定理：
2^(10^100) ≡ 2^(10^100 mod 400 + 400) (mod 1000)
3. 计算 10^100 mod 400。由于 10^2 = 100，10^3 = 1000 ≡ 0 (mod 400)，所以 10^100 ≡ 0 (mod 400)。
4. 最终结果为 2^(0 + 400) mod 1000。
3.2 密码学中的模幂运算
在 RSA 加密算法中，模幂运算 M^e mod n 是核心操作。虽然 RSA 中 e 通常较小，但在某些变体或协议中，可能需要处理巨大的指数。扩展欧拉定理可以帮助优化这些计算，尤其是在公钥或私钥指数非常大的情况下。
此外，在离散对数问题和椭圆曲线密码学中，模运算的周期性是基础，扩展欧拉定理提供了更一般的周期性描述。
3.3 编程中的实现技巧
在实现大数模幂时，需要注意以下几点：
- 数据类型： 使用
long long或__int128防止乘法溢出。 - 快速幂： 使用二进制分解的方法，将时间复杂度从
O(b)降低到O(log b)。 - 欧拉函数预处理： 如果需要多次计算不同模数的欧拉函数，可以预处理质数表，加速
φ(m)的计算。
扩展欧拉定理与其他定理的对比
| 特性 | 扩展欧拉定理 | 欧拉定理 | 费马小定理 |
|---|---|---|---|
| 适用条件 | 任意正整数 a, m |
a 与 m 互质 |
a 与质数 p 互质 |
| 公式 | a^b ≡ a^(b mod φ(m) + φ(m)) (mod m) |
a^φ(m) ≡ 1 (mod m) |
a^(p-1) ≡ 1 (mod p) |
| 指数处理 | 需要判断 b 与 φ(m) 的大小 |
不适用 | 不适用 |
| 通用性 | 最高 | 中等 | 最低 |
| 典型应用 | 大数降幂、算法竞赛 | 数论证明、密码学基础 | 质数测试、RSA 密钥生成 |
4.1 网友还关心：为什么费马小定理是特例？
当模数 m 为质数 p 时，φ(p) = p - 1。如果 a 与 p 互质（即 a 不是 p 的倍数），则扩展欧拉定理中的条件 b ≥ φ(m) 通常满足，公式变为：
a^b ≡ a^(b mod (p-1) + (p-1)) (mod p)
如果 b 本身是 p-1 的倍数，则 b mod (p-1) = 0，公式简化为 a^b ≡ a^(p-1) (mod p) ≡ 1 (mod p)，这就是费马小定理。因此，费马小定理是扩展欧拉定理在模数为质数且底数与模数互质时的特例。
代码实现
以下是使用 C++ 实现的扩展欧拉定理和快速幂算法。代码包括计算欧拉函数、快速幂和降幂主函数。
#include <iostream>
#include <cmath>
using namespace std;
// 计算欧拉函数 φ(n)
long long euler_phi(long long n) {
long long result = n;
for (long long i = 2; i i <= n; i++) {
if (n % i == 0) {
while (n % i == 0)
n /= i;
result -= result / i;
}
}
if (n > 1)
result -= result / n;
return result;
}
// 快速幂算法：计算 (base^exp) % mod
long long fast_pow(long long base, long long exp, long long mod) {
long long result = 1;
base %= mod;
while (exp > 0) {
if (exp % 2 == 1)
result = (__int128)result base % mod;
base = (__int128)base base % mod;
exp /= 2;
}
return result;
}
// 扩展欧拉定理：计算 (a^b) % m
long long extended_euler(long long a, string b_str, long long m) {
long long phi = euler_phi(m);
long long b = 0;
// 将大数 b 以字符串形式读取，并计算 b % phi
for (char c : b_str) {
b = (b 10 + (c - '0')) % phi;
}
// 如果 b 的原始值大于等于 phi，则加上 phi
// 这里简化处理，假设 b 字符串表示的数很大，肯定大于 phi
// 实际应用中需要判断 b 的位数或值是否大于 phi
b += phi;
return fast_pow(a, b, m);
}
int main() {
long long a = 2;
string b_str = "100"; // 表示 10^100
long long m = 1000;
cout << "Result: " << extended_euler(a, b_str, m) << endl;
return 0;
}常见问题解答 (FAQ)
费马小定理是扩展欧拉定理的一个特例。当模数 p 为质数时，φ(p) = p-1，此时扩展欧拉定理中的 φ(m) 替换为 p-1，即转化为费马小定理 a^(p-1) ≡ 1 (mod p)。扩展欧拉定理适用于任意正整数模数 m，而费马小定理仅适用于质数模数。
当指数 b 足够大（b >= φ(m)）时，直接对 b 取模会导致信息丢失，因为模幂运算的周期性在低指数时可能不成立。加上 φ(m) 是为了保证在模 m 意义下，指数部分保持同余关系的正确性，确保降幂公式 a^b ≡ a^(b mod φ(m) + φ(m)) (mod m) 成立。
通常使用快速幂算法结合扩展欧拉定理进行降幂。首先计算 φ(m)，然后根据指数大小决定是否需要加上 φ(m)，最后使用二进制分解的方法进行模幂运算，时间复杂度为 O(log b)。注意处理中间乘法溢出的问题，特别是在 C++ 中需要使用 __int128 或快速乘。
可以使用线性筛法（Euler Sieve）预处理 φ(m)，适用于需要多次查询不同 m 的情况。对于单次查询，可以使用试除法，时间复杂度为 O(√m)。如果 m 是质数，φ(m) = m-1；如果 m 是质数的幂 p^k，φ(m) = p^k - p^(k-1)。
常见于需要计算大数幂取模的题目，如 a^b mod m，其中 b 是字符串形式的大数，或者 b 是另一个幂运算的结果。典型题目包括 "Power Tower"（幂塔）、"Modulo Sum" 等。