このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

目次

はじめに

 2つの整数の最大公約数(GCM)を求めるもっとも素朴な方法は、2,3,5,…とmin(a,b)以内の素数について割っていくことである。割った結果、2つの整数が割り切れれば、その公約数にはその素数が含まれるということを意味する。つまり、最大公約数はこうした素数のすべての掛け合わせたものである。このアルゴリズムは次の通りである。

  • Input:A,B(10進数の整数)
  • Output:GCM(AとBの最大公約数)
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
GCM=1
if min(a,b)≦2 then
    exit
while 2|a ∧ 2|b do
    a = a/2
    b = b/2
    GCM = GCM*2
if min(a,b)≦3 then
    exit
while 3|a ∧ 3|b do
    a = a/3
    b = b/3
    GCM = GCM*3
if min(a,b)≦5 then
    exit
while 5|a ∧ 5|b do
    a = a/5
    b = b/5
    GCM = GCM*5
…(min(a,b)以下の素数についてすべて同様に考える)…

 ところが、このアルゴリズムでは、min(a,b)以下のすべての素数のリストを用意しておかなければならない。これを解決するアルゴリズムのひとつがユークリッドの互除法である。

ユークリッドの互除法

 ユークリッドの互除法では、素数を用意せずとも、どんな数の最大公約数でも求めることができる。2,000年以上前にユークリッドによって発見されたアルゴリズムである。もっとも基本的なアルゴリズムともいえる。

 ユークリッドの互除法のアルゴリズムは次の通りである。

  • Input:a,b(0以上の整数)
  • Output:(a,b)(aとbの最大公約数)
  1
  2
  3
  4
  5
  6
  7
  8
r[-2]←a,r[-1]←b,n←0
if r[n-1]=0 then
    output r[n-2]
    return
else
    r[n]←r[n-2]%r[n-1]
    n←n+1
    goto 2行目

例:a=21,b=14の最大公約数(a,b)をユークリッドの互除法を使って求める。

  • n:カウンターのn
  • qn:rn-2÷rn-1の余り
nqnrn
-221
-114
017
120
2

 黄色の部分が初期値の入力である。出力結果は、水色のように0となった個所のひとつ上である。よって、赤色が最大公約数であり、これが出力される。

(21,14)=7

 このように素因数分解をせずに単に割り算をするだけで、最大公約数が求められるわけである。

Javaによる実装

Everything is expanded.Everything is shortened.
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 
 
 
 
 
 
-
|
-
|
|
|
|
-
-
|
|
|
|
|
|
|
|
|
-
|
|
-
|
|
!
|
|
-
|
!
|
|
|
|
-
|
|
|
!
|
|
|
|
|
|
|
|
|
!
!
!
/*
 * ユークリッドの互除法で最大公約数(GCM)と最小公約数(LCM)を求める
 * 入力:2つの整数
 * 出力:最大公約数
 */
import java.io.*;
public class EuclidGCM {
 
    public static void main(String[] args){
        int a=0,b=0;
        
        //整数を入力する
        BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
        while(true){
            try{
                String line;
            
                System.out.println("整数a:");
                line=rd.readLine();
                a=Integer.parseInt(line);
            
                System.out.println("整数b:");
                line=rd.readLine();
                b=Integer.parseInt(line);        
            }catch(IOException e){
                System.out.println("入力エラー");
                return;
            }catch(NumberFormatException e){
                System.out.println("整数を入力してください。");
                continue;
            }
        
            //aまたはbが0なら終了する
            if(a==0 || b==0){
                break;
            }
        
            //aとbを保存しておく。
            int sa=a,sb=b;
            //割り切れるまで繰り返す。
            while(b != 0){
                int r = a%b;
                a=b;
                b=r;
            }
            
            //最小公約数を求める
            int lcm = sa * sb / a;
        
            //最大公約数を表示する。
            System.out.println(sa + "と" + sb + "の最大公約数は" + a + "です。");
            //最小公約数を表示する。
            System.out.println(sa + "と" + sb + "の最小公約数は" + lcm + "です。");
            
        }
    }
}

 大整数におけるユークリッドの互除法のプログラム(bigeuclid.java)を次に示す。

Everything is expanded.Everything is shortened.
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 
 
-
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
-
|
|
|
!
|
!
!
import java.io.*;
import java.math.BigInteger;
public class bigeuclid{
    public static void main(String[] args) throws Exception{
        BigInteger a,b,r,a1,b1;
 
        System.out.println("正の整数a,bを入力せよ。");
        InputStreamReader in = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(in);
 
        System.out.print("Input a = ");
        String s1=br.readLine();
        a = new BigInteger(s1);
 
        System.out.print("Input b = ");
        String s2=br.readLine();
        b = new BigInteger(s2);
 
        a1=a;
        b1=b;
 
        // bが0でないならば
        while(b.equals(BigInteger.valueOf(0)) == false){
            r=a.remainder(b);    // mod(a,b)
            a=b;
            b=r;
        }
        System.out.println("GCD(" + a1 + "," + b1 +")=" + a.toString());
    }
}

ユークリッドの互除法における繰り返し回数

 ユークリッドの互除法を求めるときの表に着眼する。qnの列がすべて1になるとき、即ち「∀n;qn=1」のとき、繰り返し回数が一番多い。そのときの式は次のようになる。

r_{n-2}~=~r_{n-1}~+~r_n

 これはちょうどフィボナッチ数を定義する漸化式を逆順にしたものになっている。よって、互除法における繰り返し回数(lとする)の上限は次の不等式によって表される。ここで\theta~=~\frac{1~+~\sqrt{5}}{2}とする(このθは黄金比である*1)。

l
<~\frac{\log~b}{\log~\theta}~+~1
<~1.4~\log~b~+1

 よって、繰り返し回数lはbの桁数程度ということを意味する。

参考文献

  • 講義ノート
  • 『I/O BOOKS Javaによる暗号理論入門』
  • 『Eclipseによる体験学習 Javaではじめるアルゴリズム入門』


*1 1:θ=θ:1-θを満たす