9.10 Euler の定理
次節で説明する RSA 暗号をはじめとした現代的なメッセージ暗号化方式では、整数の大きな冪を特定の整数で割った剰余を求める操作が使われる。この操作に関する基本的な事実は、Euler が示した合同関係に関する定理から従う。
任意の正整数 \(n\) に対して関数 \(\phi(n)\colon \mathbb{N} \to \mathbb{N}\) を次のように定める:
この関数を Euler の \(\phi\) 関数 (Euler's \(\phi\) function) と呼ぶ1。
例えば \([0..7)\) に属する整数は全て \(7\) と互いに素なので \(\phi(7) = 6\) が成り立つ。素数 \(7\) と互いに素でない整数は \(0\) だけである。また、\([0..12)\) に属する整数で \(12\) と互いに素なのは \(1\), \(5\), \(7\), \(11\) である事実から \(\phi(12) = 4\) が分かる2。
一般に、素数 \(p\) に対して \(\phi(p) = p - 1\) が成り立つ: \([0..p)\) に属する任意の整数は \(p\) と互いに素である。\(n\) が合成数のとき \(\phi\) 関数は少し複雑になる: 次節でまた考える。
Euler の定理は合同算術の言葉で表明される場合が多い:
\(n\) と \(k\) が互いに素なら、次の合同関係が成り立つ:
Euler の定理は \(\mathbb{Z}_{n}\) を使って書き換えると単純になる。
\(n\) と互いに素な \([0..n)\) の要素を \(\mathbb{Z}_{n}^{\ast}\) で表す:
この定義から次の等式が分かる:
全ての \(k \in \mathbb{Z}_{n}^{\ast}\) で次の等式が成り立つ:
定理 9.10.3 は次に示す二つの簡単な補題から従う。
まず、\(\mathbb{Z}_{n}^{\ast}\) は \(\mathbb{Z}_{n}\) における乗算で閉じている:
任意の \(j,k \in \mathbb{Z}_{n}^{\ast}\) に対して \(j \cdot_{n} k \in \mathbb{Z}_{n}^{\ast}\) が成り立つ。
補題 9.10.4 には簡単な証明が数多く知られている (問題 9.70)。
\(\mathbb{Z}_{n}\) の任意の要素 \(k\) と部分集合 \(S\) に対して、\(kS\) を次のように定義する:
任意の \(k \in \mathbb{Z}_{n}^{\ast}\) と \(S \subseteq \mathbb{Z}_{n}\) に対して、次の等式が成り立つ:
証明 定理 9.9.5 より、\(k \in \mathbb{Z}_{n}^{\ast}\) は打ち消し可能である。よって
が分かる。つまり \(S\) の各要素に \(\mathbb{Z}_{n}\) で \(k\) を乗じると、それぞれ \(kS\) の異なる要素となる。ここから \(S\) と \(kS\) が同じ個数の要素を持つと分かる。 ■
\(k \in \mathbb{Z}_{n}^{\ast}\) なら、次の等式が成り立つ:
証明 補題 9.10.4 より、\(\mathbb{Z}_{n}^{\ast}\) の二要素の \(\mathbb{Z}_{n}\) における積は \(\mathbb{Z}_{n}^{\ast}\) に属する。よって任意の \(k \in \mathbb{Z}_{n}^{\ast}\) に対して \(k \mathbb{Z}_{n}^{\ast} \subseteq \mathbb{Z}_{n}^{\ast}\) である。一方で補題 9.10.6 より \(k\mathbb{Z}_{n}^{\ast}\) と \(\mathbb{Z}_{n}^{\ast}\) は同じ要素数だから、両者は等しいと分かる。 ■
\(\mathbb{Z}_{n}\) に対する Euler の定理 (定理 9.10.3) を証明する準備がこれで整った:
定理 9.10.3 の証明 \(\mathbb{Z}_{n}^{\ast}\) の全要素の \(\mathbb{Z}_{n}\) における積を \(P\) とする:
任意の \(k \in \mathbb{Z}_{n}^{\ast}\) に対して、\(Q\) を次のように定める:
このとき \(k\) を前方に移動させれば直ちに次の等式を得る:
一方で、\(Q\) は \(k\mathbb{Z}_{n}^{\ast}\) の全要素の \(\mathbb{Z}_{n}\) における積である。系 9.10.7 より \(k\mathbb{Z}_{n}^{\ast} = \mathbb{Z}_{n}^{\ast}\) だから、\(Q\) は \(P\) と同じ整数を異なる順番で乗じた積だと分かる。よって次の等式が成り立つ:
さらに補題 9.10.4 より \(P \in \mathbb{Z}_{n}^{\ast}\) だから、\(P\) を両辺から打ち消すことができる。つまり次の結論を得る:
■
Euler の定理は \(n\) を法とする乗算における逆元を求める方法を与える: \(k\) が \(n\) と互いに素なら、\(k^{\phi(n)- 1}\) が \(\mathbb{Z}_{n}\) における \(k\) の逆元である。\(k\) の冪は高速冪乗で効率的に計算できる。しかし、このアプローチでは \(\phi(n)\) の値が必要になる。すぐに見るように、\(n\) の素因数分解が分かっていれば \(\phi(n)\) は簡単に計算できる。しかし \(n\) の素因数分解は \(n\) が巨大なとき一般に難しいので、\(\mathbb{Z}_{n}\) における \(k\) の逆元を計算する最良のアプローチは粉砕法 (第 9.2.2 項) で変わらない。
Fermat の小定理
ちょうどいい機会なので、Euler の定理の有名な特殊ケースにも触れておく。この事実は Euler より一世紀ほど前に Fermat が発見した。
\(p\) が素数で、\(k\) が \(p\) の倍数でないとする。このとき次の関係が成り立つ:
9.10.1 Euler の \(\phi\) 関数の計算
RSA 暗号は二つの大きな素数の積を法とする剰余算術を利用する。そこで、まずは素数 \(p\), \(q\) に対する \(\phi(pq)\) の初等的な計算方法を示しておく:
二つの素数 \(p\), \(q\) が \(p \neq q\) を満たすなら、次の等式が成り立つ:
証明 \(p\) と \(q\) は素数なので、\(pq\) と互いに素でない整数は \(p\) または \(q\) の倍数である。\([0..pq)\) に属する \(pq\) 個の整数の中に \(p\) の倍数はちょうど \(q\) 個、\(q\) の倍数はちょうど \(p\) 個ある。\(p\) と \(q\) は互いに素なので、\([0..pq)\) に \(p\) の倍数かつ \(q\) の倍数であるような整数は \(0\) 以外に存在しない。よって \(pq\) と互いに素でない整数は \([0..pq)\) の中に \(p + q - 1\) 個ある。ここから次の等式を得る:
■
次の定理は任意の \(n\) に対する \(\phi(n)\) を計算する方法を与える:
-
\(p\) が素数なら、任意の整数 \(k \geq 1\) に対して次の等式が成り立つ:
\[ \phi(p^{k}) = p^{k} \left( 1 - \frac{1}{p} \right) = p^{k} - p^{k-1} \] -
\(a\) と \(b\) が互いに素なら、次の等式が成り立つ:
\[ \phi(ab) = \phi(a) \phi(b) \]
定理 9.10.10 を使って \(\phi(300)\) を計算する例を示す:
補題 9.10.9 は定理 9.10.10 \(\text{(b)}\) の特殊ケースとして示せる: 素数 \(p\) では \(\phi(p) = p - 1\) が成り立つ。
定理 9.10.10 \(\text{(a)}\) の証明では、\([0..p^{k})\) に含まれる \(p^{k}\) 個の整数のちょうど \(p\) 個に \(1\) 個だけが \(p\) で割り切れる事実を利用する。つまり、その \(p^{k}\) 個の整数の \(1/p\) が \(p\) で割り切れる。ここから次の等式を得る:
定理 9.10.10 \(\text{(b)}\) の証明は練習問題 (問題 9.64) とする。
定理 9.10.10 を使うと次の系が得られる:
\(n\) を整数、\(p_{1}\), \(p_{2}\), \(\ldots\) \(p_{j}\) を \(n\) の素因数とするとき、次の等式が成り立つ:
証明 \(n = p_{1}^{e_{1}}p_{2}^{e_{2}} \cdots p_{j}^{e_{j}}\) とすれば、次の等式が分かる:
■