はじめに

拡張ユークリッドの互除法で逆元計算をする必要に迫られました。
非再帰のバージョンはようやく理解できたのでメモです。

拡張ユークリッドの互除法

拡張ユークリッドの互除法は、ax + by = gcd(a, b) を満たす x, y を導出するアルゴリズムです。

手順

次の絶対に成立する 2 式から開始します a * 1 + b * 0 = a ...f1 a * 0 + b * 1 = b ...f2

上記 2 式を用いて ax + by = gcd(a, b) の形を作りだすことが目的です。
説明のために f1, f2 を一般化した式 a * x(i) + b * y(i) = d(i) ...f3 を用います。

さて、導出したい式の右辺は gcd(a, b)。 与えられた 2 式の右辺はそれぞれ、a, b です。
gcd(a, b) はユークリッドの互除法から導出できます。

ユークリッドの互除法

ユークリッドの互除法では次の手順を繰り返します。 b(i+1) = b(i) - qa(i) a(i + 1) = b(i) ただし q = a // b です。

では、f3 に対して同様の変換を行い、右辺を gcd(a, b) の形にします。
式は、 q = a // b

おわりに

参考 を読んで理解したのですが、プログラムがエレガント過ぎて理解してからでないと頭に入ってきませんでした。
苦労してようやく空でプログラムを書けるくらい理解したのでメモでした。