はじめに
4月からの勉強で知識や技術がわずかながら身に付いてきた(気がする)ので、NTRUEncryptをRustで実装してみたいと思い立ちました。基本的な数学は学部や社会人時代に学習していたのですが、初心に帰って基本ルールの復習だ！ということで代数学を復習していきます。なおあくまで個人的な備忘録なので、全ての要素について詳しい定義や説明は書かないようにします。
代数系
算法には演算(内算法)と作用(外算法)があります。以下では入力xとyにある算法を適用して出力zを得ることを
(x, y) → zと書きます。
演算はx, y, zが同一の集合に所属する場合の算法です。具体例には加法、乗法、除法、指数計算などがあります。
1 (自然数) + 9 (自然数) = 10 (自然数)
3/4 (有理数) * 2/5 (有理数) = 3/10 (有理数)
作用はx, zが同一の集合に所属し、かつyがそれとは別の集合に所属する場合の算法です。具体例にはベクトル空間に対する線形変換の作用がパッと思いつきましたが、他には考え付きませんでした。。。
内算法に定義される性質には結合、可換が挙げられます。
結合は (a + b) + c = a + (b + c) の様に結合法則が成り立つことを表す性質で、
可換は a + b = b + a の様に順序を入れ替えることができることを表す性質です。
もちろん両方が成り立つ場合(複素数に対する加法、乗法など)もありますが、どちらも成り立たない場合(自然数に対する、割り算の余りを求める演算)やどちらか一方のみが成り立つ場合(n次実行列の積)もあります。
加えて単位元と逆元についても導入します。(元は集合の構成要素のこと)
単位元は特定の演算において、何も変えない元のことです。
例えば、複素数の加法における0、乗法における1などが例に挙げられます。
(6 + 7i) + 0 = 6 + 7i
つまり、単位元は演算と集合に対して定義されます。
逆元はある元に対して特定の演算を行うと単位元になる元のことです。
例えば、整数 9 に対して、その加法の逆元は -9 になります。
9 + (-9) = 0 (0は整数加法の単位元)
群、環
いよいよ本題に入れました。まずは大まかな説明ですが、群と環は上で述べた代数系のうち、算法として演算のみを持つ代表例です。つまり、それぞれを考える際には集合と定義される演算を意識すると全体像を把握しやすくなると思います。(個人の感想です)
群(E, *)は、以下の4条件を満たす代数系です。
1. 集合Eの任意の元a, bに対して演算a*bもEに属する。
2. 集合Eの任意の元a, b, cに対して結合法則が成り立つ
3. 集合Eの任意の元aに対して単位元が存在する
4. 集合Eの任意の元aに対して逆元が存在する
結合法則、単位元、逆元については上の通りです。1.については具体例と共に考えてみましょう。
例えば、集合を整数、演算を加法と考えると、条件1.を満たすと言えます。整数どうしを足し引きしても整数のままです。
ここで、条件1.と演算の定義を見比べると似ていますね。ただし、演算であることだけでは群の閉性の保証にはなりません。以下に反例を挙げます。
まず、集合E ＝{0, 1}と算法⊕を定義します。この算法は以下の様に定義されます。
0 ⊕ 0 = 0
0 ⊕ 1 = 1
1 ⊕ 0 = 1
1 ⊕ 1 = 2
すると、Eに属する任意の元に対して必ず算法⊕が定義されているので、⊕は演算になります。
一方で1 ⊕ 1 = 2 で、2は集合Eに属していないため、閉性は成り立ちません。
また、群の算法が可換であるとき、その群を可換群と呼びます。
次に環について説明します。
環(E, +, *)は二つの演算を持つ代数系で、以下の条件で環と呼ばれます。
1. 一つの演算+に関して、集合の要素が可換群を形成する。((E, *)が可換群をなす)
2. もう一方の演算*に関して、集合の要素が閉性と結合法則を満たす。((E, *)が半群をなす)
3. 集合Eに属する任意の元a, b, cに対して、以下が成り立つ。(分配法則)
a * (b + c) = (a * b) + (a * c)
(a + b) * c = (a * c) + (b * c)
特に、算法*が可換な環を可換環と呼ぶ。
(注：環の定義として演算*の単位元の存在を要請しているかどうかは文献によるので、複数の教科書を使う際には文脈に気を付けましょう。)
おわりに
とりあえず環まで書いたのでここまでにします。(体はどうなってんだ体は！)
余談ですが個人的には内算法、外算法と呼ぶ方が入力と出力の関係性をよく表している様に感じるので好きです。(ただこれらは環境によっては変換が一発で出てこないことがあるんですよね。。。)
次回はNTRU問題とそれに基づく暗号化方式NTRUEncryptについてまとめようと思います。
参考文献
1. 国廣昇, 東京大学工学教程 基礎系数学 代数学, 丸善出版
2. 青野良範, 安田雅哉, 格子暗号解読のための数学的基礎, 近代科学社
