アルゴリズム論特論（塩田）第4回 (3) 拡張ユークリッドアルゴリズムの計算量
拡張ユークリッドアルゴリズムの計算量
拡張ユークリッドアルゴリズムの計算量は、ユークリッドのアルゴリズムと同じです：
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}$ ( $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$ オーダーだということです。
ここ大事！