拡張版ユークリッドの互除法

ホームアルゴリズム入門講座 > 拡張版ユークリッドの互除法

拡張版ユークリッドの互除法

よくある問題

ところで問題です。29リットル入るバケツと17リットル入るバケツがあります。この2つのバケツを使って、別のバケツに1リットルの水を入れなさい。

頭の軟らかさを競うテレビ番組でおなじみですね。これが蚊取り線香になったり縄になったりしますが、すべて同じ問題です。この問題は頭の軟らかさは関係がありません。ユークリッドの互除法を知っているかどうかで決まります。知識の問題です。多くの場合、「頭のやわらかさ」というのは宣伝文句であり、そこにはなにがしかの法則・アルゴリズムが存在します。

この問題の本質は、以下の数式で表すことができます。

29x + 17y = 1
となる(x,y)の組を見つけること

このとき、(x,y)のどちらかは必ず負です。当たり前ですが。

拡張版ユークリッドの互除法の実際

ちょっと気づいてほしいのですが、もし、この問題が正しいのならば、全ての数は 29 と 17 で表すことができます。

29x + 17y = 1
となる整数(x,y)が存在するなら、整数 c を表したいとき、両辺を c 倍すればいい

29xc + 17yc = c

だったら、29 と 17 も同じようにして表してみます。

29*1 + 17*0 = 29
29*0 + 17*1 = 17

これはずいぶん見にくいですね。左辺の 29 と 17 は固定ですから、文字に置き換えます。

a = 29, b = 17 とおく

1a + 0b = 29
0a + 1b = 17

バケツの問題を解くには、右辺が 1 になればいいんです。だったら、引いてみますか? 面倒なので、何度も何度も引いて、1になるまでやってみればいいでしょう。

 1a + 0b = 29 ・・・ (1)
 0a + 1b = 17 ・・・ (2)
 1a - 1b = 12 ・・・ (3) = (1) - (2)

 0a + 1b = 17 ・・・ (2)
 1a - 1b = 12 ・・・ (3)
-1a + 2b =  5 ・・・ (4) = (2) - (3)

[-2a + 4b = 10 ・・・ (5) = (4) * 2  (12 / 5 = 2 ・・・ 2なので 2 倍した) ]

 1a - 1b = 12 ・・・ (3)
-2a + 4b = 10 ・・・ (5)
 3a - 5b =  2 ・・・ (6) = (3) - (5)
 
[ 6a - 10b = 4 ・・・ (7) = (6) * 2 (5 / 2 = 2 ・・・ 1なので 2 倍した) ]

-1a + 2b =  5 ・・・ (4)
 6a - 10b = 4 ・・・ (7)
-7a + 12b = 1 ・・・ (8) = (4) - (7)

答えが出ました。「17リットルのバケツで12回くみ入れた後、29リットルのバケツで7回くみ出す」です。

拡張版ユークリッドの互除法のアルゴリズム

式を何気なく引いていっただけですが、これが拡張版ユークリッドの互除法です。これからより厳密なアルゴリズムを説明します。RSA暗号で使うのは2つの数が互いに素なときですから、その場合に限定します。

互いに素な数 a,b が与えられたとき、
ax + by = 1
となる(x,y)の組を発見する方法

まず、基本となる式を2つ用意する
a(x1) + b(y1) = z1 ・・・ (1)
a(x2) + b(y2) = z2 ・・・ (2)

初期値として、以下の値を代入する
(x1,y1,z1) = (1,0,a)
(x2,y2,z2) = (0,1,b)

z1 を z2 で割った余りを q とする
q = (z1 - (z1 % z2)) / z2

(2) を q 倍して (1) から引く
a(x1 - (q * x2)) + b(y1 - (q * y2)) = z1 - (q * z2) ・・・ (3)

(2)を新たな(1)とし、(3)を新たな(2)とし、右辺が 1 になるまで繰り返す

文字を使って書くとわかりにくくなりますが、やっていることは上の例と同じです。上の例では商が1のとき、わざわざ q を書いていません。

拡張版ユークリッドの互除法の実装

using System;

namespace NewWorld
{
	class MainClass
	{
		public static void Main(string[] args)
		{
			long p = 29;
			long q = 17;
			Console.WriteLine("PrivateKey = {0}",GetPrivateKey(p,q));
		}
		// ax + by = 1 (x,y)
		public static long GetPrivateKey(long a, long b)
		{
    		long x1,x2,y1,y2,z1,z2,q,t;
    		x1 = 1;
    		y1 = 0;
    		z1 = a;
    		x2 = 0;
    		y2 = 1;
    		z2 = b;
    		
    		while(z2 != 1)
    		{
    			if (z2 == 0) break;
    			q = (z1 - (z1 % z2)) / z2;
    			Console.WriteLine("{0}a + {1}b = {2}",x1,y1,z1);
    			x1 = x1 - (q * x2);
    			y1 = y1 - (q * y2);
    			z1 = z1 - (q * z2);
    			
    			t = x1;
    			x1 = x2;
    			x2 = t;
    			
    			t = y1;
    			y1 = y2;
    			y2 = t;
    			
    			t = z1;
   				z1 = z2;
   				z2 = t;
    		}
    		
    		if (y2 < 0)
    		{
    			Console.WriteLine("({0},{1})",x2-b,y2+a);
    			return y2 + a;
    		}
    		else
    		{
    			Console.WriteLine("({0},{1})",x2,y2);
    			return y2;
    		}
		}
	}
}

これが秘密鍵を得るメソッドで、拡張版ユークリッドの互除法を実装しています。内容は上のアルゴリズムと全く同じです。

これによって得られた秘密鍵 d は、p - 1 と q - 1 の最小公倍数 l を法とする世界において、e と逆数の関係にあることはすでに説明しました。

d * e = 1 (mod l)

d * e = l * x + 1
移項して
-l * x + e * d = 1
l * (-x) + e * d = 1
(l,e) を (a,b), (-x,d) を (x,y) と表すと、
a * x + b * y = 1

求めるのは、d ですから、置き換えた後の y になります。yが負の場合は l を足すのでした。これも、図で説明したはずです。