拡張ユークリッド互除法 (Extended Euclidean algorithm) とは、整数上や多項式上(より一般にユークリッド環上)において、$a, b$が与えられたとき$ax + by = \gcd(a, b)$となる$x, y$を見つけるアルゴリズムである。

その式を解くのに使えるだけでなく、様々なことに使うことができる。計算途中の状態にも良い特徴があり、使うことができる。これは連分数展開と密接な関係にある。

性質

• 計算途中の値の絶対値は$a, b$の絶対値以下になる。この性質により、オーバーフローは心配しなくてもよい。

Applications

逆元を求める

整数$b > 0, a$が与えられたとき、$ax \equiv 1 \pmod b$となる$x$を求めたいとする。 $\gcd(a, b) \neq 1$の場合、このような$b$は存在しないことがわかる。 そうでない場合、拡張ユークリッドの互除法によって$ax + by = 1$となる$x, y$が求められるが、この$x$は$ax \equiv 1 \pmod b$となる。 これによって逆元が求められた。

この方法は多項式上などでも使うことができる。

中国人剰余定理と線形合同方程式

線形合同方程式の解を求めるのにも、逆元を求めるのと同じように考えれば使うことができる。

Rational reconstruction

$a, b$がある程度小さいことがわかっているとき、$\frac{a}{b} \bmod p$の値から$a, b$を復元できる。 多項式に対しても同様の復元(この場合は Rational function reconstruction)ができる。

少数展開から分数を復元する

rational reconstructionと同じように、$a, b$がある程度小さいことがわかっているとき、$\frac{a}{b}$の少数展開の最初の一部分から$a, b$を復元できる。

その他、面白い利用法がいくつかある。参考文献などを参考のこと。

参考文献

• Shoup, Victor. A computational introduction to number theory and algebra. Cambridge university press, 2009.