Archives academic　ユークリッドの互除法

極めて高速に最大公約数を求めることができるユークリッドの互除法について。

任意の自然数の最大公約数を求めるユークリッドの互除法は整数論の中でも簡単で実用性に優れる。義務教育では最大公約数を求める方法を習うが、その方法は素因数分解をして最大公約数を求める方法だ。整数論において素因数分解は有限の間には終わるが計算に莫大な時間がかかるNP問題に属し、現代の暗号化通信もこの素因数分解の難解さに基づいている。それに比べ互除法は簡単なステップで確実に最大公約数を求めることができる。

算法

この優れたアルゴリズムは簡単な計算で行える。

最大公約数を求めたい2数を大きいほうをa,小さいほうをbとする
a÷bを行う
"余り"が0ならbが最大公約数になる
"余り"が0以外ならbと"余り"をaとbに置き換えて2へ戻る

以上の作業を余りが0になるまで繰り返せば確実に最大公約数を求めることができる。これは除算の繰り返しなので収束が速く、ラメの定理によれば2数がどんな数であっても最悪の場合でも2数のうち小さいほうの桁数の5倍の計算ステップで完了する。もし素因数分解でやろうとすると桁数が1桁上がるごとに計算コストが10倍になってやってられない。

プログラム例

互除法は手計算には向かない。以下にJavaScriptによる簡単なプログラムの例を挙げる。ページの最後にCによるプログラム例も残してある。

<script type="text/javascript">
<!--
function eu_test(Number1 , Number2)
{
/*      var Number1 = 9529190;
        var Number2 = 7712525;*/
        var m,n,i,r;
        var debug = String();
        i = 0;
        
        if(Number1 < Number2)
        {
                m = Number2;
                n = Number1;
        }else{
                m = Number1;
                n = Number2;
        }
        debug +=  "Input:"+ m +" \n";
        debug +=  "Input:"+ n +" \n";
        
        while( true )
        {
                i++;
                r = m%n;
                debug +=  m+" % "+n+" = "+r+" \n";
                if( r==0 )break;
                else{
                        m = n;
                        n = r;
                }
        }
        debug += "最大公約数 : "+ n +"\n";
        debug += "計算ステップ : "+ i +"\n";
        return [n,debug];
}
document.write("<pre>", eu_test(9529190,7712525)[1] ,"</pre>");
//-->
</script>

これをそのまま実行すると12回のステップで最大公約数5が求められる。

高速化

そのままでも十分に速い互除法だが、さらに高速化できる。

互除法では余りが次の除数になるので余りをできるだけ小さくしたほうが計算効率がいい。そこで、計算した結果余りが除数の1/2よりも大きければ余りがマイナスになってもいいから商を1増やす。こうすると余りの絶対値は確実に除数の半分以下になる。計算の際マイナスは無視してよい。

これを加え先ほどの例に追加してみる。1行追加するだけいい。

<script type="text/javascript">
<!--
function eu_test(Number1 , Number2)
{
/*      var Number1 = 9529190;
        var Number2 = 7712525;*/
        var m,n,i,r;
        var debug = String();
        i = 0;
        
        if(Number1 < Number2)
        {
                m = Number2;
                n = Number1;
        }else{
                m = Number1;
                n = Number2;
        }
        debug +=  "Input:"+ m +" \n";
        debug +=  "Input:"+ n +" \n";
        
        while( true )
        {
                i++;
                r = m%n;
                debug +=  m+" % "+n+" = "+r+" \n";
                if( r==0 )break;
                else{
                        if(n/2 < r)r = n-r;
                        m = n;
                        n = r;
                }
        }
        debug += "最大公約数 : "+ n +"\n";
        debug += "計算ステップ : "+ i +"\n";
        return [n,debug];
}
document.write("<pre>", eu_test(9529190,7712525)[1] ,"</pre>");
//-->
</script>

実行してみると先ほどは12回の計算が必要だったがこれは10回で済んだ。この方法だと最大で50％以上計算ステップを節約できる。

JavaScriptプログラム

好きな数値を入力してボタンを押すだけで実行される定例の実践版。

付録(1):最小公倍数

最小公倍数は最大公約数が求められれば一発。2数をa,bとし、最大公約数をqとおくと最小公倍数はab/qで求められる。

付録(2):3数以上の最大公約数

3数をa,b,cとし最大公約数{a,b,c}は{{a,b},c}に変換できる。先にa,bの最大公約数を求め、その最大公約数とcとの最大公約数を求めれば3数の最大公約数になる。

追記

互除法は未知数が2つ以上ある不定方程式を解くのにも利用される。aとbの最大公約数をcとしたとき、入力a,bによってただ一つのcが求まる。つまりc=ax+byとなるx,yがあり、実際に求めることができる。特にaとbがお互いに素であるときには1=ax+byとなるx,yを短時間で計算できる。というかこっちのほうがむしろ利用されているのだが、単調な式変形ばかりになるのでここでは説明しない。(もう少し理解が進めばできるかも)

付録(3):Cによるプログラム例

2005/11/23

サンプルをJavaScriptに差し替える際に残しておいたCプログラム例

normal

#include <stdio.h>

int main(void){
        
        long Number1;
        long Number2;
        long m;
        long n;
        long r;
        int i = 0;
        
        Number1 = 9529190;
        Number2 = 7712525;
        
        if(Number1 < Number2){
                m = Number2;
                n = Number1;
        }else{
                m = Number1;
                n = Number2;
        }
        
        while(1){
                i++;
                r = m % n;
                printf("%ld %% %ld = %ld \n", m, n, r);
                if(r==0){
                        break;
                }else{
                        m = n;
                        n = r;
                }
        }
        
        printf("最大公約数 : %ld\n", n);
        printf("計算ステップ : %d\n", i);
        return 0;
}

Fast

#include <stdio.h>

int main(void){
        
        long Number1;
        long Number2;
        long m;
        long n;
        long r;
        int i = 0;
        
        Number1 = 9529190;
        Number2 = 7712525;
        
        if(Number1 < Number2){
                m = Number2;
                n = Number1;
        }else{
                m = Number1;
                n = Number2;
        }
        
        while(1){
                i++;
                r = m % n;
                printf("%ld %% %ld = %ld \n", m, n, r);
                if(r==0){
                        break;
                }else{
                        if(n/2 < r)r = n-r;
                        m = n;
                        n = r;
                }
        }
        
        printf("最大公約数 : %ld\n", n);
        printf("計算ステップ : %d\n", i);
        return 0;
}

ユークリッドの互除法

算法