拡張ユークリッド互除法.html

<title>拡張ユークリッド互除法</title>
<p>拡張ユークリッド互除法 (Extended Euclidean algorithm) とは、整数上や多項式上(より一般にユークリッド環上)において、$a, b$が与えられたとき$ax + by = \gcd(a, b)$となる$x, y$を見つけるアルゴリズムである。</p>
<p>その式を解くのに使えるだけでなく、様々なことに使うことができる。計算途中の状態にも良い特徴があり、使うことができる。これは連分数展開と密接な関係にある。</p>
<h3>性質</h3>
<ul>
<li>計算途中の値の絶対値は$a, b$の絶対値以下になる。この性質により、オーバーフローは心配しなくてもよい。</li>
</ul>
<h2>Applications</h2>
<h3>逆元を求める</h3>
<p>
整数$b &gt; 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$となる。
これによって逆元が求められた。
</p>
<p>この方法は多項式上などでも使うことができる。</p>
<h4>中国人剰余定理と線形合同方程式</h4>
<p>線形合同方程式の解を求めるのにも、逆元を求めるのと同じように考えれば使うことができる。</p>
<h3>Rational reconstruction</h3>
<p>
$a, b$がある程度小さいことがわかっているとき、$\frac{a}{b} \bmod p$の値から$a, b$を復元できる。
多項式に対しても同様の復元(この場合は Rational function reconstruction)ができる。
</p>
<h3>少数展開から分数を復元する</h3>
<p>rational reconstructionと同じように、$a, b$がある程度小さいことがわかっているとき、$\frac{a}{b}$の少数展開の最初の一部分から$a, b$を復元できる。</p>
<p>その他、面白い利用法がいくつかある。参考文献などを参考のこと。</p>
<h3>参考文献</h3>
<ul>
<li>Shoup, Victor. A computational introduction to number theory and algebra. Cambridge university press, 2009.</li>
</ul>