集合（set）

集合とは、ものの集まりのことで、たとえば、次のようなものは集合として考えられる。

$$X=\{1,2,3\}$$

このとき、$1,2,3$ は集合 $X$ に入っているものであり、集合に入っている一つひとつのものを要素（元、element）という。

つまり、$1$ は $X$ の要素である。

$$1\in X$$

これは「$1$ は $X$ に属する」という意味だ。

一方、$4$ は $X$ に入っていない。

$$4\notin X$$

これは「$4$ は $X$ に属さない」という意味だ。

よく使う数の集合

数学では、よく使う数の集合を決まった記号で表す。

特に、$\mathbb{Z}$ は整数全体の集合を表す。

$$\mathbb{Z}=\{\dots,-3,-2,-1,0,1,2,3,\dots\}$$

つまり、$\mathbb{Z}$ は「整数の世界」だ。

よく使う集合には次のようなものがある。

暗号学の文脈では、$0$ と $1$ からなるビット列を扱うことが多い。そのため、$\mathbb{Z}_2$ や、それを使った $\mathbb{Z}_2^n$、$\mathbb{Z}_2^{*}$ という記法が出てくる。

$\mathbb{Z}_2$ は、直感的には「整数を $2$ で割った余りの世界」である。

整数を $2$ で割った余りは、$0$ か $1$ のどちらかしかない。

したがって、$\mathbb{Z}_2$ は次のように表せる。

$$\mathbb{Z}_2=\{0,1\}$$

暗号学では、$0$ と $1$ はビットとして扱われる。

そのため、$\mathbb{Z}_2$ は「ビットの値の集合」と考えると分かりやすい。

$\mathbb{Z}_2^n$ は、長さ $n$ のビット列全体の集合である。

たとえば、$n=3$ なら、長さ $3$ のビット列全体なので、次のようになる。

$$\mathbb{Z}_2^3=\{000,001,010,011,100,101,110,111\}$$

つまり、$\mathbb{Z}_2^3$ の要素は、長さ $3$ の $0/1$ 列である。

たとえば、$010$ は $\mathbb{Z}_2^3$ の要素である。

$$010\in\mathbb{Z}_2^3$$

一方、$0101$ は長さ $4$ なので、$\mathbb{Z}_2^3$ の要素ではない。

$$0101\notin\mathbb{Z}_2^3$$

一般に、$\mathbb{Z}_2^n$ は「長さ $n$ 固定のビット列の集合」だと考えればよい。

$\mathbb{Z}_2^{*}$ は、任意長のビット列全体の集合である。

つまり、長さ $0$ のビット列、長さ $1$ のビット列、長さ $2$ のビット列、長さ $3$ のビット列……をすべて集めたものだ。

$$\mathbb{Z}_2^*=\{\epsilon,0,1,00,01,10,11,000,001,\dots\}$$

ここで、$\epsilon$ は空文字列を表す。つまり、長さ $0$ のビット列である。

たとえば、次のものはすべて $\mathbb{Z}_2^{*}$ の要素である。

$$0\in\mathbb{Z}_2^*$$

$$1011\in\mathbb{Z}_2^*$$

$$001010111\in\mathbb{Z}_2^*$$

長