暗号理論入門(整数3)

今回は、ユークリッドのアルゴリズムについて解説をしていきたいと思います。この話をするうえで、最大公約数について触れる必要があるので、簡単にまとめて本題のアルゴリズムの話に行きたいと思います。

最大公約数

なお、ここで出てくる定理などについては証明を省略します。

補足として、0と0の最大公約数は0とする。

整数$a_1 , \cdots , a_k\hspace{3mm}(k \geqq 1)$の最大公約数も同様に定義される。$a_i$のうち、少なくとも1つ0でないとき、$gcd(a_1 , \cdots , a_k)$はすべての$a_i$を割り切る最大公約数である。すべての$a_i$が0に等しければ、$gcd(a_1 , \cdots , a_k) = 0$と定義する。

$ \alpha_1 , \cdots , \alpha_k$が実数であれば、

$\alpha_1\mathbb{Z}+ \cdots + \alpha_k\mathbb{Z} = \{\alpha_1z_1+\cdots + \alpha_kz_k\hspace{2mm}|\hspace{2mm}z_i \in \mathbb{Z} , 1\leqq i \leqq k\}$

と表す。これはすべての整数値線形結合の集合である。

ユークリッドのアルゴリズム

ここからが本題です。最大公約数を求めるために、ユークリッドの互除法という手法を使って求めたことがあるかと思いますが、ここでは、なぜ、ユークリッドの互除法で最大公約数が計算できるのかを見て、そこから暗号でどのように活用されているのかを見ていきたいと思います。

下の定理を示すのに使う過去に証明した定理1と定理2を使います。下にリンクを張っておきます。

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

証明

(1)

この主張は正しい。$b = 0$で$a= 0$なら、$gcd(a,b) = 0$となる。一方、$a\ne 0$なら、最大公約数は$|a|$になる。

(2)

$b \ne 0$とする。定理2より、$a = q|b| + (a \mod |b|)$となるようなある整数$q$が存在する。

よって、$a,b$の最大公約数は$|b|$と$a \mod |b|$の最大公約数を割り切り、逆も成立する。($|b|$と$a \mod |b|$の最大公約数が$a,b$の最大公約数を割り切る)

両方の最大公約数は負でないので、定理1より主張は成立する。□

$gcd(100,35) = gcd(35 , 100 \mod 35) = gcd(35 , 30) = gcd(30 , 35 \mod 30) = gcd(30 , 5) = gcd(5 , 0) = 5$

よって、100と35の最大公約数は5であることが分かりました。

次に、本題の一つであるユークリッドのアルゴリズム(ユークリッドの互除法)の計算でなぜ、上手く最大公約数を求めることができるのかについて見ていきます。

証明
ユークリッドのアルゴリズムが中断したとき、実際に$a$と$b$の最大公約数が求まったということを示すために、次の記号を導入する。

$$ r_0 = |a| \hspace{3mm},\hspace{3mm} r_1 = |b|\hspace{1cm}(1)$$

とおき、$k \geqq 1$と$r_k \ne 0$に対して、

$$ r_{k+1} = r_{k-1} \mod r_k\hspace{1cm}(2)$$

とする。ここでの$r_2 , r_3,\cdots$はユークリッドのアルゴリズムの繰り返しの操作の中で計算される剰余の数列である。$k$回目の計算の後、ユークリッドのアルゴリズムでは、現在計算している2数$r_k , r_{k+1}$について$gcd(a,b) = gcd(r_k,r_{k+1})$が成立するので、

$$ a = r_k \hspace{3mm}, \hspace{3mm}b = r_{k+1}$$

とみなすことができる。これにより、$a$と$b$の最大公約数は変化しない。

ユークリッドのアルゴリズムにより$a$と$b$の最大公約数が計算できることを示すには、$r_k$が最終的に0になることを示せばよい。

しかし、$(2)$により数列$(r_k)_{k\geqq 1}$が単調減少であることから結論が得られる。

以上より、ユークリッドのアルゴリズムによって最大公約数を計算できることが示された。□

ユークリッドアルゴリズムの反復回数の評価

ユークリッドのアルゴリズムを利用すると、効率よく$a,b$の最大公約数を計算することができる。これを示すために、ユークリッドのアルゴリズムの反復回数を評価する。なるべく反復回数が少ない方が、計算量が少ないことを意味するからです。

一般に、$a>b>0$ と仮定することができます。なぜならば、もし $b=0$だったら、ユークリッドのアルゴリズムはそこで終了し、最大公約数を求めることができ、また、$a< b$のときも、最初にユークリッドのアルゴリズムを1回行えば、次の段階で $a>b$の形にすることができるからです。

つまり、何が言いたいかというと、ユークリッドのアルゴリズムの反復回数を考える際には、最初から $a>b>0$として考えて大丈夫ですということです。

ここまでの内容を踏まえて、次に進みます。

$r_n$が剰余の数列$(r_k)$の最後の0でない項とする。このとき、$n$はユークリッドのアルゴリズムが$gcd(a,b)$を計算するのに必要とする反復回数の総数である。

さらに、
$$ q_k = \left\lfloor \dfrac{r_{k-1}}{r_k} \right\rfloor\hspace{5mm}(1 \leqq k \leqq n)\hspace{1cm}(2.4)$$
とすると、$q_k$は$r_{k-1}$の$r_k$による除法での商であり、$r_{k-1} = q_kr_k + r_{k+1}\hspace{1cm}(2.5)$が成立する。

証明
$r_{k-1} > r_k > r_{k+1}$が成立するので、(2.4)から$1 \leqq k \leqq n$に対して、$q_k \geqq 1$が成立する。

$q_n = 1$と仮定する。このとき、$r_{n-1} = r_n$となるが、これは不可能である。

なぜなら、数列$(r_k)$は単調減少であるからである。よって、$q_n \geqq 2$.

(補足：$r_n$が剰余の数列$(r_k)$の最後の0でない項であるから、$r_{n+1} = 0$となる)□

この演習問題は次の定理を示すのに使います。もしよければ解いてみてください。

証明
問題1より、$gcd(a,b) = r_n = 1$であると仮定することができる。

帰納法で$r_k \geqq \Theta^{n-k} \hspace{5mm}(0 \leqq k \leqq n)\hspace{1cm}(2.6)$が成立することを示す。これによると、特に$b = r_1 \geqq \Theta^{n-1}$となる。

(定理6の証明の中で$ r_0 = |a| \hspace{3mm},\hspace{3mm} r_1 = |b|$とおいている。今回は$a,b > 0$なので、$a = r_0\hspace{2mm},\hspace{2mm}b = r_1$となる。)

この等式の対数を取ると、
$$ \log b \geqq \log \Theta^{n-1} = (n-1)\log \Theta$$
よって、$n-1 \leqq \dfrac{\log b}{\log \Theta} \Leftrightarrow n \leqq \dfrac{\log b}{\log \Theta} + 1$を得る。

(2.6)を示す。まず$r_n = 1 = \Theta^0$が成立し、補題7より
$$ r_{n-1} = q_nr_n = q_n \geqq 2 > \Theta$$
となる。$0 \leqq k \leqq n -2 $とし、$k < k'$に対して主張が成立するとする。

このとき、補題7から
$$ r_k = q_{k+1}r_{k+1} + r_{k+2} \geqq r_{k+1} + r_{k+2}$$
仮定より$k < k'$では$r_{k'} \geqq \Theta^{n-k'}$が成立するので、

$$ r_k \geqq r_{k+1} + r_{k+2} \geqq \Theta^{n-k-1} + \Theta^{n-k - 2} = \Theta^{n-k-1}(1 + \dfrac{1}{\Theta}) = \Theta^{n-k}$$

が成立する。よって、(2.6)と定理が示された。

今回は以上です。