オイラー関数
$1$ から $n$ までの自然数の中で、$n$ と互いに素なものの個数。
\phi(n) = n \prod_{i=1}^k \left( 1 - \frac{1}{p_i} \right)
オイラーの定理
$a$ と $n$ が互いに素であるとき、
a^{\phi(n)} \equiv 1 \pmod n
が成り立つ。
RSA暗号
秘密鍵 $d$ は次の条件を満たすように選ばれる。
ed \equiv 1 \pmod{\phi(n)}
これとオイラーの定理より
\begin{align}
m^{ed} &= m^{1 + k\phi(n)} \\
&= m \cdot (m^{\phi(n)})^k \\
&\equiv m \cdot (1)^k \\
&\equiv m \pmod n
\end{align}
🍀