暗号の数学
代数系
代数系とは
- 演算
ある集合 $A$ において定義された写像
\[ f: A \times A \rightarrow A,\ f(x, y) = z \qquad (x,y,z \in A)\]
を2項演算という.一般に,$A^m$ から $A$ への写像は $A$ における $m$ 項演算と呼ばれる.
- 代数系
集合 $A$ に演算 $\odot$ が定義されている(集合 $A$ の任意の2つの元に2項演算 $\odot$ を施して得られる結果が集合 $A$ の元である)とき,この集合と演算の組 $(A;
\odot)$ を代数系という.
集合 $A$ の任意の2つの元に2項演算 $\odot$ を施して得られる結果が集合 $A$ の元であるとき,集合 $A$ は演算 $\odot$ に関して閉じているという.
- 代数系の直積
代数系 $(A; \odot)$ に対して,直積集合 $(A^2=A \times A)$ での演算 $\odot$ を次のように定義する.
\[ (x_1,\ y_1)\odot(x_2,\ y_2)=(x_1\odot x_2,\ y_1\odot y_2) \]
ここで,$(x_1,\ y_1),\ (x_2,\ y_2)$ は,集合 $A$ の2つの要素を表す.
このとき,$(A^2;\ \odot)$ は代数系であり,代数系 $A$ の直積という.同様に,代数系の $n$ 次の直積 $(A^n;\ \odot)$ が定義できる.
群 (Group)
- 群の定義
集合 $G$ の任意の元 $x, y$ の間に演算・が定義され,次の公理が満たされるとき,$G$ を群という.
- $G$ の任意の元 $x, y$ に対し,$x・y$ が $G$ に属する.
- $G$ の任意の元 $x, y, z$ に対し,結合則が成立する.
$x・(y・z) = (x・y)・z$
- $G$ の任意の元 $x$ に対し,$x・e = e・x = x$ となるような単位元 $e$ が存在する.
- $G$ の任意の元 $x$ に対し,$x・y = y・x = e$ を満たすような逆元 $y = x^{-1}$ が存在する.
代数系 $G$ が 1,2 を満たすとき半群,1,2,3を満たすとき単位的半群(モノイド)という.
- 群の種類
群の種類には,次のようなものがある.
- 可換群(アーベル群)
任意の元 $x, y$ に対し,$x・y = y・x$ が常に成立する群
- 巡回群
1つの元(生成元)から生成される群
$\langle a \rangle = \{a^n\ |\ n \in N \}$ $\quad$ ($a$: 生成元)
$a^m = 1$ となる最小の整数 $m$ を位数という.
$\langle a \rangle = \{1, a, a^2, \cdots , a^{m-1} \}$
- 有限群
有限個の要素(元)からなる群
元の個数を位数という.
- 無限群
無限個の元からなる群
実数の集合 $R$,整数の集合 $Z$ など
部分群
群 $G$ の部分集合 $H$ が $H$ だけで群をなしているとき,$H$ を $G$ の部分群という.
$H$ が部分群であるためには,
- 演算・に対して閉じていること.
- 単位元を含むこと.
- $H$ のすべての元の逆元を含むこと.
を満足すればよい.
環 (Ring)
- 環とは
集合 $R$ に加法+と乗法・が定義され,次の公理が満たされるとき $R$ を環という.
- $R$ は加法に関してアーベル群をなす.
加法に関する単位元を零元といい $0$ で表す.$x \in R$ の加法に関する逆元は $-x$ で表す.
- $R$ の任意の元 $x, y$ に対して,$x・y$ が $R$ に属する.
- $R$ の任意の元 $x, y, z$ に対して,乗法に関する結合則が成立する.
$x・(y・z) = (x・y)・z$
- $R$ の任意の元 $x, y, z$ に対して,分配則が成立する.
$x・(y + z) = x・y + x・z$
$(x + y)・z = x・z + y・z$
- 整数環
整数の集合 $Z$ において,通常の加法+と乗法・を定義した代数系 $(Z; +, ・)$ は,
- 加法に関してはアーベル群
- 乗法に関しては可換モノイド(単位的半群)
- 乗法の加法に関する分配律が成立
より単位的可換環である.これを整数環という.
- 環の性質
- 任意の元と零元との積は零元になる.
$x・0 = 0・x = 0$
- $\forall a, b \in R$ に対して以下が成立つ.
$(-a)・b = a・(-b) = -(a・b)$
$(-a)・(-b) = a・b$
- 零でない二つの元の積が零元となることがある.その非零の元を零因子という.
- 零因子をもたない単位的可換環を整域という.整数環 $Z$ は聖域である.
- イデアル
可換環 $R$ の部分集合 $I$ が以下の性質を持つとき $R$ のイデアル(ideal)という.
- $I$ の任意の元 $\alpha, \beta$ に対して
\[ \alpha + \beta \in I \]
が常に成立つ.
- $R$ の任意の元 $a$ と $I$ の任意の元 $\alpha$ に対して以下が成立つ.
\[ a\alpha \in I \]
$n$ の倍数全体を ($n$) で表すと,これは $Z$ のイデアルになっている.
可換環 $R$ のイデアル $I$ が与えられると,新しい可換環 $R/I$ を作ることができる. これを $R$ の $I$ による剰余環(residue ring)という.
$R$ の元 $a$ に対して,$R$ の部分集合 $\overline{a}$ を
\[ \overline{a} = \{\alpha \in R\ |\ a - \alpha \in I \} \]
で定義する.$\overline{a}$ はイデアル $I$ を法とする $a$ を含む剰余類と呼ばれる.
体 (Field)
- 体とは
集合 $F$ に加法+と乗法・が定義され,次の公理が満たされるとき,$F$ を体という.
- $F$ は加法に関してアーベル群をなす.
- 加法の単位元 $0$ を除いた集合 $F^* = F - \{0\}$ は乗法に関してアーベル群(または群)である.
- $F$ の任意の元 $x, y, z$ に対して,分配則が成立する.
$x・(y + z) = x・y + x・z$
$(x + y)・z = x・z + y・z$
- 体上の演算
- 四則演算(加減乗除)が可能
- 減算は加法の逆元(負号 $-$ をつけたもの)の加算
- 除算は乗法の逆元(逆数)の乗算
- 零元の乗法に関する逆元は定義されないため,$0$ による除算は定義されない.
- 体では零因子はない(整域である).2つの元の乗算結果が零ならば,少なくとも一方は零元である.
- 有限体
有限個の元からなる体
- 元の個数が $p^n$ 個の有限体
ガロア体:
$\mathrm{GF}(p^n)$ (または $F_{p^n}$)
- 元の個数が素数 $p$ 個の有限体
素体:
$\mathrm{GF}(p)$ (または $F_p$,$Z/pZ$)
- 標数
体 $K$ が与えられていてその零元を $0$,乗法に関する単位元を $1$ とするとき,$n * 1 = 1 + 1 + … + 1 = 0$ となる最小の自然数 $n$ を体 $K$ の標数と呼ぶ.このような自然数が存在しない場合は $0$ とする.有理数体の標数は $0$ であり,有限体 $\mathrm{GF}(p$) ($p$ は素数)の標数は $p$ である.
有限体の元の個数は,ある素数 $p$ と正整数 $n$ とによって,$p^n$ と表される.この $p$ を有限体の標数と呼ぶ.
- 代数的閉包
体 $K$ の代数拡大が $K$ に限るとき,$K$ を代数的閉体という(これ以上代数的に拡大することはできない体).
体 $K$ の代数拡大体で,その体の元を係数とするすべての多項式の解がその体の元となるもの(代数的閉体となる)を代数的閉包といい,$\overline{K}$ で表す.
実数体 $R$ に虚数を付加し $R$ を拡大することにより複素数体 $C$ が得られる.$C$ 係数のすべての多項式は $C$ 内に解を持つため,複素数体 $C$ は実数体 $R$ の代数的閉包となる.
体の拡大 $K/F$ において,
\[ \{\alpha \in K\ |\ \alpha はF上代数的(F(\alpha)=0) \} \]
を $K$ における $F$ の代数的閉包といい,$\overline{F}_K$ で表す.