ここのタイトルは普段見慣れない言葉の組み合わせですが, 実は数学の基本的な言葉なのです. しばらく退屈な話が続きますが, ご勘弁.
離散対数問題とDiffie-Hellmann問題で出てきた「○○を△で割った余り」というものは今後よくでてきます. 余りというのは最大値が決まっているのでコンピュータで扱いやすい数値なので記号を導入しましょう.
n を1より大きいを整数とし固定します. 集合 {0, 1, ..., n - 1} を Z/nZ と書き, 整数 x を n で割った余りを x~ とします.
たとえば n = 5 とすると Z/5Z = { 0, 1, 2, 3, 4 }. 7~ = 2. 3~ = 3. また勝手な a について (a~)~ = a~.
実はクイズを解くとき, 無意識にちょっとした論理の飛躍がありました.
それは『「a を n で割った余り」と「b を n で割った余り」を掛けたものを n で割った余り』は a * b を n で割った余りに等しい.
一見, ???ですが何のことは無い, クイズの答えで 2 を掛けるごとに 7 で割ってましたが, それはまとめて掛けたものを 7 で割ったものと同じですよ, ということを言っているだけです. たとえば (16 * 2) mod 7 = 32 mod 7 = 4 は 16 mod 7 = 2 に 2 を掛けて 4 としたものに等しい.
当たり前のことですが, この性質が無いとクイズは解けません(全部掛けてからでないと割り算できなくなってしまう).
この性質を記号で書くと (a~ * b~)~ = (a * b)~ となります.
足し算についても (a~ + b~)~ = (a + b)~ が成り立ちます. もう, 常に計算結果は余りで考えることにし, ~を省略すると 3 * 2 = 1. 2 + 3 = 0 などとかけます. (1 + 2) * 4 = 2 など括弧も自然に使えます.
要するに Z/nZ の中で日常の普通の足し算や掛け算と極めて似た性質を持つ足し算や掛け算を導入できました.
このような普通の感覚に近い足し算や掛け算ができる集合を数学では環(ring)といいます.
Z/5Z の中では 3 * 2 = 1 でした. 普通 a * b = 1 となる b を a の逆数(1/a)といいますね. その感覚を強引に持ち込むと, 1 / 3 = 2 という式を認めてもよいことになります. Z/5Z の中で 3 で割るということは 2 を掛けるに等しいということです.
なんのことかさっぱり, かもしれませんが, 1 / 3 = 2 を認めるなら両辺に 2 を掛けてみると 2 / 3 = 4 を認めるということです. これは 2 = 4 * 3 という意味で, 4 * 3 = 12 = 2 なのであってます. つまり, どんな式変形をしても破綻がでてこない(どこかで 1 = 4 とかにならない)のです.
Z/5Z の掛け算を作ってみると次のようになりました.
| Z/5Z の掛け算の表 | |||||
|---|---|---|---|---|---|
| × | 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 |
| 2 | 0 | 2 | 4 | 1 | 3 |
| 3 | 0 | 3 | 1 | 4 | 2 |
| 4 | 0 | 4 | 3 | 2 | 1 |
これを見ると 0 以外については 1 / 1 = 1, 1 / 2 = 3, 1 / 3 = 2, 1 / 4 = 4 と思えば Z/5Z の中で自由に割り算もできるわけです. こういう環であって更に割り算もできる集合を体(field)といいます.
環だけと体じゃない集合ももちろんあります. Z/5Z ではなく Z/4Z を考えてみます. 2 * 1 = 2, 2 * 2 = 0, 2 * 3 = 2 と 2 を掛けて 1 になる数が存在しません. つまり逆数を作れないので割り算ができません. よって体ではありません.
いいかげん, 無味乾燥な話で疲れてきましたがもう一つだけ. Z/5Z の掛け算の表を見ると 0 を除くと掛けた結果はどれも 0 ではありません. Z/5Z から 0 を除いた集合を (Z/5Z)* とかくことにすると, これは掛け算と割り算だけができる世界です. 足し算は 3 + 2 = 0 と 0 ができてしまうので含めません. こういう集合を群(group)といいます.
次回, この群という観点から離散対数問題を見直します.