アルゴリズム論特論（塩田） 2020年度教材 第5回
- 出席代わりに、塩田 ( shiota＠is.kochi-u.ac.jp ) 宛てにメールを出してください。
- 件名は「アルゴリズム論特論第５回出席」とでもしてください。
今日のテーマ
RSA 暗号をはじめとする多くの公開鍵暗号系は、
整数の法演算を用いて設計されています。
今日はその定義と、基本的な性質を勉強します。
1. 合同式
Def.1 ( 合同式 )
- 自然数 $n$ をひとつ固定し、これを「法 ( modulus )」と呼ぶ。
- $a-b$ が $n$ で割り切れるとき、
$a \equiv b \pmod n$
と表し、「 $a$ 合同 $b$ モッド $n$ 」と読む。
また、「 $a$ は $n$ を法として $b$ と合同である」と言う。
Rem.2 次は同じことの言い換えである：
- (1) $a \equiv b \pmod n$
- (2) $a-b$ が $n$ で割り切れる
- (3) $a-b$ は $n$ の
□□ ... □□を埋めよ
- (4) $n$ は $a-b$ の
□□ ... □□を埋めよ
- (5) ( $a$ を $n$ で割った余り ) $=$ ( $b$ を $n$ で割った余り )
ただし (5) は理論上の話で、プログラミング言語の仕様によってはバグることがあるので注意してください。
Rem.3 $a\,\%\,n$ の符号は
- C 言語では $a$ の符号に同じ
- Python では $n$ の符号に同じ
例えば
$\newcommand\T{\Rule{0pt}{1em}{.3em}}
\begin{array}{|c|c|c|c|c|}
\hline & 2\ \%\ 5 & (-3)\ \%\ 5 & 2\ \%\ (-5)\ & (-3)\ \% (-5) \\\hline
\mbox{C} & 2 & -3 & 2 & -3 \\\hline
\mbox{Python} & 2 & 2 & -3 & -3 \\\hline
\end{array}$
すなわち、$a=2$, $b=-3$, $n=5$ のとき、理論上は $a\equiv b \pmod n$ ですが、
(a % n) == (b % n)
は Python では正しく True と判定されるのに対し、C 言語では False と判定されてバグの原因となります。
2. 法演算
Def.4 法 $n$ で合同な数を「同じ」と思って計算することを法演算と言う。
計算のテクニック
- $n$ の倍数は $0$ に置き換えてよい。
- 数を $n$ で割った余りに置き換えることで、扱う数を小さくする。
Ex.5 $\bmod 7$ で
\begin{align}
6\,! &\equiv 6 \times 5 \times 4 \times 3 \times 2 \times 1 \\
&\equiv (-1) \times (-2) \times (-3) \times 3 \times 2 \times 1 \\
&\equiv (-1) \times 6 \times 6 \\
&\equiv (-1) \times (-1) \times (-1) \equiv -1 \\
\\
3^6 & \equiv (3^2)^3 \equiv 9^3 \equiv 2^3 \equiv 8 \equiv 1 \\
\end{align}
法演算を使わなければ、$6\,!=720=7 \times 103 - 1$, $3^6=729=7 \times 104+1$ ですが、
$7$ で割った余りなら１桁の数だけで計算できる、という例です。
何故こんな計算をして良いか、という理由は、次の定理が成り立つからです：
Th.6 $\bmod n$ で
$a \equiv b\quad$ かつ $\quad c \equiv d$
であれば
(1)$\quad a+c \equiv b+d$
(2)$\quad a-c \equiv b-d$
(3)$\quad a \times c \equiv b \times d$
証明 (1), (2) 条件より $a-b$, $c-d$ が $n$ の倍数であるから、
$(a \pm c) - (b \pm d) = (a-b) \pm (c-d)$
は $n$ の倍数ゆえ。
(3) 同じく
$ac - bd = ac - bc + bc -bd =(a-b)c + b(c-d)$
は $n$ の倍数ゆえ。(証明終)
Cor.7 $a \equiv b \pmod n$ ならば、$\forall e \geqq 0$ について
$a^e \equiv b^e \pmod n$
※ $+$, $-$, $\times$, べき乗に関して $\equiv$ は「イコール感覚」で扱ってよい、ということです。
※ ただし、べき指数 $e$ は $n$ で割った余りに取り換えては
いけません。
3. 九去法
$\bmod 9$ の法演算を応用した検算法を紹介しましょう。
Ex.8 $367 \times 52 = 19084$ の検算をしてみましょう。
- 被乗数、乗数、答えのそれぞれの各桁の数字を足します。
- ただし、$9$ を超えているときは $9$ を引きます ( 九を取り去る )。
- 被乗数$\quad 367 \rightarrow 3+6+7 = (3+6)+7\rightarrow 7$
- 乗数 $\quad 52 \rightarrow 5+2=7$
- 答え $\quad 19084 \rightarrow 1+9+0+8+4=(1+8)+9+4\rightarrow 4$
- $7 \times 7$ でまた同じことをします。
- $7 \times 7 = 49 \rightarrow 4 + 9 \rightarrow 4$
- 答えの $4$ と一致したので一安心します。
原理 $\bmod 9$ では $10 \equiv 1$ なので、
Cor.7 から $\forall e \geqq 0$ について
$10^e \equiv 1$
が成り立ちます。従って
$367 = 3 \times 10^2 + 6 \times 10 + 7 \equiv 3 \times 1 + 6 \times 1 + 7 \equiv 3+6+7 = (3+6)+7 \equiv 7$
という計算ができ、
被乗数 $\times$ 乗数 $\equiv 7 \times 7 \equiv 4 \equiv$ 答え
のはず、ということです。
計算間違えは繰り上がりなどで $1$ とか $2$ とかずれていることが多いので、
電卓のない時代にはこの方法が結構重宝したらしいです。
4. フェルマの小定理
フェルマ先生は17世紀、フランスの法律家にして数学者です。
その頃は、法律家は論理的に話をしないといけないので数学が必須だったのですね。
パスカル先生やデカルト先生がお友達で、
歴史的難問のフェルマ予想（＝フェルマの大定理）を書き残したことで知られています。
今から述べるフェルマの小定理は RSA 暗号の動作原理でもあり、
数学全般の基礎となる非常に重要な定理です。
Th.9 ( フェルマの小定理 ) $p$ を素数とするとき、$\forall a$ について
$a^p \equiv a \pmod p$
今日は二項定理を用いた証明を与えましょう。
Lemma 10 ( 二項定理 )
$\displaystyle{(x+y)^p = \sum_{k=0}^p \left(\begin{array}{c}p \\ k\end{array}\right) \, x^{p-k}\, y^{k}}$
二項係数 $\displaystyle{\left(\begin{array}{c}p \\ k\end{array}\right)}$ は、
高校では ${}_p C_k$ と書いて、組合せの数と呼んでいたものです。
公式は書けますか？
二項係数 $\displaystyle{\left(\begin{array}{c}p \\ k\end{array}\right)}$ は、
高校では ${}_p C_k$ と書いて、組合せの数と呼んでいたものです。
公式は書けますか？
$\displaystyle{\left(\begin{array}{c}p \\ k\end{array}\right)=\frac{p\,!}{k\,!\,(p-k)\,!}}$
Lemma 11 $p$ を素数、$1 \leqq k \leqq p-1$ とするとき
$\left(\begin{array}{c}p \\ k\end{array}\right) \equiv 0 \pmod p$
証明 二項係数は整数であり、分母は素因子 $p$ を持たないので。(証明終)
Th.9 の証明 $p=2$ のときは $\pmod 2$ で
$a^2 \equiv \left\{
\begin{array}{ll}
0 & \quad \mbox{if }\ \ a \equiv 0 \pmod 2 \\
1 & \quad \mbox{if }\ \ a \equiv 1 \pmod 2 \\
\end{array}
\right.
$
ゆえ。
以下、$p \geqq 3$ とします。$a=0$ のときは
$a^p = 0^p = 0 \equiv a \pmod p$
で成り立ちます。
$a^p \equiv a \pmod p$
を仮定すると、
L'a 10 より
$\displaystyle{(a+1)^p = \sum_{k=0}^p \left(\begin{array}{c}p \\ k\end{array}\right) \, a^{p-k}\, 1^{k}}$
ですが、
L'a 11 より $k=0$, $k=p$ 以外の項は $p$ で割り切れるので
$\displaystyle{(a+1)^p \equiv \left(\begin{array}{c}p \\ 0\end{array}\right) \, a^p + \left(\begin{array}{c}p \\ p\end{array}\right)
\equiv a^p + 1 \equiv a + 1 \pmod p}$
となり、$a+1$ のときも正しくなります。
数学的帰納法により全ての $a \geqq 0$ について正しいことが言えました。
$a \lt 0$ のときは、$b = -a$ については
$b^p \equiv b \pmod p$
がわかりましたので
$a^p = (-b)^p = - b^p \equiv - b =a \pmod p$
(証明終)
Th.12 ( これもフェルマの小定理 ) $p$ が素数で、$a$ が $p$ で割り切れないとき、
$a^{p-1} \equiv 1 \pmod p$
証明 Th.9 より
$a^p-a = a(a^{p-1}-1)$
は $p$ の倍数であり、$a$ は $p$ と互いに素ですから $a^{p-1}-1$ が $p$ で割り切れます。(証明終)
5. 完全数
フェルマ先生は「完全数」の研究の中でこの定理を見つけました。
Def.13 自然数 $n$ が、$n$ より小さいすべての $n$ の約数の和と等しいとき、$n$ を「完全数」と呼ぶ。
Ex.14 $6$, $28$ はいずれも完全数である：
$6=1+2+3$,
$28=1+2+4+7+14$
$6$, $28$ の次に大きい完全数は $496$, $8128$, $33550336$, $\cdots$ と急激に大きくなっていきます。
$6$ は半年の月の数、$28$ は月の公転周期であり、完全数が宇宙の構造を決めているという発想がありました。
それは勘違いだったのかもしれませんが、科学を発展させる原動力は、案外そういう勘違いだったりします。
$p$ が素数で、$2^p -1$ も素数であるとき、$2^{p-1}(2^p-1)$ は完全数になります。
また逆に、偶数の完全数はこの形に書けることもわかっています。
しかし、奇数の完全数が存在するか否かは、紀元前からの問題ですが未だに解けていません。
まとめ
- 加法・減法・乗法・べき乗に関して、合同式はイコール感覚で使える。
- RSA 暗号の動作原理であるフェルマの小定理を学んだ。
自宅学習の例
- Ex.8 をまねて、$715 \times 46 = 32890$ の検算をする。
- $10\,!$ を $11$ で割った余りを、合同式を使って求める。( ウィルソンの定理 )
- 「10進数 $(x_n \cdots x_2x_1x_0)_{10}$ が $11$ で割り切れること
$\Leftrightarrow$ $x_0 - x_1 + x_2 - x_3 + \cdots$ が $11$ で割り切れること」を証明する。
戻る