歐拉函數與歐拉定理

歐拉函數 (Euler's totient) $\varphi(n)$ 數 $1$ 到 $n$ 中與 $n$ 互質的個數。公式:質因數分解 $n = \prod p_i^{e_i}$ 後 $$\varphi(n) = n\prod\left(1 - \frac{1}{p_i}\right)$$ 特例 $\varphi(p) = p-1$、$\varphi(p^k) = p^k - p^{k-1}$、互質時 $\varphi(mn) = \varphi(m)\varphi(n)$(積性)。

算例:$36 = 2^2\cdot3^2$,$\varphi(36) = 36\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right) = 36\cdot\frac{1}{2}\cdot\frac{2}{3} = 12$;$\varphi(100) = 40$。

歐拉定理:$\gcd(a,n) = 1$ 則 $a^{\varphi(n)}\equiv1\pmod n$,是費馬小定理對合數的推廣;所以 $\gcd(a,n) = 1$ 時,算 $a^k\bmod n$ 可以把指數先對 $\varphi(n)$ 取餘(不互質時不行,例如 $2^2\equiv0\pmod4$)。

$\varphi(n)$ 是乘法群 $U(n)$ 的階、$\mathbb{Z}_n$ 生成元的個數;RSA 的核心是 $ed\equiv1\pmod{\varphi(N)}$,而 $\varphi(N) = (p-1)(q-1)$ 必須知道質因數才算得出——這正是 RSA 安全性的來源。