暗号学 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