暗号理論入門　3.4〜3.6

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

3.4 剰余環

環(ring)は組 $(R,\ +,\ \cdot)$ において、 $(R,\ +)$ がアーベル群でかつ $(R,\ \cdot)$ が半群であり、さらに、すべての $x, y, z \in R$ に対して分配法則 $x \cdot (y + z) = (x \cdot y) + (x \cdot z)$ と $(x + y) \cdot z = (x \cdot z) + (y \cdot z)$ が成立するものである。
半群 $(R, \cdot)$ が可換であるとき、環は可換であるという。
環の単位元とは半群 $(R, \cdot)$ の単位元のことである。

組 $\mathbb{Z}, + , \cdot)$ は単位元1をもつ可換環である。 $(\mathbb{Z}/m \mathbb{Z}, +, \cdot)$ は単位元 $1 + m \mathbb{Z}$ をもつ可換環である。この環をmodulo $m$ の剰余環(residue class ring)という。

$R$ を単位元をもつ環とする。乗法についての半群 $R$ で、 $a$ が可逆であれば、 $R$ の元 $a$ を $R$ の可逆元、または単元という。
0でない元 $a \in R$ に対し、ある0でない元 $b \in R$ が存在し、 $ab = 0$ または $ba = 0$ となるとき、 $a$ を零因子(zero divisor)という。

整数環は零因子を持たない。
剰余環 $\mathbb{Z} / m \mathbb{Z}$ の零因子は、 $1 \lt gcd(a, m) \lt m$ とする剰余類 $a + m \mathbb{Z}$ である。もし $a + m \mathbb{Z}$ が $\mathbb{Z} / m \mathbb{Z}$ の零因子であれば、 $ab \equiv 0\ mod\ m$ となるある整数 $b$ が存在する。しかし $a \equiv 0\ mod\ m$ でも $b \equiv 0\ mod\ m$ でもない。
$m$ は $ab$ の約数であるが、 $a$ の約数でも $b$ の約数でもない。 $1 \lt gcd(a, m) \lt m$ が成立する。
$m$ が素数のとき、 $\mathbb{Z} / m \mathbb{Z}$ は零因子をもたない。

3.5 体

体(field)とは、0ではない任意の元が可逆であり、単位元をもつ可換環のことである。
例.　整数の集合は体ではない。（可逆な整数は1と-1のみだから）
実数全体の集合と複素数全体の集合は体をなす。

3.6 剰余環での除法

$R$ を環とし、 $a,\ n \in R$ とする。
$n = ab$ であるような $b \in R$ が存在するとき、 $a$ は $n$ を割り切るという。
$a$ が環の元 $n$ を割り切るとき、 $a$ を $n$ の約数、 $n$ を $a$ の倍数といい $a | n$ と書く。

剰余類 $a + m \mathbb{Z}$ が $\mathbb{Z} / m \mathbb{Z}$ において可逆、すなわち $ax \equiv 1\ mod\ m$ が解をもつ必要十分条件は、 $gcd(a, m) = 1$ である。

$gcd(a, m) = 1$ である剰余類 $a + m \mathbb{Z}$ をmodulo $m$ の規約剰余類(primitive residue class)という。
例． $m = 12$ とする。剰余類 $a + 12 \mathbb{Z}$ は、 $gcd(a, 12) = 1$ であるときに限り $\mathbb{Z} / 12 \mathbb{Z}$ で可逆である。したがって、mod 12の可逆剰余類は $1 + 12 \mathbb{Z}$ 、 $5 + 12 \mathbb{Z}$ 、 $7 + 12 \mathbb{Z}$ 、 $11 + 12 \mathbb{Z}$ である。
$5 + 12 \mathbb{Z}$ の逆元を見つけるには拡張ユークリッドアルゴリズムを使い、 $5 * 5 \equiv\ mod\ 12$ となる。