Extended Euclidean Algorithm
拡張ユークリッドの互除法は gcd(a,b) を計算すると同時に、ax+by=gcd(a,b) を満たすベズー係数 x, y を求める。
目的
法の逆元の計算や線形ディオファントス方程式の求解に使う、数論と暗号の基礎道具。
メカニズム
ユークリッドの互除法 gcd(a,b)=gcd(b, a mod b) を遡りながら係数を維持する。逆代入で x=y_prev、y=x_prev-floor(a/b)*y_prev。計算量は O(log min(a,b))。
ユースケース
- モジュラ逆元の計算
- RSA の秘密鍵生成
- 線形ディオファントス方程式