暗号理論入門　2.11〜3.1

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

2.11 素因数分解

自然数 $p > 1$ が、二つの正の数1と $p$ のみを約数としてもつ場合、素数(prime number)という。
すべての素数の集合を $\mathbb{P}$ で表す。
素数ではない自然数 $a > 1$ を合成数(composite)という。
素数 $p$ が整数 $a$ を割れば $p$ は $a$ の素因数(prime divisor)という。

任意の自然数 $a > 1$ は素因数をもつ。

素数 $p$ が二整数の積を割り切れば、 $p$ は両方の因数のうち少なくとも一つを割り切る。

素数 $p$ が素数の積 $\prod_{i=1}^k q_i$ を割り切れば、 $p$ は素数 $q_1,\ q_2,\ ...,\ q_k$ のうちの一つに一致する。

任意の自然数 $a > 1$ は素数の積として表すことができる。順序を除き、因数は一意的に定まる。

自然数 $a$ の素因数分解(prime factrization)は、素因数の積としての数の表し方である。
自然数の素因数分解を計算する効果的なアルゴリズムは知られていない。素因数分解の問題が難しいことを示す証明もまた知られていない。

第3章

この章が終われば暗号の話が始まる。

3.1 合同

$m$ が $b - a$ を割り切るとき、 $a$ は $b$ に modulo $m$ で合同(congruent)であるといい、 $a \equiv b\ mod\ m$ と書く。

$a$ の同値類(equivalence class)は、 $a$ と $m$ の整数倍の和により与えられるすべての整数からなる。したがって
　 $\{b\ :\ b \equiv a\ mod\ m\} = a + m \mathbb{Z}$
となる。これを $a$ の mod $m$ での剰余類(residue class)という。

$mod\ m$ の剰余類全体の集合は $\mathbb{Z} / m \mathbb{Z}$ で表され、 $m$ 個の元をもつ。
$mod\ m$ での任意の剰余類からちょうど一つの元を含む集合を $mod\ m$ の完全剰余系(complete system of residues)という。
例.　 $mod\ 3$ の完全剰余系は $3 \mathbb{Z}$ 、 $1 + 3 \mathbb{Z}$ 、 $2 + 3 \mathbb{Z}$ から各々一つずつの元を含む。{0, 1, 2}、{3, -2, 5}、{9, 16, 14}はmod 3の完全剰余系である。

$mod\ m$ の完全剰余系は{0, 1, ..., m - 1}である。その元を $mod\ m$ の最小非負剰余といい、その代表系を $\mathbb{Z}_m$ で表す。
同様に、{1, 2, ..., m} は $mod\ m$ の完全剰余系である。その元は $mod\ m$ の最小正剰余という。
{n + 1, n + 2, ..., n + m}は $n = - \lceil m / 2 \rceil$ に対する $mod\ m$ の完全剰余系である。その元を $mod\ m$ の絶対値最小の正剰余という。