欧拉函数 (Euler’s Totient Function)

1. 定义

欧拉函数，通常用希腊字母 $\phi(n)$ (phi) 表示。 它的定义是：对于正整数 $n$，$\phi(n)$ 表示小于等于 $n$ 的正整数中，与 $n$ 互素（最大公约数为 1）的数的个数。

直观理解：在 $1$ 到 $n$ 的范围内，有多少个整数与 $n$ “没有共同因子”。

举个栗子

求 $\phi(10)$：

1. 列出 1 到 10 的数：1, 2, 3, 4, 5, 6, 7, 8, 9, 10
2. 找出与 10 互素的数：
   • 1 (互素)
   • 2 (公约数2，排除)
   • 3 (互素)
   • 4 (公约数2，排除)
   • 5 (公约数5，排除)
   • 6 (公约数2，排除)
   • 7 (互素)
   • 8 (公约数2，排除)
   • 9 (互素)
   • 10 (公约数10，排除)
3. 互素的数有：{1, 3, 7, 9}，共 4 个。
4. 所以 $\phi(10) = 4$。

2. 核心计算公式

在密码学（特别是 RSA）中，我们不需要用笨办法数数，而是利用它的数学性质直接计算。

情况 A：$n$ 是素数

如果 $p$ 是一个素数，那么比它小的所有正整数都与它互素。

$$ \phi(p) = p - 1 $$

情况 B：$n$ 是两个素数的乘积 (RSA 核心)

如果 $n = p \times q$（且 $p, q$ 互不相同），利用欧拉函数的积性：

$$ \phi(n) = \phi(p) \times \phi(q) $$

进而推导出 RSA 密钥生成中最关键的公式：

$$ \phi(n) = (p-1)(q-1) $$

这也是 RSA 安全性的关键：你只知道 $n$，很难算出 $\phi(n)$；但如果你知道 $p$ 和 $q$，算 $\phi(n)$ 易如反掌。

3. 欧拉定理 (Euler’s Theorem)

这是 RSA 能够“解密还原”的根本数学原理。

定理内容： 如果两个正整数 $a$ 和 $n$ 互素，那么：

$$ a^{\phi(n)} \equiv 1 \pmod n $$

在 RSA 中的意义： 还记得我们需要 $e \times d \equiv 1 \pmod{\phi(n)}$ 吗？ 这正是为了凑出欧拉定理的形式，让密文经过 $e \times d$ 次运算后，能够让底数（明文）“转一圈回到原点”，从而变为 1（或者说变为 $M \times 1$），实现解密。

4. 与 RSA 的关系图谱

1. 生成公钥/私钥：需要计算 $\phi(n) = (p-1)(q-1)$。
2. 计算私钥 $d$：需要求解 $e \times d \equiv 1 \pmod{\phi(n)}$（模逆元依赖于 $\phi(n)$）。
3. 安全性：攻击者想从公钥 $n$ 破解私钥 $d$，必须先算出 $\phi(n)$。要算 $\phi(n)$，必须分解 $n$ 得到 $p, q$。这就是大整数分解难题。

---

相关链接：

• euclidean-algorithm

Related notes

• 相关概念: 辗转相除法
• 相关概念: 3DES
• 相关概念: 仿射密码(Affine-Cipher)