アルゴリズム論特論（塩田）　2020年度教材 第7回

  • 出席代わりに、塩田 ( shiota＠is.kochi-u.ac.jp ) 宛てにメールを出してください。
  • 件名は「アルゴリズム論特論第７回出席」とでもしてください。 $\newcommand{\ol}[1]{\overline{#1}}$ $\newcommand{\znz}[1]{\mathbb{Z}/#1 \mathbb{Z}}$ $\newcommand{\znzc}[1]{(\mathbb{Z}/#1 \mathbb{Z})^{\times}}$ $\newcommand{\inv}[1]{\displaystyle{\frac{1}{#1}}}$

今日のテーマ

  • 剰余類
  • オイラーの定理
　今日は、法演算のもう一つの表記法として「剰余類」というものを学びます。 同じことを表しているのならわざわざ別の表記法を作らなくてもいいじゃないかと思うかもしれませんが、 表記法の違いがものの見方を変えて、それに従って新たな思考ができたりするのです。 フェルマの小定理の発展形であるオイラーの定理も、そういう思考の上で発見されたものです。

1. 剰余類

　まずは定義から。
Def.1　法 $n$ の合同関係により $a$ の属する同値類を
$\bar a$
と表して、$a$ の属する「法 $n$ の 剰余類」と呼ぶ。 その実体は集合であって、
$\bar a=\{\,$ 法 $n$ で $a$ と合同な整数たち$\,\}$
である。
Rem.2　$a \equiv b \pmod n$ $\ \Leftrightarrow\ $ $\bar a = \bar b$
※　前々回「$\equiv$ はイコール感覚で使える」というフレーズが出てきましたが、 本当にイコールにしてしまおう、という表記法です。
Ex.3　$n=7$, $a=2$ のとき、集合として
$\ol{2}=\{\,\cdots,\,-12,\,-5,\,2,\,9,\,\cdots\,\}$
であり、
$\cdots=\ol{(-12)}=\ol{(-5)}=\ol{2}=\ol{9}=\cdots$
です。
Def.4　法 $n$ の剰余類全ての集合を $\znz{n}$ と表し、 ゼット・オーバー $n$ ゼットと読む。
$\znz{n} = \{\,\ol{0},\,\ol{1},\,\cdots,\,\ol{(n-1)}\,\}$
であり、$\znz{n}$ には $n$ 個の要素がある。
　法演算を剰余類で表現すると
Th.5　$\znz{n}$ には次のようにして加減乗除の四則演算が定義できる。 \begin{align} \bar a + \bar b &= \ol{(a+b)} \\ \bar a - \bar b &= \ol{(a-b)} \\ \bar a \times \bar b &= \ol{(a \times b)} \\ \bar a \div \bar b &= \ol{\left(a \times \inv{b}\right)} \\ \end{align} ただし除算においては、除数 $b$ は $\gcd(b,n) = 1$ を満たすものに限り、$\inv{b}$ は法 $n$ での $b$ の逆数を表す。
　うかっと見ると意味が分かりませんが、 左辺は剰余類同士の演算で、それを右辺の式で定義しよう、という式です。

　例えば $n=7$ のとき、
$\ol{2} = \ol{9}$, $\quad\ol{3} = \ol{10}$
なので
$\ol{2} \times \ol{3} = \ol{(2 \times 3)}$
でもあるし、
$\ol{2} \times \ol{3} = \ol{9} \times \ol{10} = \ol{(9 \times 10)}$
でもあるのですが、第5回 Th.6 から
$\ol{(2 \times 3)} = \ol{(9 \times 10)}$
が保証されているので矛盾が生じない訳です（ well-defined, と言います）。 除算も同様に第6回 Th.5 から矛盾が生じません。

2. 既約剰余類

　法と互いに素な整数の属する剰余類を特別扱いします。
Def.6　$\gcd(b,n) = 1$ を満たす $b$ の属する剰余類を「法 $n$ の既約剰余類」と呼ぶ。 それらすべての集合を $\znzc{n}$ と表し、 ゼット・オーバー $n$ ゼット・クロスと読む。
　教科書によっては $(\znz{n})^{\ast}$ と書いていることもありますが、同じものです。
Ex.7　$\znzc{2}=\{\,\ol{1}\,\}$, $\quad\znzc{3}=\{\,\ol{1},\ol{2}\,\}$, $\quad\znzc{4}=\{\,\ol{1},\ol{3}\,\}$.
やってみよう　$n=5,6,7,10$ に対しても $\znzc{n}$ の要素を書き出してみましょう。
Rem.8　素数 $p$ が法ならば、
$\znzc{p}=\{\,\ol{1},\ol{2},\cdots,\ol{(p-1)}\,\}$
　ここから $\ol{\phantom{e}}$ を付けずに剰余類を書くことがありますが、 例えば $a = \ol{2}$ というように書いてあると思ってください。
Th.9
  1. $a \in \znzc{n}$ $\Leftrightarrow$ $\inv{a}$ が存在する
  2. $a$, $b \in \znzc{n}$ ならば $ab \in \znzc{n}$
  3. $a \in \znzc{n}$ ならば、
    $a$ 倍写像 : $x \mapsto ax$
    は　$\znz{n}$ から $\znz{n}$ 自身への全単射（一対一写像）であり、 また $\znzc{n}$ から $\znzc{n}$ 自身への全単射でもある。
証明　(1) は第6回の Th.6。
  1. $a$, $b \in \znzc{n}$ ならば (1) より $\inv{a}$, $\inv{b}$ が存在するので、 $\inv{a} \times \inv{b}$ は $ab$ の逆数となり $ab \in \znzc{n}$.
  2. $\inv{a}$ が存在するので $a$ 倍写像は単射であり、従って全射にもなる。(証明終)
※　代数学用語で
  • $\znz{n}$ は環を成す
  • $\znzc{n}$ は乗法群を成す
と言います。

3. オイラーの定理

Def.10（オイラーのトーシャント関数）　$\znzc{n}$ の要素数を $\varphi(n)$ と表す。 $\varphi$ をオイラーのトーシャント関数（または簡単にオイラー関数）と呼ぶ。
　言い換えれば、$1$, $\cdots$, $n$ の中で $n$ と互いに素な整数の個数が $\varphi(n)$ です。 Ex.7 より
Ex.11　$\varphi(2)=1$, $\varphi(3)=2$, $\varphi(4)=2$, $\varphi(5)=4$, $\varphi(6)=2$, $\varphi(7)=6$, $\varphi(10)=4$.
　また Rem.8 より
Rem.12　$p$ が素数ならば $\varphi(p)=p-1$.
　なぜ $\varphi$ をオイラー関数と呼ぶかと言うと、次の定理をオイラー先生が発見したからです。
Th.13（オイラーの定理）　$a \in \znzc{n}\quad$ならば$\quad a^{\varphi(n)}=\ol{1}$.
　同じことを合同式で書けば
Th.13'（オイラーの定理）　$\gcd(a,n)=1\quad$ならば$\quad a^{\varphi(n)} \equiv 1 \pmod{n}$.
証明　$m=\varphi(n)$ とおき、$\znzc{n}$ の $m$ 個の要素に
$x_1$, $x_2$, $\cdots$, $x_m$
と名前を付けます。Th.9 (3) から $a$ 倍写像は全単射ですから
$ax_1$, $ax_2$, $\cdots$, $ax_m$
も $\znzc{n}$ の $m$ 個の要素になります。従ってそれらの積は同じ値になり、 \begin{align} x_1 \times x_2 \times \cdots \times x_m &= (ax_1) \times (ax_2) \times \cdots \times (ax_m) \\ &= a^m \times (x_1 \times x_2 \times \cdots \times x_m) \\ \end{align} $ (x_1 \times x_2 \times \cdots \times x_m)$ は $\znzc{n}$ の要素ですから両辺を割ることができて
$\ol{1}=a^m=a^{\varphi(n)}$.
(証明終)
Ex.14　$n=24$, $a=\ol{5}$ のとき、
$\znzc{24}=\{\,\ol{1},\ol{5},\ol{7},\ol{11},\ol{13},\ol{17},\ol{19},\ol{23}\,\}$, $\quad\varphi(24)=8$
で、
$\ol{5}\times\ol{1}=\ol{5}$, $\quad\ol{5}\times\ol{5}=\ol{1}$, $\quad\ol{5}\times\ol{7}=\ol{11}$, $\quad\ol{5}\times\ol{11}=\ol{7}$,
$\ol{5}\times\ol{13}=\ol{17}$, $\quad\ol{5}\times\ol{17}=\ol{13}$, $\quad\ol{5}\times\ol{19}=\ol{23}$, $\quad\ol{5}\times\ol{23}=\ol{19}$
辺々掛けると
$\ol{5}^8 \times(\ol{1}\times\ol{5}\times\ol{7}\times\ol{11}\times\ol{13}\times\ol{17}\times\ol{19}\times\ol{23})$
　$=\ol{5}\times\ol{1}\times\ol{11}\times\ol{7}\times\ol{17}\times\ol{13}\times\ol{23}\times\ol{19}$
　$=\ol{1}\times\ol{5}\times\ol{7}\times\ol{11}\times\ol{13}\times\ol{17}\times\ol{19}\times\ol{23}$
よって
$\ol{5}^8 = \ol{1}$
Cor.15（フェルマの小定理の別証明）　特に $p$ が素数ならば $\varphi(p)=p-1$ ゆえ、
$a$ が $p$ で割り切れなければ$\quad a^{p-1} \equiv 1 \pmod{p}$.
　オイラーの定理で法を素数に限定した version がフェルマの小定理、という訳です。

4. RSA暗号設計のための補題

Lemma 16　$p$ を素数とし、$p-1$ と互いに素な 2 つの自然数 $e$, $d$ が
$ed \equiv 1 \pmod{(p-1)}$
を満たすとする。このとき任意の整数 $x$ について
誤り：　$x^{ed} \equiv 1 \pmod{p}$
訂正：　$x^{ed} \equiv x \pmod{p}$
が成り立つ。
証明　以下、$\equiv$ は法 $p$ の合同を表すとします。
  1. $x \equiv 0$ のとき
    $x^{ed} \equiv 0^{ed} \equiv 0 \equiv x$
    となって成り立ちます。
  2. $x \not\equiv 0$ のとき
    まずフェルマの小定理より
    $x^{p-1} \equiv 1$.
    ここで条件より
    $ed=1 + k(p-1)$
    と置けますので、
    $x^{ed} \equiv x^{1 + k(p-1)} \equiv x \times (x^{p-1})^k \equiv x \times 1^k \equiv x$.
(証明終)
Prop.17　Lemma 16 の状況下で次のような暗号システムが設計できる。
  • 平文(ひらぶん)集合は $P=\{\,0,1,\cdots,p-1\,\}$
  • 暗号文集合も $C=\{\,0,1,\cdots,p-1\,\}$
  • 暗号化関数 $E:P\rightarrow C$ は $E(x)=x^e \,\%\, p$
  • 復号関数　 $D:C\rightarrow P$ は $D(y)=y^d \,\%\, p$
  • 暗号化鍵は $(e,p)$
  • 復号鍵は　 $(d,p)$
ただし、 $\%$ は Python 風に非負の最小剰余を返すとする。
証明　Lemma 16 より $D(E(x)) = x^{ed} \,\%\, p = x$ となるので。(証明終)
Ex.18　$p=307$, $e=37$, $d=91$ とします。
$ed = 3367 =306 \times 11 + 1 \equiv 1 \pmod{306}$
ですから Lemma 16 の仮定が満たされています。 平文 $x=2$ を暗号化すると
$y=E(x) = 2^{37} \,\%\, 307 = 163$.
これを復号すると
$D(y) = 163^{91} \,\%\, 307 = 2$
となり $x$ に戻っています。
　もちろんこんな小さな数では全検索で復号鍵の $d$ を見つけられてしまいますので暗号にはなりませんが、 大きな数を用いるとどうでしょうか。
宿題　$p$, $e$, $d$ をもっと巨大にしたとき、Prop.17 の暗号は「公開鍵暗号」になるでしょうか。 提出はしなくて良いですが、次回までに考えておいてください。

まとめ

  • 集合をひとつの要素と考える「剰余類」の考え方を導入した。
  • フェルマの小定理の一般化であるオイラーの定理を導いた。
  • 法演算のべき乗剰余を応用した暗号を提案した。

戻る