15.3.4 拡張GCD

拡張GCD関数，GCDEXTはgcd(a,b)に加えて，a*x+b*y=gcd(a,b)を満足する余因子x と yも導出します。 通常のGCDアルゴリズムは全て拡張GCD計算に適用できます。 2進GCDアルゴリズムは単一リム用のGCDEXTにのみ適用されます。 Lehmerのアルゴリズムは，GCDEXT_DC_THRESHOLDのサイズまで適用され，それを超えるサイズに対してはGCDEXTは HGCDのループ適用を行い，余因子の導出用にテーブルを作って保存するようにします。 こうすることで，GCDやHGCDの計算時間は漸近的にO(M(N)*log(N))となります。

通常のGCDとの違いは，入力値a と bに対して減次プロセスを回す一方，余因子xとy の桁数がだんだん伸びていく所にあります。これによって計算を打ち切るポイントをどこに設定するのかが難しくなります。 現在の実装では，最初のHGCDの呼び出しに対しては入力値の半分程度の有効桁数のところで打ち切るようにし，以降の呼び出しでは 有効桁数の2/3程度に対して実行するようにしています。このやり方はまだ改良の余地があります。また，停止則についても，Lehmerのアルゴリズムを一度実行して入力値をGCDEXT_DC_THRESHOLD以下になるようにしたところで止める，というだけでなく，その時点の余因子のサイズも考慮すると改善できるのではないかなぁと思っています。