RSA暗号の数学 その2 ユークリッドの互除法
カテゴリー:高校数学
はじめに
前回の記事では、RSA 暗号の数理を理解するために必要な合同式について説明しました。今回は前回の予告通り、「ユークリッドの互除法」について解説したいと思います。まだスタイルが定まっておらず統一感がありませんが、お付き合いいただける方はぜひお読みください。
定理の証明と問題の解答は載せていますが、補題の証明はありません。
目標
今回と次回で次の定理を証明します。
定理 2-1 (逆元の存在とその唯一性)
整数 \(x\) は \(\ZZ_n\) 上の \(a\) の乗法に関する逆元といえます。
時間に余裕がある方は前回省略した次の補題を証明してから進みましょう。
補題 2-1 (商と余り)
上の \(q,\) \(r\) はそれぞれ \(a / b\) の商と余りです。
定理 2-1 の唯一性の証明
まず、定理 2-1 の解の存在を仮定した上で、その唯一性を証明してしまいましょう。自分で証明したい方はここでスクロールを止めてください。
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)
例を一つ挙げますと、\(\gcd(72, 27) = 9\) となります。\(9\) は \(72\) と \(27\) を割り切る最大の正の整数です。
以下、\(\gcd(a, b)\) に関して、つねに \(a \geq b\) が成り立つと仮定します (一般性は失いません)。さらに、\(\gcd(a, 0) = a\) と定義します。他の本やウェブサイトにあたるときは注意してください。
「互いに素」という用語もここでちゃんと定義してしまいましょう。
定義 2-2 (互いに素な整数)
さて、GCD を定義をしましたので早速次の定理を証明します。
定理 2-2
自分で証明したい方はここでスクロールを止めてください。下に証明を示します。
定理 2-2 の証明
先ほど、\(\gcd(a, 0) = a\) と定義したおかげでシンプルに証明できました。
ユークリッドの互除法 (Euclidean Algorithm)
定理 2-2 は \(\gcd(a, b)\) の効率的な求め方のヒントを示しています。次に \(\gcd(a, b)\) を求めるユークリッドの互除法 (Euclidean Algorithm) と呼ばれる有名なアルゴリズムを示します。
定義 2-3 (ユークリッドの互除法)
このとき、\(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-1 の解答
余りの性質を用いると比較的簡単に示すことができました。もう少し厳密な証明を与えておきます。
問題 2-1 の解答 (別解)
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 拡張ユークリッドの互除法。