MathJax初導入ということで,離散対数問題を modmod 演算だけでなく,
演算を一般化して考えてみましょう.
まずは,集合と演算子の組 (G,⊙) が
群になす条件について復習しましょう.
TEX の数式が使えるからうれしい.
なぜ, G なのか?
群を英語で言うとGroupで,
頭文字をとって G としているからです.
- 全ての x,y∈G に対して, x⊙y∈G .
つまり,演算結果も集合 G の中に入っているということです. - 全ての x,y∈G に対して, (x⊙y)⊙z=x⊙(y⊙z).
いわゆる,結合法則ですね.
ここまで満たせば半群になりますが,
群をなすというためにはさらに二つの条件が必要です.
- 全ての x∈G に対して x⊙e=e⊙x=x となるような
e∈G がただ一つ存在する.
つまり,単位元が存在するということで,演算を施しても自分自身であるということですね. - 全ての x∈G に対して x⊙y=y⊙x=e となるような
y∈G がただ一つ存在する.
つまり,逆元が存在するということで,この y を y=x−1 と書きます.
足し算だったら, y=−x と書いたほうがわかりやすいでしょう.
集合 G の要素数 |G| を
群 (G,⊙) の位数といいます.
位数が有限の群を有限群といいます.
このとき,次の定理が知られています.
これはフェルマーの定理を一般化したものです.
定理 有限群 (G,⊙) において,任意の a∈G に対して a⊙a⊙⋯⊙a⏟|G|=e である.
この定理の意味は,どんな a を G の要素数の回数だけ演算すれば,
必ず単位元 e に戻ってくるということです.
では,例を見てみましょう.
5で割った余りの世界(つまり集合 Z5 )で考えてみましょう.
(Z5,+) の単位元は0ですね(小学生でもわかるはずです).
5回同じ数で足し算して,その答えを5で割って,余りを計算してみましょう.
0+0+0+0+0=0≡0(mod5)
1+1+1+1+1=5≡0(mod5)
2+2+2+2+2=10≡0(mod5)
3+3+3+3+3=15≡0(mod5)
4+4+4+4+4=20≡0(mod5)
ちゃんと0になったので,フェルマーの定理が正しいことが確かめられました.
めでたしめでたし.