暗号学 1歩目

[TOC]

代数学

群論

Definition 1-1. 群

集合\(G\)と\(G\)の上の2項演算\(\phi\)(簡単のため\(\phi(g_1, g_2) = g_1 g_2\)とも書く)が以下を満たすとき,\((G, \phi)\)は群(group)であるという.
(0) \[\forall g_1, g_2 \in G, g_1 \cdot g_2 \in G\]
これは\(\phi\)が\(G\)上の二項演算であるという条件である.
(1) 結合法則(associative law)
\[\forall g_1, g_2, g_3 \in G, g_1(g_2g_3) = (g_1 g_2) g_3\]
(2) 単位元の存在
\[\exists e \in G \text{ s.t. } \forall g \in G g e = e g = g\]この\(e\)を\((G, \phi)\)の単位元(identity)という.
(3) 逆元の存在
\[\forall g \in G , \exists g^{-1} \text{ s.t. } g g^{-1} = g^{-1} g = e\]
この\(g^{-1}\)を\(g\)の逆元(inverse)という.

群\((G, \phi)\)について,演算\(\phi\)に混同の恐れがないときは単に\(G\)と書く.
群の要素数\(\# G = | G|\)を\(G\)の位数(order)とも呼ぶ.

Corollary 1-2.

\((G, \phi)\)の単位元はただひとつだけ存在する.
proof.
\(e, e'\)を\(G\)の単位元とすると,\(e = ee' = e'e = e'\)

Definition 1-3. 部分群

群\((G, \phi)\)があって,\(H \subset G\)が同じ演算によって群になるとき,すなわち\((H, \phi)\)が群であるとき,\((H, \phi)\)は\((G, \phi)\)の部分群(subgroup)であるという.

Definition 1-4. 同値関係

集合\(S\)とその上の関係\(\sim\)が以下の条件を満たすとき\(\sim\)を同値関係(equivalency)という.
(1) 反射律(reflexivility)
\[ \forall x \in \S x \sim x\]
(2) 対象律(symmetry)
\[x \sim y \Rightarrow y \sim x\]
(3) 推移律(transitivity)
\[x \sim y, y \sim z \Rightarrow x \sim z\]
\[\forall x \in S x \sim x\]

Definition 1-5. 同値関係による商

(1)集合\(C(x) = \{ y| y \in S, y \sim x\}\)を\(x\)の同値類(equivalence class)といい,同値類の集合\(\{C(x) | x \in S\}\)を\(S\)の\(\sim\)による商(quotient set)といい,\(S / \sim\)と書く.
(2)\(C \in S / \sim\)について,\(x = C \Leftrightarrow C = C(x)\)なる\(x\)を\(C\)の代表元という.
(3) \(R \subset S\)が\(S / \sim\)の代表元を一つづつ含むとき,\(S / \sim\)の完全代表系という.明らかに\(|R| = |S/\sim|\)である.

群\(G\)と部分群\(H\)があって,\(g_1, g_2 \in G\)が\(g_1^{-1} g_2 \in H\)をみたすとき,\(g_1 \sim g_2\)と書くことにすると,\(\sim\)は同値関係である(証明略).同値類\(C(g)\)を特に\(gH\)と書いて左剰余類(left coset)と呼ぶ. \(\{gH| g\in G\}\)はこの同値関係による商 \(G / \sim = \{gH| g \in G\}\) に等しく,特に\(G / H\)と書く.

Proposition 1-6

任意の\(g \in G\)に\(|gH| = |H|\)
proof.

\[\phi: H\ni h \mapsto gh \in gH\]
という写像を考え,全単射であることを示す. 全射なのは明らかで,
\(h_1, h_2 \in H\)について,\(gh_1 = gh_2\)ならば左から\(g^{-1}\)をかけて\(h_1 =h_2\)
よって示せた.

Theorem 1-7 (Lagrange)

\[|G/H| |H|= |G|\]
proof.

\(G/H\)の完全代表系を\(\{x_i\}\)とする. \(| \{x_i\}|=|G/H|\)(def. 1-5)であり,また\(|C(x_i)| = |gH| = |H|\)(prop.1-6)から,
\[|G| = \sum_{i} |C(x_i)| = \sum_i |H| = |G/H||H|\]

参考文献:
代数学1群論入門, 雪絵明彦, 日本評論社, 2010
代数入門―群と加群, 堀田良之, 裳華房, 1987