欧拉函数与欧拉定理

这是一个常见的误解。公式 φ(n) = n - 1 仅当 n 是质数时 成立。

因为质数 p 的定义就是只有 1 和 p 两个正因数，所以在 1 到 p-1 之间的所有整数都与 p 互质。

• 例如：n = 7 (质数)。小于等于 7 且与 7 互质的数是 1, 2, 3, 4, 5, 6，共 6 个。所以 φ(7) = 6 = 7 - 1。
• 例如：n = 12 (合数)。小于等于 12 且与 12 互质的数是 1, 5, 7, 11，共 4 个。所以 φ(12) = 4，而 12 - 1 = 11。显然 φ(12) ≠ 12 - 1。

欧拉定理 a^φ(n) ≡ 1 (mod n) 成立的重要前提是：a 与 n 必须互质，即 gcd(a, n) = 1。

如果 a 与 n 不互质，定理就不一定成立了。

例如：a = 2, n = 4。gcd(2, 4) = 2 ≠ 1。欧拉函数 φ(4) = 2 (与4互质的数是1, 3)。

我们计算 a^φ(n) mod n = 2^φ(4) mod 4 = 2² mod 4 = 4 mod 4 = 0。

结果是 0，而不是 1。这说明当 a 和 n 不互质时，不能直接套用欧拉定理。

（注：对于不互质的情况，有欧拉定理的扩展形式，有时也称为费马-欧拉定理或欧拉降幂，例如当 b ≥ φ(n) 时，a^b ≡ a^{b mod φ(n) + φ(n)} (mod n)，但这超出了基础欧拉定理的范围。）

欧拉函数有一些方便计算的性质，特别是对于质数的幂和两个不同质数的乘积：

1. 质数的幂： 如果 p 是一个质数，k 是一个正整数 (k ≥ 1)，那么与 p^k 互质的数就是那些不被 p 整除的数。在 1 到 p^k 中，p 的倍数有 p^k-1 个 (p, 2p, ..., p^k-1·p)。所以：

   φ(p^k) = p^k - p^k-1 = p^k-1(p - 1) = p^k (1 - 1/p)

   例如：φ(8) = φ(2³) = 2³ - 2² = 8 - 4 = 4。 （与8互质的是1, 3, 5, 7）
   例如：φ(27) = φ(3³) = 3³ - 3² = 27 - 9 = 18。
2. 两个不同质数的乘积： 如果 p 和 q 是两个不同的质数，那么根据欧拉函数的 积性如果函数 f(n) 满足：对于任意互质的正整数 m 和 n，都有 f(mn) = f(m)f(n)，则称 f(n) 是积性函数。欧拉函数 φ(n) 就是一个积性函数。 性质：

   φ(pq) = φ(p) × φ(q) = (p - 1) × (q - 1)

   例如：φ(15) = φ(3 × 5) = φ(3) × φ(5) = (3 - 1) × (5 - 1) = 2 × 4 = 8。 （与15互质的是1, 2, 4, 7, 8, 11, 13, 14）
   例如：φ(77) = φ(7 × 11) = (7 - 1) × (11 - 1) = 6 × 10 = 60。

利用这些性质，结合欧拉函数的积性，我们可以计算任意正整数 n 的欧拉函数值。首先将 n 进行质因数分解 n = p₁^k₁ p₂^k₂ ... p_r^k_r，然后：

φ(n) = φ(p₁^k₁) × φ(p₂^k₂) × ... × φ(p_r^k_r)

这与之前提到的公式 φ(n) = n × ∏(1 - 1/p) 是等价的。

例如：φ(36) = φ(2² × 3²) = φ(2²) × φ(3²) = (2² - 2¹) × (3² - 3¹) = (4 - 2) × (9 - 3) = 2 × 6 = 12。

下面的图表展示了 n 从 1 到 50 时，欧拉函数 φ(n) 的值。观察值的变化趋势：

观察图表，你可能会发现：

• 当 n 是 质数 p 时，φ(p) = p - 1，这是图像上的局部最大值点（相对于前一个数）。
• 偶数 n 的 φ(n) 值通常比 n/2 小或等于 n/2（因为至少所有大于 n/2 的偶数都不与 n 互质，且 φ(n) ≤ n-1）。
• φ(n) 的值 整体上是增长的，但波动很大。
• 当 n 含有 较多不同的小质因数 时，φ(n) 相对于 n 的比值会比较小 (例如 φ(30) = 8)。

提示：图表将在您展开此部分时生成。

欧拉函数和欧拉定理是现代密码学基石之一——RSA 公钥加密算法 的核心数学原理。

RSA 的安全性很大程度上依赖于大整数质因数分解的困难性，以及计算欧拉函数 φ(n) 的困难性（如果不知道 n 的质因数分解）。

RSA 密钥生成过程简述：

1. 选择两个非常大的 秘密质数这两个质数 p 和 q 是保密的，只有密钥的拥有者知道。它们的乘积 n 是公开的。 p 和 q。
2. 计算它们的乘积 n = p × q。这个 n 是公开的，作为模数。
3. 计算 φ(n) = φ(p) × φ(q) = (p - 1) × (q - 1)。这个值是保密的。
4. 选择一个整数 e (1 < e < φ(n))，使得 e 与 φ(n) 互质 (gcd(e, φ(n)) = 1)。e 作为公钥指数，是公开的。
5. 计算 e 关于模 φ(n) 的乘法逆元找到一个整数 d，使得 e × d ≡ 1 (mod φ(n))。这通常使用扩展欧几里得算法计算。 d。即找到 d 使得 e × d = k × φ(n) + 1 (对于某个整数 k)。d 作为私钥指数，是保密的。

公钥： (n, e)      私钥： (n, d)

加密： (使用公钥) 假设明文是 M (一个小于 n 的整数)，密文 C = M^e mod n。

解密： (使用私钥) 收到密文 C 后，计算 M = C^d mod n。

解密为什么能成功？

C^d ≡ (M^e)^d ≡ M^e×d (mod n)

因为 e × d ≡ 1 (mod φ(n))，所以 e × d = k × φ(n) + 1。

M^e×d = M^{k×φ(n) + 1} = (M^φ(n))^k × M¹ (mod n)

根据 欧拉定理，如果 M 与 n 互质，M^φ(n) ≡ 1 (mod n)。所以：

(M^φ(n))^k × M ≡ 1^k × M ≡ M (mod n)

（即使 M 与 n 不互质，也可以证明这个解密过程仍然有效。）

因此，知道私钥 d 的人可以将密文 C 解密回明文 M。而不知道 d（或者等价地，不知道 p 和 q 从而无法计算 φ(n) 和 d）的人，很难从公钥 (n, e) 和密文 C 中恢复 M。

正如前面提到的，欧拉函数 φ(n) 是一个重要的 积性函数 (Multiplicative Function)。

这意味着，如果两个正整数 m 和 n 互质 (gcd(m, n) = 1)，那么它们乘积的欧拉函数值等于它们各自欧拉函数值的乘积：

φ(m × n) = φ(m) × φ(n)      (当 gcd(m, n) = 1)

重要提示： 这个性质要求 m 和 n 必须互质。

• 正确示例： gcd(4, 9) = 1。 φ(4) = 2 (1, 3)。φ(9) = 6 (1, 2, 4, 5, 7, 8)。 φ(36) = φ(4 × 9) = φ(4) × φ(9) = 2 × 6 = 12。 我们之前计算过 φ(36) = 12，验证了这一点。
• 错误示例： gcd(2, 4) = 2 ≠ 1。 φ(2) = 1。φ(4) = 2。 φ(8) = φ(2 × 4) = 4。 但 φ(2) × φ(4) = 1 × 2 = 2。 这里 φ(8) ≠ φ(2) × φ(4)，因为 2 和 4 不互质。

积性是数论函数的一个重要特性，它使得我们可以通过研究函数在质数幂即形如 p^k 的数，其中 p 是质数，k 是正整数。上的取值，来推断它在所有正整数上的取值。结合唯一分解定理（算术基本定理），任何正整数 n > 1 都可以唯一地分解为质数幂的乘积 n = p₁^k₁ p₂^k₂ ... p_r^k_r。由于不同的质数幂 p_i^k_i 和 p_j^k_j (i ≠ j) 总是互质的，我们可以应用积性性质：

φ(n) = φ(p₁^k₁ × p₂^k₂ × ... × p_r^k_r) = φ(p₁^k₁) × φ(p₂^k₂) × ... × φ(p_r^k_r)

这就是为什么计算 φ(p^k) 很重要的原因，也是质因数分解公式法的基础。