アルゴリズム論特論(塩田)第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$ オーダーだということです。 ここ大事!