オイラーのファイ関数とモジュラ逆数

数学

こんにちは。今回も暗号のための数学です。う～ん、ちゃんと全体像を理解できていないから、場当たり的に数学をやっている感じになっています。ま、PVが少ない過疎なサイトなので、とりあえず自分の確認用として書いておくことにします・・・

オイラーの\(\phi\)関数とは

ある正の整数\(n\)に対して、\(1,2,\cdots,n\)の中で\(n\)と互いに素であるものの個数を、オイラーの\(\phi\)関数（トーシェント関数）といい、\(\phi(n)\)と書きます。

とりあえず具体例から考えていきます。

正の整数\(1\)に対して、\(1\)と\(1\)の最大公約数は\(1\)なので、互いに素である数は\(1\)個といえます。
よって\(\phi(1)=1\)です。

正の整数\(2\)に対して、\(1,2\)の中で\(2\)と互いに素であるものは\(1\)だけで、\(1\)個あります。
よって\(\phi(2)=1\)です。

正の整数\(3\)に対して、\(1,2,3\)の中で\(3\)と互いに素であるものは、\(1,2\)の\(2\)個あります。
よって\(\phi(3)=2\)です。

正の整数\(4\)に対して、\(1,2,3,4\)の中で\(4\)と互いに素であるものは、\(1,3\)の\(2\)個あります。
よって\(\phi(4)=2\)です。

正の整数\(5\)に対して、\(1,2,\cdots,5\)の中で\(5\)と互いに素であるものは、\(1,2,3,4\)の\(4\)個あります。
よって\(\phi(5)=4\)です。

正の整数\(6\)に対して、\(1,2,\cdots,6\)の中で\(6\)と互いに素であるものは、\(1,5\)の\(2\)個あります。
よって\(\phi(6)=2\)です。

正の整数\(7\)に対して、\(1,2,\cdots,7\)の中で\(7\)と互いに素であるものは、\(1,2,3,4,5,6\)の\(6\)個あります。
よって\(\phi(7)=6\)です。

正の整数\(8\)に対して、\(1,2,\cdots,8\)の中で\(8\)と互いに素であるものは、\(1,3,5,7\)の\(4\)個あります。
よって\(\phi(8)=4\)です。

正の整数\(9\)に対して、\(1,2,\cdots,9\)の中で\(9\)と互いに素であるものは、\(1,2,4,5,7,8\)の\(6\)個あります。
よって\(\phi(9)=6\)です。

正の整数\(10\)に対して、\(1,2,\cdots,10\)の中で\(10\)と互いに素であるものは、\(1,3,7,9\)の\(4\)個あります。
よって\(\phi(10)=4\)です。

正の整数\(11\)に対して、\(1,2,\cdots,11\)の中で\(11\)と互いに素であるものは、\(1,2,3,4,5,6,7,8,9,10\)の\(10\)個あります。
よって\(\phi(11)=10\)です。

正の整数\(12\)に対して、\(1,2,\cdots,12\)の中で\(12\)と互いに素であるものは、\(1,5,7,11\)の\(4\)個あります。
よって\(\phi(12)=4\)です。

\(\phi\)関数の値を求める

これまでの具体例をもとに一般化していきます。

\(n=p\)が素数の場合

正の整数\(n=p\)に対して、\(1,2,\cdots,p-1\)と互いに素であるものは素数なので、\(\phi(p)=p-1\)になります。

Ｐｏｉｎｔ

正の整数\(p\)が素数のとき、\(\phi(p)=p-1\)

\(n=p^k\)のとき（\(p\)は素数）

次に素数の累乗について考えます。

上の例では値が小さすぎるので\(n=2^4=16\)について考えます。

\(1,2,\cdots,16\)の中で\(16\)と互いに素であるものは、\(1,3,5,7,9,11,13,15\)の\(8\)個あります。

よって\(\phi(16)=8\)です。

\(16\)と互いに素でない数は、\(2\)の倍数です。

\(1,2,\cdots,16\)の中で、\(2\)の倍数は、\(2\times1,2\times2,\cdots,2\times8\)と\(8\)個あります。

同様に、\(1,2,\cdots,p^k\)の中で\(p\)と互いに素でないものは、\(p\)の倍数で\(p\times1,p\times2,\cdots,p\times p^{k-1}\)の\(p^{k-1}\)個あります。

よって\(\phi(p^k)=p^k-p^{k-1}\)になります。

Ｐｏｉｎｔ

正の整数\(p\)が素数のとき、\(\phi(p^k)=p^k-p^{k-1}\)

\(n=ab\)のとき（\(a,b\)は互いに素）

次に合成数について考えます。

\(n=6\times7=42\)について、\(\phi(42)\)を次のように数えてみます。

\(1\)\(2\)\(3\)\(4\)\(5\)\(6\)
\(7\)\(8\)\(9\)\(10\)\(11\)\(12\)
\(13\)\(14\)\(15\)\(16\)\(17\)\(18\)
\(19\)\(20\)\(21\)\(22\)\(23\)\(24\)
\(25\)\(26\)\(27\)\(28\)\(29\)\(30\)
\(31\)\(32\)\(33\)\(34\)\(35\)\(36\)
\(37\)\(38\)\(39\)\(40\)\(41\)\(42\)

表を横方向に見ていくと、\(6\)で割った余りが\(1,2,3,4,5,0\)である数が\(1\)つずつ含まれています。

これらのうち、余りが\(2,3,4,0\)である数は\(42\)と共通の約数を持ちます。

\(42\)と互いに素であるのは、余りが\(1,5\)の数だけになり、それぞれの行に\(\phi(6)=2\)個ずつあります。

表を縦方向に見ていくと、行数は\(7\)行です。\(7\)は\(6\)と互いに素なので、縦方向に並んだ数を\(7\)で割った余りはすべて異なり、\(7\)と互いに素でないものが\(1\)つずつ含まれています。

よって、\(7\)と互いに素でないものの個数は、それぞれの列に\(\phi(7)=6\)個ずつあります。

\(42\)と互いに素でないものの個数は、横方向に\(2\)個ずつ、縦方向に\(6\)個ずつあり、全部で\(2\times6=12\)個あります。

同様に考えると、\(a,b\)が互いに素であるとき、\(n=ab\)について、\(\phi(n)=\phi(ab)=\phi(a)\phi(b)\)であることが示せます。

Ｐｏｉｎｔ

\(a,b\)が互いに素であるとき、\(n=ab\)について、\(\phi(n)=\phi(ab)=\phi(a)\phi(b)\)

一般化する

\(n\)が\(n={p_1}^{e_1}{p_2}^{e_2}\cdots{p_k}^{e_k}\)（\(p_1,p_2.\cdots,p_k\)は素数）と素因数分解できるとき、

\[ \begin{eqnarray} \phi(n) &=& \phi \left({p_1}^{e_1}{p_2}^{e_2}\cdots{p_k}^{e_k}\right) \\
&=& \phi\left({p_1}^{e_1}\right)\phi\left({p_2}^{e_2}\right)\cdots\phi\left({p_k}^{e_k}\right) \\
&=& \left({p_1}^{e_1}-{p_1}^{e_1-1}\right) \left({p_2}^{e_2}-{p_2}^{e_2-1}\right) \cdots \left({p_k}^{e_k}-{p_k}^{e_k-1}\right) \\
&=& {p_1}^{e_1}\left(1- \frac{1}{p_1}\right) {p_2}^{e_2}\left(1- \frac{1}{p_2}\right)  \cdots {p_k}^{e_k}\left(1- \frac{1}{p_k}\right) \\
&=& {p_1}^{e_1}{p_2}^{e_2}\cdots{p_k}^{e_k} \left(1-\frac{1}{p_1}\right) \left(1-\frac{1}{p_2}\right) \cdots \left(1-\frac{1}{p_k}\right)  \\
&=& n \left(1-\frac{1}{p_1}\right) \left(1-\frac{1}{p_2}\right) \cdots \left(1-\frac{1}{p_k}\right) \end{eqnarray}\]

で求めることができます。

Ｐｏｉｎｔ

\(n={p_1}^{e_1}{p_2}^{e_2}\cdots{p_k}^{e_k}\)（\({p_1},{p_2},\cdots,{p_k}\)は素数）とするとき、
\[\phi(n)=n \left(1-\frac{1}{p_1}\right) \left(1-\frac{1}{p_2}\right) \cdots \left(1-\frac{1}{p_n}\right) \]

オイラーの定理

証明は割愛しますが、\(\phi\)関数について、次の関係が成り立つことが知られています。

これをオイラーの定理といいます。

Ｐｏｉｎｔ

\(n\)を正の整数とする。\(n,a\)を互いに素である正の整数とするとき、
\[ a^{\phi(n)} \equiv 1 (\bmod n)\]

フェルマーの小定理

オイラーの定理において、特に\(n=p\)（\(p\)は素数）とすると次の定理になります。

Ｐｏｉｎｔ

\(p\)を素数、\(a,p\)を互いに素である正の整数とするとき、
\[ a^{p-1} \equiv 1 (\bmod p)\]

以前の記事のリンクを貼っておきます。

ようやく話の流れがつかめてきたような気がします・・・フェルマーの小定理は、次に取り上げるモジュラ逆数を求めるのに使えます。

モジュラ逆数とは

例として、\(2x \equiv 1 \bmod 5 \)となる整数\(x\)を求めます。

単純な\(2x=1\)となる整数は存在しませんが、\(5\)で割った余りのように、剰余を用いて考えると整数解が存在します。

\(2 \times 3 \equiv 6 \equiv 1 \bmod 5\)が成り立ちます。

よって、\( x \equiv 3 \bmod 5\)になります。

このように、\(5\)で割った余りについて（\(5\)を法とするとき）\(2\)にある整数\(x\)をかけて単位元\(1\)になるような\(x\)を、\(2\)のモジュラ逆数といいます。

同様に、\(n\)を法とするとき\(a\)にある整数\(x\)をかけて単位元\(1\)になるような\(x\)を、\(a\)のモジュラ逆数といい、\(x \equiv a^{-1} \bmod n\)と表します。

モジュラ逆数を求める（１）フェルマーの小定理を用いる

素数\(p\)を法とするとき、\(a^{p-1} \equiv aa^{p-2} \equiv 1 \bmod p\)が成り立ちます。

これにより\(a\)のモジュラ逆数は、\(a^{p-2} \bmod p\)になります。

\(a^{p-2} \bmod p\)を求めるのに\(p-3\)回の掛け算をしてもよいのですが、工夫すると計算量を減らすことができます。

例えば、法\(19\)において\(8\)の逆元を求めるとき、\(8^{19-2} \equiv 8^{17} \bmod 19\)を次のように求めることができます。

\(17\)を\(2\)進法で考えると、\(17=16+1\)より\((10001)_2\)です。

\(8^2 \equiv 64 \equiv 7 \bmod 19\)

\(8^4 \equiv (8^2)^2 \equiv 7^2 \equiv 49 \equiv 11 \bmod 19\)

\(8^8 \equiv (8^4)^2 \equiv {11}^2 \equiv 121 \equiv 7 \bmod 19\)

\(8^{16} \equiv (8^8)^2 \equiv 7^2 \equiv 49 \equiv 11 \bmod 19\)

となるので

\(8^{17} \equiv 8^{16+1} \equiv 8^{16} \times 8^1 \equiv 11 \times 8 \equiv 88 \equiv 12 \bmod 19\)

により、\(19\)を法とするとき、\(8\)のモジュラ逆数が\(12\)であることが求められます。

モジュラ逆数になっていることを確認してみます。

\(8\times12 \equiv 96 \equiv 1 \bmod 19\)となり、\(8\)と掛け算したときに、\(19\)で割った余りが\(1\)になることから、モジュラ逆数であることが確かめられます。

この方法では、\(p\)の値が大きくなっても計算回数は\(\log_{2}p\)回で済みます。

毎度のPythonで書いてみます。

def inverse( a, p ):
  e = p - 2
  k = a
  result = 1
  while e > 0:
    bit = e & 1
    if bit == 1:
      result = result*k % p
    k = k*k % p
    e = e >> 1
  return result

if __name__ == '__main__':
  for i in range(1,19):
    print( '{0}^-1 ≡ {1} mod 19'.format( i, inverse( i, 19 ) ) )

ビット演算をしていてわかりにくい点がありますが、上の操作と同じことをしています。

試しに\(19\)を法とするとき、\(1\)から\(18\)についてそれぞれのモジュラ逆数を求めます。実行結果は次になります。

1^-1 ≡ 1 mod 19
2^-1 ≡ 10 mod 19
3^-1 ≡ 13 mod 19
4^-1 ≡ 5 mod 19
5^-1 ≡ 4 mod 19
6^-1 ≡ 16 mod 19
7^-1 ≡ 11 mod 19
8^-1 ≡ 12 mod 19
9^-1 ≡ 17 mod 19
10^-1 ≡ 2 mod 19
11^-1 ≡ 7 mod 19
12^-1 ≡ 8 mod 19
13^-1 ≡ 3 mod 19
14^-1 ≡ 15 mod 19
15^-1 ≡ 14 mod 19
16^-1 ≡ 6 mod 19
17^-1 ≡ 9 mod 19
18^-1 ≡ 18 mod 19

モジュラ逆数を求める（２）拡張ユークリッドの互除法を用いる

今回のテーマから若干外れますが、拡張ユークリッドの互除法を用いた方法も載せておきます。

\(ax \equiv 1 \bmod n\)の解\(x\)を求めます。

この式では、\(ax\)に\(n\)の倍数をたしたときに\(1\)になることを示しています。

そのことから、\(ax+ny=1\)（\(y\)は整数）と表せます。

具体的な数値を使って書いてみます。

\(19\)を法とするとき\(8\)のモジュラ逆数\(x\)は、\(8x \equiv 1 \bmod 19\)の解\(x\)になります。

このような\(x\)は、不定方程式\(8x+19y=1\)の整数解になります。

この解法は以前の記事に書いていたのでリンクを貼っておきます。

拡張ユークリッドの互除法のプログラムは、RSA暗号ですでに書いていました (・_・;)

拡張ユークリッドの互除法の部分を少し手直ししたプログラムを載せておきます。 

def inverse( a, m ):
  b = m
  x, y = 1, 0
  while b:
    q = a // b
    a, b = b, a-q*b
    x, y = y, x-q*y
  return x if x>0 else x+m


if __name__ == '__main__':
  for i in range(1,19):
    print( '{0}^-1 ≡ {1} mod 19'.format( i, inverse( i, 19 ) ) )

フェルマーの小定理を使った場合と同じ結果になりますが、結果を載せておきます。 

1^-1 ≡ 1 mod 19
2^-1 ≡ 10 mod 19
3^-1 ≡ 13 mod 19
4^-1 ≡ 5 mod 19
5^-1 ≡ 4 mod 19
6^-1 ≡ 16 mod 19
7^-1 ≡ 11 mod 19
8^-1 ≡ 12 mod 19
9^-1 ≡ 17 mod 19
10^-1 ≡ 2 mod 19
11^-1 ≡ 7 mod 19
12^-1 ≡ 8 mod 19
13^-1 ≡ 3 mod 19
14^-1 ≡ 15 mod 19
15^-1 ≡ 14 mod 19
16^-1 ≡ 6 mod 19
17^-1 ≡ 9 mod 19
18^-1 ≡ 18 mod 19

今回はこれでおしまいにします。それではまた。

Posted by 春日井 優