暗号理論入門　3.7〜3.10

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

3.7 剰余環の演算に対する計算時間

公開鍵暗号のあらゆる方式で、剰余環の計算が行われるので、計算量の知ることが重要。

modulo $m$ の二つの剰余類の和と差は時間 $O(size\ m)$ で計算される。
積と商は $O((size\ m)^{2})$ の時間がかかる。
すべての演算は $O(size\ m)$ の大きさの格納領域が必要。

3.8 既約剰余群

mod mのすべての既約剰余類の集合は、乗法に関する有限アーベル群である。

mod mの既約剰余類の群は、mod mの規約剰余群(primitive residue class group)といい、 $(\mathbb{Z} / m \mathbb{Z})^*$ と書く。
その位数を $\phi(m)$ で表す。
写像
　 $\mathbb{N} \to \mathbb{N}$ 、 $m \to \phi(m)$
をオイラーの $\phi$ 関数という。
$\phi(m)$ は、{1, 2, ..., m} の中の gcd(a, m) = 1である数aの総数である。特に $\phi(1) = 1$ である。
例．　 $(\mathbb{Z}/ 12\mathbb{Z})^* = \{1 + 12\mathbb{Z},\ 5 + 12\mathbb{Z},\ 7 + 12\mathbb{Z},\ 11 + 12\mathbb{Z}\}$ は mod 12の規約剰余群である。 $\phi(12) = 4$ である。

$p$ が素数のとき、 $\phi(p) = p - 1$ が成り立つ。

3.9 群の元の位数

$G$ を乗法を演算とする群とし、1をその単位元とする。
$g \in G$ とし、 $g^{e} = 1$ となる自然数 $e$ が存在すれば、そのような最小の数を $g$ の $G$ での位数(order)という。
その他の場合、 $G$ での $g$ の位数は無限大であるという。
$G$ での $g$ の位数は $order_G g$ と書く。
例． $2 + 13\mathbb{Z}$ の $(\mathbb{Z}/13\mathbb{Z})$ の中での位数は12となる。