ユークリッドの互除法

世界最古に発見されたアルゴリズムのひとつとして知られるユークリッドの互除法は, 歴史上の価値のみならず, 公約数という素因数が絡む計算を素因数分解せずに効率的に求めることができるという点で非常に有用な手法となっています.

ユークリッドの互除法とは, 2つの0ではない整数a, b に対して, 次の手続を繰り返すことで ab の最大公約数を求めることができます.

  1. b=0 ならば a が求めるべき最大公約数である. アルゴリズムはここで終了する.
  2. c≡a (mod b) を計算し, ab を代入, bc を代入する.
  3. 最初に戻る.

ラメの定理により, アルゴリズムの繰り返し回数は a, b のうち小さい方の 10 進桁数を d とすれば, 高々 5d 回となることが知られており, 5d 回程度の繰り返しが発生する例はフィボナッチ数列(最初の2項を1としたもの)の隣接2項を対象とした場合が知られています.

もしも, これを素因数分解で解決しようとすると, a, b のうち小さい方の正の平方根の数だけ「試しに割り算して割り切れるかを確かめる」作業が必要となります。

つまり, abのもとで割算の回数を比較すると, ユークリッドの互除法ならば 2.2log(b), 素因数分解するなら √b と見積もることができます. b が大きい場合, どちらの方が効率がいいのかは明らかです.

この方法を拡張すると不定方程式 ax+by=gcd(a,b) の整数解を導出することができます. これが拡張されたユークリッドの互除法です. 拡張されたユークリッドの互除法の手順は次のとおりです.

  1. r0=a, s0=1, t0=0, r1=b, s1=0, t0=1, i=1 とする.
  2. ri+1=ri-1-qiri を 0≤ri+1≤abs(ri), qi は整数となるように定める.
  3. si+1=si-1-qisi, ti+1=ti-1-qiti とする.
  4. ri+1=0 の場合は x=si, y=ti であるので計算を終了する. ri+1≠0 の場合は次の項目に進む.
  5. i に 1 を加えて 2. の項目へ戻る.

ユークリッドの互除法の使用例