暗号に必要な数学１#

使用する記号#

  • \(\mathbf{N}\): 自然数全体の集合

  • \(\mathbf{Z}\): 整数全体の集

  • \(\mathbf{R}\): 実数全体の集合

  • \(\mathbf{Z}_q\): 法を\(q\)とした整数全体の集合：\(\{0,1,...,q-1\}\)

群(group)#

\(G\)を集合として、その元\(f,g \in G\)に対して\(G\)の元\(f＊g\)を対応させる二項演算＊が定義されているとする。このとき、以下の全ての条件を満たす(\(G,＊\))の組を群という。

  1. 演算＊は任意の\(x,y,z \in G \)に対して\((x＊y)＊z = x＊(y＊z)\)を満たす (結合法則)

  2. 任意の\(x\in G\)に対して\(x＊e = e＊x = x\)を満たす\(e \in G\)が存在する (単位元の存在)

  3. 任意の\(x \in G\)に対してある\(y\in G\)が存在して\(x＊y=y＊x=e\)を満たす (逆元の存在)

ここで\(e\)は単位元、\(y\)は逆元と呼ばれる。演算＊は省略して\(x＊y\)を単に\(xy\)と書くときもある。
条件1のみを満たす組を半群、1,2を満たす組をモノイドとも呼ぶ。
また、以下の追加の性質も満たす群のことを可換群、またはアーベル群などと呼ぶ。

  1. 任意の\(x,y \in G\)に対して\(x＊y=y＊x\)を満たす (交換法則)

Note

二項演算＊は閉包則を満たさないといけないことに注意 (つまり任意の\(x,y\in G\)に対して\(x＊y \in G\))

群の例#

  • \((\mathbf{Z},+)\)

\(x,y,z\in \mathbf{Z}\)とする。

  1. \((x+y)+z = x+(y+z)\)は成り立つ (結合法則)

  2. \(x+0 = 0 + x = x\)が成り立つ (単位元の存在)

  3. \(x + (-x) = (-x) + x = 0\) が成り立つ (逆元の存在)

  4. \(x+y = y+x\) が成り立つ (交換法則)

以上より\((\mathbf{Z},+)\)は可換群である。

  • \((\mathbf{Z},×)\)

\(x,y,z\in \mathbf{Z}\)とする。

  1. \((x×y)×z = x×(y×z)\)は成り立つ (結合法則)

  2. \(x ×1 = 1×x = x \)が成り立つ (単位元の存在)

  3. 任意の\(x \in \mathbf{Z}\)に対して \( x×y = y ×x = 1\)となる\(y \in \mathbf{Z}\)は存在しない。

以上より\((\mathbf{Z},×)\) は群ではない。

Attention

\(x > 1\) のとき、\(\frac{1}{x} \notin \mathbf{Z}\)

巡回群#

\(G\)を群とする。\(G\)の元がただ一つの元\(a\)によって生成されるとき、\(G = \langle a\rangle\)と表し、この\(a\)を生成元と呼ぶ。(つまり、\(G\)の元が乗法,加法の場合それぞれ\(a^kn\),\(ka\)で表される。)このとき、\(G\)を巡回群と呼ぶ。
有限乗法群である場合、\(a^n = 1\)となる最小の正整数\(n\)を \(a\)の位数 と呼ぶ。
有限加法群である場合、\(na = 0\)となる最小の正整数\(n\)を\(a\)の位数とする。

環(ring)#

集合\(R\)とその上の2つの二項演算\(+,×\)について以下の条件を満たすとき、\(R\)を環と呼ぶ。

  1. \((R,+)\)が可換群である。

  2. \((R,×)\)が半群である。

  3. 任意の元\(x,y,z\in R\)に対して

  • \(x×(y+z) = x×y+x×z\)

  • $(y+z)×x = y×x + z×xk が成立する (分配則)

また、2. について、モノイドであるときは単位的環と呼ぶ。
上に加えて、 二項演算\(×\)が交換法則を満たすとき、可換環と呼ぶ。

Note

環\(R\)は自身の集合\(R\)上で足し算、掛け算、引き算が出来る。しかし逆元の存在が保証されないため割り算は出来るとは限らない。

環の例#

  • \(\mathbf{Z}\)

群の例より\(+\)に関して\(\mathbf{Z}\)は可換群となる。さらに、\(×\)に関して群の条件1,2を満たす(モノイドとなる)。 さらに\(+,×\)に対して分配則も満たすため\(\mathbf{Z}\)は可換環である。

多項式環#

\(A\)を可換環とする。\(A\)の要素\(a_0,a_1,...,a_n \in A\)を係数に持った多項式

\[a_0 + a_1X + a_2 X^2 + ... + a_nX^n \quad \quad (n \in \mathbf{N}) \]

を\(A\)上の多項式といい、その全体の集合

\[ A[X] = \{a_0 + a_1X + a_2 X^2 + ... + a_nX^n | n \in \mathbf{N},a_0,a_1,...,a_n \in A\} \]

は可換環である。\(A[X]\)を\(A\)上の多項式環と呼ぶ。

剰余環\(\mathbf{Z}/n\mathbf{Z}\)#

自然数\(n>= 2\)で割った剰余が等しい整数を集めた集合を剰余類と呼ぶ。例えば、\(n=3\)で割ったあまりは\(0,1,2\)のどれかになる。3で割って余りがそれぞれ\(0,1,2\)になる数をまとめて\([0]_3,[1]_3,[2]_3\)と記述する。 今，以下のような集合を考えたとき，これを剰余類環と呼び環構造をなす。

\[ \mathbf{Z}/n\mathbf{Z} := \{[a]_n|a \in \mathbf{Z}\}=\{[0]_n,[1]_n,...,[n-1]_n\} \]

体(field)#

集合\(F\)とその上の二項演算\(+,×\)について以下の条件を満たすとき、\(F\)を体と呼ぶ。

  1. \(F\)は演算\(+,×\)において単位的環である。

  2. 集合\(F \backslash \{0\}\)が演算\(×\)において可換群となる。ただし、\(F \backslash \{0\}\)は\(F\)から加法単位元\(0\)を除いた集合である。

Note

簡単にいうと、集合\(F\)内で四則演算(零による除算以外)が出来るのが体

有限体#

有限個の要素からなる体を有限体という。また、その要素数を位数という。 素数\(p\)に対して剰余類環\(\mathbf{Z}/p\mathbf{Z}\)は0以外の数で四則演算ができるため体となる。その要素数は\(p\)個と有限であるため有限体である。
\(\mathbf{Z}/p\mathbf{Z}\)は\(GF(p)\)と書くこともある。