暗号理論入門　3.2〜3.3

作者: 林芳樹
出版社/メーカー: 丸善出版
発売日: 2012/04/20
メディア: 単行本
この商品を含むブログを見る

3.2 半群

$X$ が集合であるとき、 $X$ の元の任意の組 $(x_1, x_2)$ に１つの元 $x_1 \circ x_2$ が対応しているような写像 $\circ : X \times X \to X$ を $X$ 上の演算子(operation)という。

剰余類 $a + m \mathbb{Z}$ と $b + m \mathbb{Z}$ の和を $(a + m \mathbb{Z}) + (b + m \mathbb{Z}) = (a + b) + m \mathbb{Z}$ と定義する。
剰余類 $a + m \mathbb{Z}$ と $b + m \mathbb{Z}$ の積を $(a + m \mathbb{Z}) \cdot (b + m \mathbb{Z}) = (a \cdot b) + m \mathbb{Z}$ と定義する。

空でない集合 $H$ と、 $H$ 上の結合法則を満たす演算 $\circ$ の組 $(H, \circ)$ を半群(semigroup)という。半群はその演算 $\circ$ について可換であるとき、可換またはアーベル(abelian)であるという。
例.　 $(\mathbb{Z}, +)$ 、 $(\mathbb{Z}, \cdot)$ 、 $(\mathbb{Z}/m \mathbb{Z}, +)$ 、 $(\mathbb{Z}/m \mathbb{Z}, \cdot)$ は可換半群である。

半群 $(H, \circ)$ の単位元(unit element)は、任意の $a \in H$ に対して $e \circ a = a \circ e = a$ を満たす元 $e \in H$ のことである。半群が単位元を持てば、単位半群(monoid)という。

$e$ が半群 $(H, \circ)$ の単位元であり、 $a \in H$ に対して $a \circ b = b \circ a = e$ となる $b \in H$ が存在すれば、 $b \in H$ は $a$ の逆元(inverse)という。 $a$ が逆元をもてば、 $a$ は半群 $(H, \circ)$ で可逆(invertible)であるという。

3.3 群

群(group)とは、単位元をもち、かつ各元が可逆となる半群のことである。群はその半群が可換であるとき、可換またはアーベルであるという。
例.　半群 $(\mathbb{Z}, +)$ はアーベル群である。
半群 $(\mathbb{Z}, \cdot)$ はアーベル群ではない。任意の元が逆元をもつとは限らないため。