拡張ユークリッド互除法
Latest Author anta /Date 2015-06-12 23:45:31 / Views 6680拡張ユークリッド互除法 (Extended Euclidean algorithm) とは、整数上や多項式上(より一般にユークリッド環上)において、が与えられたときとなるを見つけるアルゴリズムである。
その式を解くのに使えるだけでなく、様々なことに使うことができる。計算途中の状態にも良い特徴があり、使うことができる。これは連分数展開と密接な関係にある。
性質
- 計算途中の値の絶対値はの絶対値以下になる。この性質により、オーバーフローは心配しなくてもよい。
Applications
逆元を求める
整数が与えられたとき、となるを求めたいとする。 の場合、このようなは存在しないことがわかる。 そうでない場合、拡張ユークリッドの互除法によってとなるが求められるが、このはとなる。 これによって逆元が求められた。
この方法は多項式上などでも使うことができる。
中国人剰余定理と線形合同方程式
線形合同方程式の解を求めるのにも、逆元を求めるのと同じように考えれば使うことができる。
Rational reconstruction
がある程度小さいことがわかっているとき、の値からを復元できる。 多項式に対しても同様の復元(この場合は Rational function reconstruction)ができる。
少数展開から分数を復元する
rational reconstructionと同じように、がある程度小さいことがわかっているとき、の少数展開の最初の一部分からを復元できる。
その他、面白い利用法がいくつかある。参考文献などを参考のこと。
参考文献
- Shoup, Victor. A computational introduction to number theory and algebra. Cambridge university press, 2009.