バイナリ法

ホームアルゴリズム入門講座 > バイナリ法

バイナリ法

指数とバイナリ法

今回紹介するのは、バイナリ法という指数に関するアルゴリズムです。これは非常にパワフルなので、是非身に着けてください。

今回はバイナリ法を用いて、326 % 87 を求めてみます。これは私の好きなYUIの誕生日を組み合わせたものです。

2進法の考え方

バイナリ法は2進法の考え方をうまく利用しており、10進法の世界では使えません。一度2進法に変換してから使います。

ところで、26を2進法で表記するとどうなるでしょうか。これには、2つのやりかたがあります。

まず一般的なのが、素因数分解に近い考え方です。(もちろん素因数分解ではありません。2のべき乗分解とでもいうべきものです。)

20 = 1
21 = 2
22 = 4
23 = 8
24 = 16
であるから、
26 = 16 + 8 + 0 + 2 + 0
   = 24*1 + 23*1 + 22*0 + 21*1 + 20*0
よって、
11010

そしてもう一つが、余りを用いる方法です。こっちの方が賢いです。

26 / 2 = 13 ・・・ 0
13 / 2 = 6  ・・・ 1
6  / 2 = 3  ・・・ 0
3  / 2 = 1  ・・・ 1
1  / 2 = 0  ・・・ 1
あまりを逆から読んで、
11010

これら2つの考え方から、2つのバイナリ法が生まれます。

バイナリ法 Ver.1.0

2進法の最初の考え方は単純です。

326
= 316 + 8 + 0 + 2 + 0
= 316 * 38 * 32

32を計算し、それをさらに2乗して34、さらに2乗して38と、計算していき、最後にそれらを足すのです。

もちろん、ここで n を法とする世界ですから、この法則を使います。

a * b mod n = {(a mod n) * (b mod n)} mod n

これは指数の計算をしているときも、合計の計算をしているときも使えます。

34 mod n
= (32 * 32) mod n
= {(32 mod n) * (32 mod n)} mod n

このバイナリ法 Ver.1.0も大変効率がいいのですが、今回は使いません。実は最初、私もこいつで実装していましたが、Ver.2.0のほうが効率的であることに気付きました。

バイナリ法 Ver.2.0

バイナリ法Ver.2.0は、余りの考え方で2進法表記を試みた方です。あの考え方をもう一度整理します。

26 / 2 = 13 ・・・ 0
13 / 2 = 6  ・・・ 1
6  / 2 = 3  ・・・ 0
3  / 2 = 1  ・・・ 1
1  / 2 = 0  ・・・ 1
あまりを逆から読んで、
11010

今度は、これを逆から復元することが可能でしょうか。つまり、「11010」から「26」を同じ考え方で復元させることは可能でしょうか。試してみます。

上の式を逆から積の形に戻していく

 0 * 2 + 1 = 1
 1 * 2 + 1 = 3
 3 * 2 + 0 = 6
 6 * 2 + 1 = 13
13 * 2 + 0 = 26

この考え方に従って以下のようにおく
sum = 0
bit = "11010"

bit の該当箇所が
'1' のときは sum * 2 + 1
'0' のときは sum * 2 + 0
をする

bit[0] = '1'
sum = sum * 2 + 1
    = 1
bit[1] = '1'
sum = sum * 2 + 1
    = 3
bit[2] = '0'
sum = sum * 2 + 0
    = 6
bit[3] = '1'
sum = sum * 2 + 1
    = 13
bit[4] = '1'
sum = sum * 2 + 0
    = 26

sum = 26 復元完了!!

ビットが0か1かで0を足すか1を足すかを判断すればいいのです。とてもスマートだと思いませんか。

今度はこのバイナリ法Ver.2.0を、本来の指数と法を組み合わせたものでやってみましょう。

326 % 87を求める

sum = 1
bit = "11010"

bit[0] = '1'
sum = sum * sum % 87 = 1
sum = sum * 3 % 87 = 3
bit[1] = '1'
sum = sum * sum % 87 = 9
sum = sum * 3 % 87 = 27
bit[2] = '0'
sum = sum * sum % 87 = 729 % 87 = 33
bit[3] = '1'
sum = sum * sum % 87 = 1089 % 87 = 45
sum = sum * 3 % 87 = 48
bit[4] = '0'
sum = sum * sum % 87 = 2307 % 87 = 42

よって、
326 % 87 = 42

スマートですね。実にスマートだ。そう思いませんか? 26乗がたったの5回でできるんですよ。ちなみに、326 は 2541865828329 だそうです。

バイナリ法Ver.2.0 の実装

public static long Encode(long x, long y, long n)
{
	string bit = Convert.ToString(y, 2);
	long sum = 1;
	for (int i=0;i<bit.Length;i++)
	{
		sum = sum * sum % n;
		if(bit[i] == '1') sum = sum * x % n;
	}
	return sum;
}

アルゴリズムに感動するときって、ごくたまにあります。このバイナリ法はそれに値するでしょうね。素晴らしいと思いますよ。

RSA暗号化すべてのソースコード

RSA暗号化に必要なアルゴリズムはすべて学んだので、ソフト全体のソースコードを公開します。"abc" を暗号化して、復号化する様子を見ることができます。当然ですが、秘密鍵と公開鍵も表示します。

using System;
using System.Text;

namespace Rsa
{
	class MainClass
	{
		public static void Main(string[] args)
		{
			long p = 15439;
			long q = 3511;
			long n = p * q;
			
			long l = Lcm(p-1,q-1);
			long e = 35537;
			
			long d = GetPrivateKey(l,e);
			Console.WriteLine("Private = [ {0} ] / Public = [ {1} ]", d,n);
			
			byte[] message = Encoding.UTF8.GetBytes("abc");
			Console.Write("message:");
			foreach(byte b in message)
				Console.Write(b + " ");
			Console.WriteLine();
			
			long[] encode = new long[message.Length];
			for(int i=0;i<message.Length;i++)
				encode[i] = Encode(message[i],e,n);

			Console.Write("encode:");
			foreach(long b in encode)
				Console.Write(b + " ");
			Console.WriteLine();
			
			long[] decode = new long[encode.Length];
			for(int i=0;i<encode.Length;i++)
				decode[i] = Encode(encode[i],d,n);

			Console.Write("decode:");
			foreach(long b in decode)
				Console.Write(b + " ");
			Console.WriteLine();

		}
		
		public static long Gcd(long m, long n)
		{
			long temp;
			while (m % n != 0)
			{
				temp = n;
				n = m % n;
				m = temp;
			}
			return n;
		}
		
		public static long Lcm(long m, long n)
		{
			return m * n / Gcd(m,n); 
		}
		
		// 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 / z2;
				
				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) return y2 + a;
			else  return y2;

		}
		
		// return x^y mod n
		public static long Encode(long x, long y, long n)
		{
			string bit = Convert.ToString(y, 2);
			long sum = 1;
			for (int i=0;i<bit.Length;i++)
			{
				sum = sum * sum % n;
				if(bit[i] == '1') sum = sum * x % n;
			}
			return sum;
		}
	}
}