アルゴリズム論特論（塩田）第4回 (5) ユークリッドのアルゴリズム 再帰 version
ユークリッドのアルゴリズム 再帰 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 は不適切と言えましょう。