Open Clock

欧拉函数 φ(n) 的定义

欧拉函数 φ(n)（Euler's Totient Function）定义为：小于等于 n 的正整数中，与 n 互素的数的个数。

例如：φ(10) = 4，因为 {1, 3, 7, 9} 与 10 互素。

计算公式

若 n 的素因数分解为 n = p₁^a₁ × p₂^a₂ × ... × p_k^a_k，则：

φ(n) = n × ∏(1 - 1/p_i) = n × (1 - 1/p₁)(1 - 1/p₂)...(1 - 1/p_k)

特殊情况

• 素数 p：φ(p) = p - 1（1 到 p-1 都与 p 互素）
• 素数幂 p^k：φ(p^k) = p^k - p^k-1 = p^k-1(p - 1)
• 两个素数乘积 n = p × q：φ(n) = (p - 1)(q - 1)
• 互素乘积：若 gcd(m, n) = 1，则 φ(m × n) = φ(m) × φ(n)（积性函数）

例如：φ(15) = φ(3) × φ(5) = 2 × 4 = 8

欧拉定理

若 gcd(a, n) = 1（a 与 n 互素），则：

a^φ(n) ≡ 1 (mod n)

证明思路：将与 n 互素的数排成 {r₁, r₂, ..., r_φ(n)}，乘以 a 后仍是模 n 的完全剩余系，即 {a×r₁, a×r₂, ..., a×r_φ(n)} 与 {r₁, r₂, ..., r_φ(n)} 是同一组数的排列。将两组数的乘积取模即得结论。

费马小定理（欧拉定理的特例）

当 n = p 为素数时，φ(p) = p - 1，欧拉定理变为：

a^p-1 ≡ 1 (mod p)，当 gcd(a, p) = 1 时

等价形式：对任意整数 a，a^p ≡ a (mod p)。

在 RSA 中的应用

RSA 的核心依赖于欧拉定理：

1. 选两个大素数 p, q，计算 n = p × q
2. 计算 φ(n) = (p - 1)(q - 1)
3. 选公钥 e，满足 1 < e < φ(n) 且 gcd(e, φ(n)) = 1
4. 计算私钥 d = e^-1 mod φ(n)（用扩展欧几里得算法）
5. 加密：c = m^e mod n
6. 解密：m = c^d mod n = m^ed mod n = m^1+kφ(n) mod n = m (mod n)

解密正确性由欧拉定理保证：因为 ed ≡ 1 (mod φ(n))，所以 m^ed = m × (m^φ(n))^k ≡ m × 1^k = m (mod n)。

阶与原根

阶：a 在模 n 下的阶 ord_n(a) 是满足 a^k ≡ 1 (mod n) 的最小正整数 k。由欧拉定理知 ord_n(a) | φ(n)。

原根：若 ord_n(a) = φ(n)，则 a 是模 n 的原根。原根的存在性：n 有原根当且仅当 n = 1, 2, 4, p^k, 2p^k（p 为奇素数）。

原根在 Diffie-Hellman 密钥交换中用于生成循环群的生成元。