暗号理論入門(第2章整数1)

洋書の暗号理論の本とは別で、『暗号理論入門(丸善出版)』の本も読んでいます。こっちは、洋書と比べて日本語ということもあり、さくさく読めるかなーと思って手を出して痛い目を見たものになります。自主ゼミの成果をまとめるという意味でこの記事を書いています。

2.1基礎事項

次の記号を定める。

実数$a$に対して、

$$ \lfloor a \rfloor = \max \{b \in \mathbb{Z} \mid b \leqq a\}$$

とする。数$\lfloor a \rfloor$は$a$より小さいかまたは等しい最大の整数を表している。

2.2 整除

$n = ab$であるような$b$が存在すれば、$a$は$n$を割り切るという。

$a$が数$n$を割れば、$a$は$n$の約数、そして$n$は$ a$の倍数であるといい、$a | n$と書く。$n$は$a$で割り切れるともいう。$a$が$n$の約数でないとき、$a \nmid n$と書く。

1.$a | b $と$b \mid c$より$a \mid c$が成り立つ
2.$a \mid b$から任意の$c$に対して$ac \mid bc$が成立する
3.$c \mid a$と$c \mid b$から任意の$d$と$e$について$c \mid da + eb$が成立する
4.$a \mid b$と$b \ne 0$から、$|a| \leqq |b|$が成立する
$\hspace{3mm}$$a \mid b$と$b \mid a$から、$|a| = |b|$が成立する

証明は簡単のため、省略する。

$a , b$が整数で、$b > 0$であれば、$a = qb + r$かつ$0 \leqq r < b$であるように一意的に定まる整数$q , r$が存在する。すなわち、$q = \lfloor \dfrac{a}{b} \rfloor$かつ$r = a - bq$である。

証明

(i)存在すること

$a = qb + r$かつ$0 \leqq r < b$であるとする。

このとき、$0 \leqq \dfrac{r}{b} = \dfrac{a}{b} - q < 1$となる。

($0 \leqq r < b$より、$b \ne 0$なので、$b$で割ってあげると、$0 \leqq \dfrac{r}{b} < 1$となる。

$a = qb + r$より、$r = a - qb$であるから、両辺$b$で割ると、$\dfrac{r}{b} = \dfrac{a}{b} - q$となる。)

これから$\dfrac{a}{b} - 1 < q \leqq \dfrac{a}{b}$となり、したがって、$q = \lfloor \dfrac{a}{b}\rfloor$である。$r$については容易に示せる。

(ii)一意性

$a = qb + r = q'b + r'$が成り立つとする。
($q , q' , r , r' \in \mathbb{Z} \hspace{1mm},\hspace{1mm} 0 \leqq r , r' < b \hspace{1mm}$)

このとき、$qb + r = q'b + r'$
$\Longleftrightarrow (q - q')b = r' - r$

$q - q' > 0$とすると、$q - q'$は整数なので、$(q - q')b \geqq b$

$r , r' \geqq 0$かつ$r , r' < b$なので、　$ r' - r < b$となり、矛盾する。

よって、$q = q' , r = r'$である。□

定理2の状況では$a$の$b$による除法での$q$を商または整商といい、$r$を余りまたは剰余という。これを$r \equiv a \hspace{3mm}(\mod b)$と表す。

2.3 整数の表し方

自然数$g > 1$と正の実数$\alpha$に対して、$\log_g \alpha$で、$\alpha$の底$g$に対する対数を表す。集合$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$は自然数で、$g > 1$であるとする。任意の自然数$a$に対して、一意的に定まる自然数$k$と一意的に定まる数列

$$ (a_1,a_2,\cdots,a_k)\in\{0,1,\cdots,g-1\}$$

が$a\ne 0$かつ

$$ a = \sum_{i = 1}^k a_i g^{k-i}\hspace{1cm}(2.1)$$

であるように定める。

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

この定理3は、本の中ではかなり行間があるように個人的に感じたため、括弧内に付け足しをして保管することとします。証明の証明みたいになってしまって気持ちが悪いかもしれません。

証明
$a$を自然数とする。$a$の(2.1)のような表し方が存在すれば、

$$ g^{k-1} \leqq a = \sum_{i=1}^k a_ig^{k-i} \leqq (g-1)\sum_{i=1}^k g^{k-i} = g^k - 1 < g^k$$

が成立する。

各$a_i$は$0,\cdots , g-1$のどれかなので、

$$0 \leqq a_i \leqq g-1$$

よって、$a_ig^{k-i} \leqq (g-1)g^{k-i}$.
すべての項に対して上の関係が成り立つので、

$\sum_{i=1}^k a_ig^{k-i} \leqq \sum_{i=1}^k (g-1)g^{k-i} = (g-1)\sum_{i=1}^k g^{k-i}$

$\sum_{i=1}^k g^{k-i} = g^{k-1} + g^{k-2} + \cdots + g + 1$より

$(g-1)\sum_{i=1}^k g^{k-i}= (g-1)(g^{k-1} + g^{k-2} + \cdots + g + 1) = g^k - g^{k-1} + g^{k-1} - \cdots - g + g - 1 = g^k - 1 < g^k$

よって、

$$ k = \lfloor \log_g a \rfloor + 1$$

となる。

$g^{k-1} \leqq a < g^k$である。両辺に$\log_g$を取ると
$g>1$より$\log_g x$は単調増加であるから、大小関係は変化せず

$$ \log_g g^{k-1} \leqq \log_g a < \log_g g^k$$

$\Longleftrightarrow k-1 \leqq \log_g a < k$

これより$k-1 \leqq \lfloor \log_g a \rfloor \hspace{1mm},\hspace{1mm} \lfloor \log_g a \rfloor < k$となるので、

$\lfloor \log_g a \rfloor = k - 1 \Longleftrightarrow k = \lfloor \log_g a \rfloor + 1$

これにより$k$の一意性が証明される。数列$(a_1 , \cdots , a_k)$の存在と一意性を$k$について帰納法で証明する。

$k = 1$のとき、$a_1 = a$とおく。このとき、(2.1)は満たされ、$a_1$については他の選び方はない。

$k>1$とする。まず、一意性を示す。

もし、(2.1)のような表現が存在するならば、

$$ 0 \leqq a - a_1g^{k-1} < g^{k-1}$$

であり、よって、$0 \leqq \dfrac{a}{g^{k-1}} - a_1 < 1$となる。

$a - a_1g^{k-1} = (a_1g^{k-1} + a_2g^{k-2} + \cdots + a_k) - a_1g^{k-1} = a_2g^{k-2} + \cdots + a_k$

$0 \leqq a_i \leqq g-1$より

$a - a_1g^{k-1} = a_2g^{k-2} + \cdots + a_k \leqq (g-1)g^{k-2} + \cdots + (g-1) = g^{k-1}-1 < g^{k-1}$

これにより$a_1$は$a$の$g^{k-1}$による除法の(整数の)商であり、したがって、一意的に定まる。

$a' = a - a_1g^{k-1} = \sum_{i=2}^k a_ig^{k-i}$とおく。

$a' = 0$とすると、$a_i = 0\hspace{3mm}(2 \leqq i \leqq k)$である。

$a' = \sum_{i=2}^k a_ig^{k-i}$であれば帰納法により一意的に決まる$a'$の表現である。

$k = 1$なら、$a = a_1$と一意に定まる。

$k-1$まで一意に定まると仮定すると、$k$桁目の$a$は

$$ 0 \leqq \dfrac{a}{g^{k-1}} - a_1 < 1$$

より

$$ a_1 = \lfloor \dfrac{a}{g^{k-1}} \rfloor$$

となる。

すると、$a' = a - a_1g^{k-1}$も一意に定まる。

表現(2.1)が存在することは明らかである。

必要であるのは、$a_1 = \lfloor \dfrac{a}{g^{k-1}}\rfloor$とおき、他の係数を$a' = a - a_1g^{k-1}$という表し方から得ることである。□

定理3の列$(a_1 , a_2 , \cdots , a_k)$を$a$の$g$進展開という。$a_k$を$k$桁目の数という。その列の長さは$\lfloor \log_g a \rfloor + 1$である。

$g = 2$であるとき、この列を$a$の二進展開という。$g= 16$のときには十六進展開という。

自然数の$g$進展開は、最初の桁の数字が零でないという条件を付けたときのみ一意的である。$(a_1 , \cdots, a_k)$の代わりに$a_1a_2\cdots a_k$と書く。

$10101_{(2)} = 21_{(10)} \hspace{2mm},\hspace{2mm} A1C_{(16)} = 2588_{(10)}$

105の二進展開を決定する。

$$ 64 = 2^6 < 105 < 128 = 2^7$$

より、$a_1 = \lfloor \dfrac{105}{64} \rfloor = 1$ , $a_2 = \lfloor \dfrac{41}{32} \rfloor= 1$ , $a_3 = \lfloor \dfrac{9}{16} \rfloor = 0$ , $a_4 = \lfloor \dfrac{9}{8} \rfloor = 1$ , $a_5 = a_6 = 0$ , $a_7 = 1$

したがって、$105_{(10)} = 1101001_{(2)}$

十六進展開の二進展開への変換と、その逆の変換は簡単です。

$(h_1 , h_2 , \cdots , h_k)$を自然数$n$の十六進展開とする。$1 \leqq i \leqq k$に対して

$(b_{1,i} , b_{2 , i} , b_{3,i} , b_{4 , i})$を、$h_i$を表す長さ4の列とする。($16 = 2^4$)

したがって、

$$ h_i = b_{1,i}2^3 + b_{2,i}2^2 + b_{3,i}2 + b_{4,i}$$

このとき、$(b_{1,1} , b_{2,1} , b_{3,1} , b_{4 , 1} , b_{1,2} , \cdots , b_{4,k})$は$n$の二進展開である。

十六進数$n = 6EF$を考える。

数字を長さ4に正規化した二進展開は、$6_{(16)} = 0110_{(2)} $ , $E_{(16)} = 1110$ , $F_{(16)} = 1111$である。

よって、$6EF_{(16)} = 011011101111_{(2)}$

自然数の二進展開の長さをその自然数の二進長と呼ぶ。

0の二進長は1と定義する。整数の二進長はその絶対値の二進長である。整数$ a$の二進長は$size(a)$または$size \hspace{2mm}a$で表す。