目次 †
はじめに †
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の余り
黄色の部分が初期値の入力である。出力結果は、水色のように0となった個所のひとつ上である。よって、赤色が最大公約数であり、これが出力される。
(21,14)=7
このように素因数分解をせずに単に割り算をするだけで、最大公約数が求められるわけである。
Javaによる実装 †
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
|
-
|
-
|
|
|
|
-
-
|
|
|
|
|
|
|
|
|
-
|
|
-
|
|
!
|
|
-
|
!
|
|
|
|
-
|
|
|
!
|
|
|
|
|
|
|
|
|
!
!
!
|
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;
}
if(a==0 || b==0){
break;
}
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)を次に示す。
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;
while(b.equals(BigInteger.valueOf(0)) == false){
r=a.remainder(b); a=b;
b=r;
}
System.out.println("GCD(" + a1 + "," + b1 +")=" + a.toString());
}
}
|
ユークリッドの互除法における繰り返し回数 †
ユークリッドの互除法を求めるときの表に着眼する。qnの列がすべて1になるとき、即ち「∀n;qn=1」のとき、繰り返し回数が一番多い。そのときの式は次のようになる。

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



よって、繰り返し回数lはbの桁数程度ということを意味する。
参考文献 †
- 講義ノート
- 『I/O BOOKS Javaによる暗号理論入門』
- 『Eclipseによる体験学習 Javaではじめるアルゴリズム入門』