1. ユークリッドのアルゴリズムの計算量
ユークリッドのアルゴリズムは、RSA暗号をはじめ、多くの公開鍵暗号に必須のアルゴリズムです。
その計算量を把握しておきましょう。
記号は第3回（ 5月11日 ）
Alg.6 ( ユークリッドのアルゴリズム ),
Alg.9 ( 拡張ユークリッドアルゴリズム ) のとおりとします。
簡単のため、その入力 $a$, $b$ は
$a \gt b \gt 0$
を満たすと仮定します。
Lemma 1 $r_{n+2} \lt \frac{1}{2}r_n$.
大雑把に言うと、数列 $\{\,r_{n}\,\}$ は公比 $\frac{1}{\sqrt{2}}$ の等比数列以上の速さで減少してゆく、
という意味です。
証明 (i) $r_{n} \lt 2 \times r_{n+1}$ のとき：
$r_{n}$ を $r_{n+1}$ で割った商は $1$ になるので、余り $r_{n+2}$ は
$r_{n+2} = r_n - 1 \times r_{n+1} \lt r_n - \frac{1}{2} r_n = \frac{1}{2} r_n$
を満たします。
(ii) $r_{n} \geqq 2 \times r_{n+1}$ のとき：
$\{\,r_{n}\,\}$ は減少列ですから $r_{n+2} \lt r_{n+1} \leqq \frac{1}{2} r_n$.
(証明終)
Rem.2 負の余りも使うときは、もっと強く $r_{n+1} \lt \frac{1}{2} r_n$
が成り立ちます。
Lemma 3 ユークリッドのアルゴリズムのループ回数は $O(\log a)$.
証明
L'a 1 より $r_n$ は番号 $n$ が 2 増えるとビット長が 1 つ以上減ります。
従って、$r_0=a$ のビット長を $k$ とすると、
$n \leqq 2k$ の範囲でアルゴリズムの終了条件 $r_{n+1}=0$ が満たされ、
ループ回数 $\leqq 2 k = O(\log a)$.
(証明終)
Th.4 ( 緩い評価 ) ユークリッドのアルゴリズムの計算量は $O(\log^3 a)$.
証明
$\{\,r_n\,\}$ は減少列ゆえ、全ての $n$ について $r_n \leqq a$ が成り立ちます。
1回のループで用いる計算は $a$ 以下の整数の除算1回だけなので、
計算量 $=$ ループ回数 $\times$ ( 除算の計算量 ) = $O(\log a) \times O(\log^2 a) = O(\log^3 a)$.
(証明終)
本当はもっと計算量は少なくて、
Th.5 ( 詳細な評価 ) ユークリッドのアルゴリズムの計算量は $O(\log^2 a)$.
その証明の前に、除算の計算量を詳しく見ておきましょう。
Lemma 6 除算 $x \div y$ の計算量は、商を $q$ として $O(\log y \times \log q)$.
第1回の講義では大雑把に $O(\log^2 x)$ と言っていましたが、もう少し小さい、ということになります。
証明
筆算の各段は除数 $y$ の桁数の引き算で、
それを高々 ( 商 $q$ のビット長 ) 回繰り返します。
従ってその計算量は
$O$( $y$ のビット長 ) $\times$ $O$( $q$ のビット長 ) = $O(\log y) \times O(\log q) = O(\log y \times \log q)$.
(証明終)
Th.5 の証明
$r_n$ を $r_{n+1}$ で割った商を $q_n = \lfloor r_n / r_{n+1}\rfloor$ とおきます。全ての番号 $n$ で
$r_{n+2} = r_n - q_n \times r_{n+1}$
であり、特に終了時の番号 $N$ では
$0 = r_{N+1} = r_{N-1} - q_{n-1} \times r_{N}$
となっています。$n \geqq 1$ のときは
$r_n \leqq r_1 = b \lt a$
ですから
$r_n \div r_{n+1}$ の計算量 $= O(\log r_{n+1}) \times O(\log q_n) = O(\log a) \times O(\log q_n)$
アルゴリズム全体でこれを加えると
\begin{align}
\sum_{n=0}^{N-1} O(\log a) \times O(\log q_n) &= O(\log a) \times \sum_{n=0}^{N-1} O(\log q_n) \\
&= O(\log a) \times O\left(\sum_{n=0}^{N-1} \log q_n\right) \\
&= O(\log a) \times O(\log (q_0 \times \cdots \times q_{N-1})) \quad \cdots\cdots\ (\ast)\\
\end{align}
ここで、全ての番号 $n$ で
$r_n = q_n \times r_{n+1} + r_{n+2} \geqq q_n \times r_{n+1}$
が成り立ちますので
\begin{align}
a = r_0 &\geqq q_0 \times r_1 \\
&\geqq q_0 \times q_1 \times r_2 \\
&\ \ \vdots \\
&\geqq (q_0 \times \cdots \times q_{N-1}) \times r_N \\
&\geqq (q_0 \times \cdots \times q_{N-1}) \\
\end{align}
よって
$(\ast)$ の右辺 $ = O(\log a) \times O(\log a) = O(\log^2 a)$.
(証明終)
2. 拡張ユークリッドアルゴリズムの計算量
拡張ユークリッドアルゴリズムの計算量は、ユークリッドのアルゴリズムと同じです：
Th.7 拡張ユークリッドアルゴリズムの計算量も $O(\log^2 a)$.
これは次の補題を使って示します：
Lemma 8 $x_n$, $y_n$ は次の不等式を満たす：
$\displaystyle{|\,x_n\,| \lt \frac{b}{2 \times \gcd(a,b)}}$,
$\quad \displaystyle{|\,y_n\,| \lt \frac{a}{2 \times \gcd(a,b)}}$
証明 は J. A. ブーフマン「暗号理論入門―暗号アルゴリズム、署名と認証、その数学的基礎」 pp.22-23 を見てください。
( この講義の $x_n$, $y_n$ とは $\pm$ がずれていますので読むときは注意してください。)
Th.7 の証明 ユークリッドのアルゴリズムとの違いは、乗算
$q_n \times x_{n+1}$, $\quad q_n \times y_{n+1}$
も行うことですが、
L'a 8 より
$|\,x_n\,| \lt b \lt a$, $\quad y_n \lt a$
が成り立ちますので、
$q_n \times x_{n+1}$ ( $\quad q_n \times y_{n+1}$ ) の計算量の総和 = $\displaystyle{\sum_{n=0}^{N-1} O(\log q_n) \times O(\log a)}$
となって
Th.5 の証明と同じ評価ができます。(証明終)
参考 Python で組んで実行時間を計測してみました：
2000-ビット
実行時間 = 0.00500011444092
4000-ビット
実行時間 = 0.0149998664856
8000-ビット
実行時間 = 0.0539999008179
16000-ビット
実行時間 = 0.168999910355
32000-ビット
実行時間 = 0.594000101089
64000-ビット
実行時間 = 2.09999990463
128000-ビット
実行時間 = 7.8220000267
入力のビット長が 2 倍になると実行時間が約 4 倍になっています。これが、計算量が $\log^2$ オーダーだということです。
ここ大事！
3. フィボナッチ数列
「フィボナッチ数」をユークリッドのアルゴリズムに入力すると面白いことが起こります。
Def.9 漸化式
$f_0 = f_1 = 1$, $f_{n+2} = f_{n+1} + f_n$ ( $n =0, 1, \cdots$ )
で定まる数列 $\{\,f_n\,\}$ をフィボナッチ数列という。
最初の数項は
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
で与えられ、ひまわりの種の個数、アンモナイトの模様、など自然界の至る所に現れることが知られています。
フィボナッチ数列の一般項は「黄金比」で書き表すことができます。
Def.10 $\displaystyle{\phi = \frac{1 +\sqrt{5}}{2}} = 1.618\cdots$ を黄金比という。
人間が一番美しいと思う長方形の縦横比が黄金比であると言われ、
また、正五角形や正十二面体にも関わっています。
Th.11 フィボナッチ数列の一般項は
$f_n = \frac{1}{\sqrt{5}}\left\{ \phi^{n+1} - (\bar{\phi})^{n+1} \right\}
= \frac{1}{\sqrt{5}}\left\{ \left(\frac{1 + \sqrt{5}}{2}\right)^{n + 1} - \left(\frac{1 - \sqrt{5}}{2}\right)^{n + 1} \,\right\}$
代数学用語で $\bar{\phi} = \frac{1 - \sqrt{5}}{2}$ は $\phi$ の「共役」と呼ばれる数です。
Cor.12 (1) $n$ が十分大きいとき $f_n \mbox{ ≒ } \frac{1}{\sqrt{5}} \phi^{n+1}$
(2) $\displaystyle{\lim_{n \rightarrow \infty}\frac{f_{n+1}}{f_n} = \phi}$.
∵ $\bar\phi = -0.618\cdots$ は絶対値が 1 より小さいので。(証明終)
Prop.13 フィボナッチ数列の隣接する 2 項を ( 大きい方から ) ユークリッドのアルゴリズムの初期値とする：
$a = r_0 = f_N$ , $\quad b = r_1 = f_{N-1}$ .
すると $r_n$ ( $n \lt N$ ) はフィボナッチ数列を逆順に並べたものになる：
$r_n = f_{N-n}$ .
また $x_n$ ( $n \geqq 2$ ), $y_n$ ( $n \geqq 1$ ) はフィボナッチ数列の番号をずらして $\pm$ を付けたものになる：
$x_{n+2} = (-1)^n \times f_n$ , $\quad y_{n+1} = (-1)^n \times f_n$ .
実行例
フィボナッチ数列を拡張ユークリッドアルゴリズムに入力します。
N = 10
r[0] = f[10] = 89
r[1] = f[9] = 55
(r[ 0], x[ 0], y[ 0]) = ( 89, 1, 0)
(r[ 1], x[ 1], y[ 1]) = ( 55, 0, 1)
(r[ 2], x[ 2], y[ 2]) = ( 34, 1, -1)
(r[ 3], x[ 3], y[ 3]) = ( 21, -1, 2)
(r[ 4], x[ 4], y[ 4]) = ( 13, 2, -3)
(r[ 5], x[ 5], y[ 5]) = ( 8, -3, 5)
(r[ 6], x[ 6], y[ 6]) = ( 5, 5, -8)
(r[ 7], x[ 7], y[ 7]) = ( 3, -8, 13)
(r[ 8], x[ 8], y[ 8]) = ( 2, 13, -21)
(r[ 9], x[ 9], y[ 9]) = ( 1, -21, 34)
(r[10], x[10], y[10]) = ( 0, 55, -89)
(89) * (-21) + (55) * (34) = 1
N = 11
r[0] = f[11] = 144
r[1] = f[10] = 89
(r[ 0], x[ 0], y[ 0]) = ( 144, 1, 0)
(r[ 1], x[ 1], y[ 1]) = ( 89, 0, 1)
(r[ 2], x[ 2], y[ 2]) = ( 55, 1, -1)
(r[ 3], x[ 3], y[ 3]) = ( 34, -1, 2)
(r[ 4], x[ 4], y[ 4]) = ( 21, 2, -3)
(r[ 5], x[ 5], y[ 5]) = ( 13, -3, 5)
(r[ 6], x[ 6], y[ 6]) = ( 8, 5, -8)
(r[ 7], x[ 7], y[ 7]) = ( 5, -8, 13)
(r[ 8], x[ 8], y[ 8]) = ( 3, 13, -21)
(r[ 9], x[ 9], y[ 9]) = ( 2, -21, 34)
(r[10], x[10], y[10]) = ( 1, 34, -55)
(r[11], x[11], y[11]) = ( 0, -89, 144)
(144) * (34) + (89) * (-55) = 1
Rem.14 Prop.13 の状況ではループ回数は $N \mbox{ ≒ } \log_\phi a =O(\log a)$.
∵ Cor.12 (1)
Cor.15 ユークリッドのアルゴリズムの計算量の評価 $O(\log^2 a)$ は best-possible である。
best-possible は「可能な限り最良」という意味です。
計算量の評価は、
Th.4 が
Th.5 に改良できたように、
まだ改良の余地があることもあるのですが、
ユークリッドのアルゴリズムは入力がフィボナッチ数列だと本当に計算量が $O(\log^2 a)$ になりますので、
これが最良ということになります。
4. ユークリッドのアルゴリズム 再帰 version
第 3 回
L'a 5 より
$\gcd(a, b) = \gcd(b, a\,\%\, b)$
( % は剰余の記号 ) が成り立ちますから、ユークリッドのアルゴリズムは再帰的には次のように書けます：
Algorithm 16 ( ユークリッドのアルゴリズム 再帰 version )
def gcd(a, b):
if b == 0:
return abs(a)
else:
return gcd(b, a % b)
では拡張ユークリッドアルゴリズムを再帰的に書くにはどうしたらいいでしょうか。
力のある諸君は自分で考えてみましょう。
答え
入力 $a$, $b$ に対して、$d=\gcd(a,b)$ と $d=ax+by$ を満たす $x$, $y$ を返したいのですが、
入力 $b$, $a\, \%\, b$ で再帰呼び出しを掛けると、返って来るのは
$d = bX + (a\,\%\, b)Y$
を満たす $X$, $Y$ です。
ということは $(a\,\%\, b)$ を $a$ 〇 $+$ $b$ □ の形に書いておけばいい訳です。
$a \div b$ の商を $q$ とすれば $(a\,\%\, b) = a \times 1 - b \times q$ ですから
$d = bX + (a\,\%\, b)Y = bX +(a-bq)Y = aY + b(X-qY)$
すなわち
$x = Y$, $\quad y = X-qY$
で解決です。
Algorithm 17 ( 拡張ユークリッドアルゴリズム 再帰 version )
def euclid(a, b):
if b == 0:
if a >= 0:
return [q, a, 0]
else:
return [-a, -1, 0]
else:
q = a // b
d, X, Y = euclid(b, a % b)
return [d, Y, (X - q * Y)]
プログラミング上の注意
- 再帰的プログラムはメモリを大量に消費しますので、
システムやプログラミング言語の仕様・設定により、
再帰呼び出しの深さには制限が掛けられているのが普通です。
- Python では
- 再帰回数の上限を取得する関数： sys.getrecursionlimit()
- 再帰回数の上限を変更する関数： sys.setrecursionlimit()
です。
デフォルトでは上限 1000 回に設定されている処理系が多いようですが、
RSA暗号で推奨されている 2048 ビットの鍵サイズではこれでは足りません。
- そもそも、大きな暗号システムの部品として用いる為には、再帰 version は不適切と言えましょう。