最大公約数・最小公倍数・ユークリッドの互除法

ホームアルゴリズム入門講座 > 最大公約数・最小公倍数・ユークリッドの互除法

最大公約数・最小公倍数・ユークリッドの互除法

関連性

RSA暗号化アルゴリズムの証明の際に、「拡張版ユークリッドの互除法」を使って秘密鍵を得るといいました。その時に、φ(n) = (p - 1) * (q - 1) でもよいが、最小公倍数をとった方が数が少なくなるので効率的だ、とも言いました。

このページで紹介するのは最終的には、最小公倍数の求め方です。ですが、最小公倍数は最大公倍数から簡単に得ることができます。そして、最大公約数はユークリッドの互除法によって簡単に得ることができます。

これはアルゴリズム入門講座の第1部でやった分割統治法に似ています。最小公倍数を直接求めるのではなく、十分に解決が容易である問題に分けて、そこから復元していくという方法です。そして、ユークリッドの互除法は最古のアルゴリズムとしても有名です。

ユークリッドの互除法

ユークリッドの互除法を簡単に言い表せば「余りで割る」ということです。しかも繰り返し、「余りで割る」ことができなくなるまでです。その時は、当然「余りが0」のときであり、「割り切れたとき」です。

具体的に数値でやってみます。

p = 15439
q = 3511
のとき、(p - 1) と (q - 1) の最大公約数を求める

m = p - 1 = 15438
n = q - 1 = 3510
とする

m % n = 1398
ここで、m = 3510, n = 1398 とする
m % n = 714
ここで、m = 1398, n = 714 とする
m % n = 684
ここで、m = 714, n = 684 とする
m % n = 30
ここで、m = 684, n = 30 とする
m % n = 24
ここで、m = 30, n = 24 とする
m % n = 6
ここで、m = 24, n = 6 とする
m % n = 0

余りが 0 になった時点の n は 6 
よって、最大公約数は 6

実際に 6 で割れるかどうかを試してみてください。このとき、6 という数字は 2 * 3 ですから、2でも3でも割れたらいいのです。その場合は「偶数である」ことと「各位の和が3の倍数」であればいいのです。

15438 と 3510 はともに偶数である。

1 + 5 + 4 + 3 + 8 = 21
3 + 5 + 1 + 0 = 9

いずれも3の倍数である。
よって、2の倍数であり、3の倍数でもあるから、6の倍数である。

ユークリッドの互除法は極めて高速に最大公約数を求めることができます。また、このアルゴリズムをソースコードとして実装することも非常に簡単です。素因数分解で求めることもできますが、素因数分解は基本的に困難な問題です。素因数分解が困難であることが、RSA暗号化の安全性の根拠になっているくらいです。

なお、p - 1 と q - 1 ではなく、間違えて p, q でやったら 1 が出力されます。最大公約数が 1 というのは、互いに素であるということです。その場合の最小公倍数は p * q になります。その理由はあとで自然と分かるでしょう。

ソースコード

public static long Gcd(long m, long n)
{
	long temp;
	while (m % n != 0)
	{
		temp = n;
		n = m % n;
		m = temp;
	}
	return n;
}

ユークリッドの互除法はこのように簡潔に表すことができます。常に「m を n で割る」ことができるように、値を入れ替えています。割り終わったら、m は不要ですが、n は次「割られる数」になりますから必要です。

まず、「割る数」である n を temp に一時保存します。そして、「割った余り」を次の「割る数」である n にセットします。最後に、一時保存しておいた前の「割る数」 n を次の「割られる数」である m にセットします。

ここでは、大きな数も想定して、long型を使っています。ただし、p - 1, q - 1 などの処理はしていませんから、RSA暗号化でこれを使う場合は当然 p - 1 と q - 1 を渡す必要があります。

なお、p,q の大小関係は関係ありません。小さな数を大きな数で割った場合、商が 0 で余りは小さな数ですから、自動的に逆転するようになっています。ただし、おそらく1回だけ繰り返す回数は増えるでしょう。

最小公倍数

最小公倍数は最大公約数が分かっていれば極めて簡単に求めることができます。

(最小公倍数) = m * n / (最大公約数)

これは最小公倍数と最大公約数をひっくりかえしても成立します。今回は最小公倍数を求めたいので意味はありませんが。

ソースコード

public static long Lcm(long m, long n)
{
	return m * n / Gcd(m,n); 
}

これは最小公倍数を求めるメソッド「Lcm()メソッド」ですが、その中から最大公約数を求めるメソッド「Gcd()メソッド」を呼び出していることに注目してください。こうすることで、実際にRSA暗号の秘密鍵を得るときには、あたかもGcd()は関係ないかのように、Lcm()にアクセスするだけで十分です。