暗号理論入門　1章〜2.3まで

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

とりあえずAES暗号のところまで読む。

第１章

本の内容の説明のみ。

第２章

2.1 基礎事項

$\mathbb{N} = \{\ 1,\ 2,\ 3,\ 4,\ 5,\ ... \}$ を自然数全体の集合
$\mathbb{Z} = \{ 0, \pm1, \pm2, \pm3, ...\}$ を整数全体の集合
$\mathbb{Q}$ を有理数全体の集合
$\mathbb{R}$ を実数全体の集合
と表したとき、
　 $\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R}$
が成立する。

実数の集合 $M$ について、 $M$ のあらゆる元が $\gamma$ より大きくなる実数 $\gamma$ が存在するとき、 $M$ は下に有界である(bounded from below)という。
または、 $M$ は下から $\gamma$ に抑えられているという。自然数全体の集合は、下から0で抑えられている。

実数 $\alpha$ に対して
　 $\lfloor \alpha \rfloor = \max \{ b \in \mathbb{Z} : b \le \alpha \}$
とする。数 $\lfloor \alpha \rfloor$ は $\alpha$ より小さいか等しい最大の整数を意味している。
例. $\lfloor 3.43 \rfloor = 3$ であり、 $\lfloor -3.43 \rfloor = -4$ である。

2.2 整除

$n = ab$ であるような $b$ が存在すれば、 $a$ は $n$ を割り切る(devide)という。
$a$ が $n$ を割れば、 $a$ は $n$ の約数(devisor)、 $n$ は $a$ の倍数(multiple)であるいい、 $a | n$ と書く。

$a$ , $b$ が整数であり $b > 0$ であれば、 $a = qb + r$ かつ $0 \le r \lt b$ であるように一意に定まる整数 $q$ と $r$ が存在する。
すなわち $q = \lfloor a / b \rfloor$ かつ $r = a - bq$ である。
$q$ を商(quotient)といい、 $r$ を余りまたは剰余という。 $r \equiv a \bmod b$ と表す。

2.3 整数の表し方

集合 $M$ に対して、 $M ^ k$ は $M$ の項による長さ $k$ のすべての数の列の集合を表す。
例. 列 $(0, 1, 1, 1, 0)$ は $\{ 0, 1 \} ^ 5$ の元である。 $\{1, 2\} ^2 = \{ (1,1), (1,2), (2,1), (2,2)\}$ である。

$g$ は自然数で $g \gt 1$ とする。任意の自然数 $a$ に対して、一意的に定まる自然数 $k$ と一意的に定まる数列
　 $(a_1,\ ...,\ a_k) \in \{0,\ ...,\ g - 1\}^k$
が $a_1 \ne 0$ かつ
　 $a = \sum_{i=1}^{k-i} a_i g^{k-i}$
であるように定まる。

ここで $k = \lfloor log_g a \rfloor + 1$ であり、 $a_i$ は $a - \sum_{j=1}^{i-1} a_j g^{k-j}$ の $g^{k-i} (1 \le i \le k)$ による除法の整数の商である。

$(a_1,\ ...,\ a_k)$ を $a$ の $g$ 進展開(g-adic expansion)という。 $a_k$ を $k$ 桁目の数という。その列の長さは $k = \lfloor log_g a \rfloor + 1$ である。
$g = 2$ のとき、この列を $a$ の2進展開(binary expansion)と呼ぶ。 $g = 16$ のときは16進展開(hexadecimal expansion)という。