RSA暗号の数学その2 ユークリッドの互除法

公開日：2021年2月12日

最終更新日：2021年2月14日

1 はじめに
- 1.1 目標
  - 1.1.1 定理 2-1 (逆元の存在とその唯一性)
  - 1.1.2 補題 2-1 (商と余り)
2 定理 2-1 の唯一性の証明
3 定理 2-1 の存在性の証明 (前編)
- 3.1 最大公約数 (GCD)
- 3.2 ユークリッドの互除法 (Euclidean Algorithm)
4 次回予告

はじめに

前回の記事では、RSA 暗号の数理を理解するために必要な合同式について説明しました。今回は前回の予告通り、「ユークリッドの互除法」について解説したいと思います。まだスタイルが定まっておらず統一感がありませんが、お付き合いいただける方はぜひお読みください。
定理の証明と問題の解答は載せていますが、補題の証明はありません。

目標

今回と次回で次の定理を証明します。

定理 2-1 (逆元の存在とその唯一性)

$2$ 以上の整数 $n$ に対して、集合 $\ZZ_n = \{0, 1, 2, \dotsc, n – 1\}$ を定義する。正の整数 $a$ を $n$ と互いに素な $\ZZ_n$ の元 (要素) とするとき、$$ax \equiv xa \equiv 1 \pmod n$$をみたす $x \in \ZZ_n$ がただ一つ存在する。

整数 $x$ は $\ZZ_n$ 上の $a$ の乗法に関する逆元といえます。
時間に余裕がある方は前回省略した次の補題を証明してから進みましょう。

補題 2-1 (商と余り)

非負整数 $a,$ 正の整数 $b$ に対して、ある整数 $q,$ $r$ がただ一組存在し、$$a = bq + r\ \ (0 \leq r < b)$$をみたす。

上の $q,$ $r$ はそれぞれ $a / b$ の商と余りです。

定理 2-1 の唯一性の証明

まず、定理 2-1 の解の存在を仮定した上で、その唯一性を証明してしまいましょう。自分で証明したい方はここでスクロールを止めてください。

定理 2-1 の唯一性の証明

整数 $x,$ $x’ \in \ZZ_n$ を共に $a \in \ZZ_n$と互いに素な整数とし、$$\begin{align}
ax &\equiv xa = 1 \pmod n, \\
ax’ &\equiv x’a = 1 \pmod n
\end{align}$$をみたすとすると、$$x’ \equiv x’\cdot 1 \equiv x’\cdot(ax) \equiv (x’a)\cdot x \equiv 1\cdot x \equiv x \pmod n$$となる。よって、$x \in \ZZ_n$ はただ一つ存在する。

定理 2-1 の存在性の証明 (前編)

次に、定理 2-1 の解の存在を証明します。このシリーズは RSA 暗号の理解を最終目標としていますので、その近道となるような証明をしていきます。

最大公約数 (GCD)

まず、二つの正の整数 $a,$ $b$ の最大公約数 (Greatest Common Divisor: GCD) を考えます。これを $\gcd(a, b)$ と表記します。

定義 2-1 (最大公約数: GCD)

二つの正の整数 $a,$ $b$ の最大公約数 $\gcd(a, b)$ は $a,$ $b$ を割り切る最大の正の整数である。$d = \gcd(a, b)$とおくと、$\gcd(a’, b’) = 1$ となる正の整数 $a’,$ $b’$ が存在して, $$a = da’,\ \ b = db’$$が成り立つ。

例を一つ挙げますと、$\gcd(72, 27) = 9$ となります。$9$ は $72$ と $27$ を割り切る最大の正の整数です。
以下、$\gcd(a, b)$ に関して、つねに $a \geq b$ が成り立つと仮定します (一般性は失いません)。さらに、$\gcd(a, 0) = a$ と定義します。他の本やウェブサイトにあたるときは注意してください。
「互いに素」という用語もここでちゃんと定義してしまいましょう。

定義 2-2 (互いに素な整数)

二つの正の整数 $a,$ $b$ に対して、$\gcd(a, b) = 1$ が成り立つとき、それらを互いに素という。

さて、GCD を定義をしましたので早速次の定理を証明します。

定理 2-2

正の整数 $a,$ $b$ に対して、$r = a \bmod b$ とおくと、$$\gcd(a, b) = \gcd(b, r)$$が成り立つ。

自分で証明したい方はここでスクロールを止めてください。下に証明を示します。

定理 2-2 の証明

まず、$d = \gcd(a, b)$とおく。また、正の整数 $a$ を正の整数 $b$ で割ったときの商と余りをそれぞれ $q,$ $r$ とおくと、$$a = bq + r\ \ (0 \leq r < b)$$が成り立つ。互いに素な整数 $a’,$ $b’$ を用いて、$a = da’,$ $b = db’$ と表わせるから、$$d = \gcd(a, b) = \gcd(bq + r, b) = \gcd(db’q + r, db’)$$となる。したがって、$da’ = db’q + r$ となるから、$r$ も $d$ の倍数であり、$\gcd(a, b) \leq \gcd(b, r)$が成り立つ。一方、$d’ = \gcd(b, r)$ とおくと、$$d’ = \gcd(b, r) = \gcd(b, a – bq)$$が成り立つ。同様の議論により、 $\gcd(a, b) \geq \gcd(b, r)$ がいえる。よって、$\gcd(a, b) = \gcd(b, r)$ が成り立つ。

先ほど、$\gcd(a, 0) = a$ と定義したおかげでシンプルに証明できました。

ユークリッドの互除法 (Euclidean Algorithm)

定理 2-2 は $\gcd(a, b)$ の効率的な求め方のヒントを示しています。次に $\gcd(a, b)$ を求めるユークリッドの互除法 (Euclidean Algorithm) と呼ばれる有名なアルゴリズムを示します。

定義 2-3 (ユークリッドの互除法)

正の整数 $a,$ $b$ $(a \geq b)$ を入力とする手続き $P_1(a, b)$ を次のように定める。

1. $a_0 \sets a,$ $a_1 \sets b$ とおく。

2. $a_{n + 1} = 0$ となるまで、$a_{i + 1} \sets a_{i – 1} \bmod a_i$ とおく。

3. $a_n$ を出力する。

このとき、$a_n = \gcd(a, b)$ である。

ユークリッドの互除法が正しく $\gcd(a, b)$ を求めることは$$\gcd(a_0, a_1) = \gcd(a_1, a_2) = \dotsm = \gcd(a_{n – 1}, a_n) = \gcd(a_n, 0) = a_n$$となることからわかります。
コンピュータ上で $P_1(a, b)$ などの手続き (アルゴリズム) を実行する際に重要になってくるのが「その手続きが現実的時間内に終了するか」ということです。絶対に答えを求められる手続きであっても、それに百万年もかかってしまうのであれば (実用的には) 意味がありません。手続きが現実的時間内に終了する保証がされていることが望ましいです。それでは次の問題にチャレンジしてみましょう。

問題 2-1

定義 2-3 の手続き $P_1(a, b)$ における整数 $n$ が $$n \leq a_0$$をみたすことを示せ。

ここでは二つ証明を与えておきます。

問題 2-1 の解答

商と余りの定義から、$i \geq 2$ に対して、$0 \leq a_{i} < a_{i - 1}$ となる。したがって、$$0 = a_{n+1} < a_n < a_{n - 1} < \dotsm < a_1 \leq a_0$$が成り立つ。数列 $\{a_i\}$ はすべて整数だから有限数列である。もし、$a_0 = a_1$ であれば、$n = 1 \leq a_0$ である。そうでない場合、$n < a_0$ となる。よって、$n \leq a_0$ が成り立つ。

余りの性質を用いると比較的簡単に示すことができました。もう少し厳密な証明を与えておきます。

問題 2-1 の解答 (別解)

$n = 1$ のときは明らか。$1 \leq i \leq n$ のとき、$$\begin{align}
a_{i+1} &= a_{i-1} – a_iq_i \\
&\leq a_{i – 1} – a_i\cdot 1 \\
&= a_{i – 1} – a_i
\end{align}$$より、$1 \leq i \leq n$ に対して、$$a_{i-1} = a_i + a_{i + 1}$$が成り立つとき、ステップ数 $n$ が最大になる。これは数列 $\{a_i\}$ がフィボナッチ数列$$\begin{align}
f_0 &= 0,\ \ f_1 = 1, \\
f_{i+2} &= f_{i+1} + f_i\ \ (i \geq 0)
\end{align}$$の最初の $(n + 1)$ 項を逆順に並べたものに一致する。すなわち、$0 \leq i \leq n + 1$ に対して、$$a_i = f_{n+1-i}$$が成り立つ。実数 $\phi$ を黄金比 $$\phi = \frac{1 + \sqrt{5}}{2}$$ とすると、$i \geq 1$ に対して、$$\phi^{i-1} \leq f_i \leq \phi^i$$が成り立つ ($\{f_i\}$ の一般項を考える)。また、$\phi^2 = \phi + 1$ より、$n \geq 2$ に対して$$\begin{align}
a_0 &= f_{n+1} \\
&= f_n + f_{n-1} \\
&\geq \phi^{n-1} + \phi^{n-2} \\
&= \phi^{n-2}(\phi + 1) \\
&= \phi^{n-2}\cdot\phi^2 \\
&= \phi^n
\end{align}$$が成り立つ。よって、両辺底が $\phi$ の対数をとると、$$n \leq \log_{\phi} a_0 \leq a_0$$となる。

$\phi < 2$ より、$a = a_0$ を $2$ 進表記で $m$ 桁の整数とすると、$2^{m - 1} \leq a_0 < 2^m$ をみたしますから、$$n \leq \log_{\phi} a_0 < \log_2 a_0 < m$$となって、手続き $P_1(a, b)$ が $m$ 回未満の割り算で終了することがわかります。これはかなり効率がよいアルゴリズムといえます。アルゴリズムが終了するかという問題に興味を持った方は「コラッツ予想 (Collatz conjecture)」や「竹内関数」、「停止性問題」などを調べてみると面白いかもしれません。最後の問題は私もいま勉強中です。

次回予告

次回は今回扱ったユークリッドの互除法を拡張し、定理 2-1 の存在性を証明します: RSA暗号の数学その3 拡張ユークリッドの互除法。

この記事のキーワード

数学

Facebook Twitter

はじめに