گوس در مورد نظریه اعداد می گوید : نظریه ی اعداد ملکه ی ریاضیات است. (البته سایر ریاضی دانها هم می گویند گوس پادشاه ریاضیات است.)

رشته ی کامپیوتر بخشی از ریاضیات است که یکی از اهداف اصلی آن محاسبات است. در ریاضیات هم یکی از بهترین زمینه ها که می توان با کمک آن ساده تر به نتیجه رسید استفاده از علم نظریه ی اعداد است.

امروز برنامه ای خواهیم نوشت که با کم ترین هزینه ی ممکن عبارت b ^ n)  mod m) را محاسبه کند که به این عبارت ها Modular Exponentiation گفته می شود که اهمیت خیلی مهمی در رمزنگاری دارد و محاسبه ی سریع آن بسیار مهم است.

اولین راه و بدترین راه این است که ابتدا b را به توان n برسانیم بعد باقی مانده (mod) آن را بر m حساب کنیم. ولی فرض کنید عبارتی که می خواهید محاسبه کنید این عبارت است:

(۵۶۳ ^ ۴۳۱۳۲۵۶) mod 245

برای محاسبه ی عبارت بالا دو مشکل اساسی وجود دارد :

1. محاسبه ۵۶۳ به توان ۴۳۱۳۲۵۶ بسیار و بسیار زمان بر است.
2. در حافظه ی جا نمی شود.

در نظریه ی اعداد این تساوی را داریم که از آن استفاده می کنیم:

(a * b) mod c = ( (a mod c) * ( b mod c) ) mod c

همان تور که در بالا گفتیم می خواهیم  b ^ n)  mod m) را محاسبه کنیم . ابتدا n را به صورت binary expansion

یا همان نمایش دودویی (binary) در می آوریم که عبارت زیر می شود‌ :

n = ( a(k-1), …, a(2), a(1), a(0))

اگر آن نمایش باینری را به ده دهی تبدیل کنیم از این رابطه استفاده می کنیم:

n = [2 ^ (k – 1)  * a(k-1)] + … + [۲ ^  ۲ * a(2)] + [۲ ^ ۱ * a(1)] + [۲ ^ ۰ * a(0)]

آنگاه b به توان n می شود :

b ^ n = b ^ ( a(k-1), …, a(2), a(1), a(0)) =

b ^  [۲ ^ (k – 1)  * a(k-1)] + … + [۲ ^  ۲ * a(2)] + [۲ ^ ۱ * a(1)] + [۲ ^ ۰ * a(0)] =

(b ^ [2 ^ (k – 1)  * a(k-1)]) * … * (b ^ [۲ ^  ۲ * a(2)]) * (b ^ [۲ ^ ۱ * a(1)]) * (b ^ [۲ ^ ۰ * a(0)])

b ^ n را به صورت چند جمله که در هم ضرب شده اند در آوردیم  , اکنون از تساوی که در ابتدا گفتیم می توانیم استفاده کنیم و با به دست آوردن باقی مانده  ی  هر قسمت بر m و ضرب آن ها در هم باقی مانده ی نهایی را به دست بیاوریم.

اگر به دلیل توضیح کوتاه من متوجه نشدید به کدهای زیر توجه کنید (کد اول با سی پلاس پلاس است و دومی با        جاوا اسکریپ  ) و آن را یک بار تریس کنید.

کد سی پلاس پلاس

برای تبدیل عدد دهدهی به دودویی (binary) تابع  زیر را نوشته ام :

vector<bool> decimalToBinary(int n)
{
	bitset<32> convertor(n);
	string binaryString = convertor.to_string();
	
	int finalIndex;
	for (int i = 0; i < binaryString.size(); i++)
	{
		finalIndex = i;
		
		if (binaryString.at(i) == '1')
		{
			break;
		}
	}

	vector<bool> output;
	for (int i = finalIndex; i < binaryString.size(); i++)
	{
		output.push_back( (binaryString.at(i) == '1') ? true : false );
	}

	return output;
}

در این تابع از ویژگی کلاس bitset خود سی پلاس پلاس استفاده کرده ام که خودش قابلیت تبدیل عدد ده دهی را به دودویی دارد که یک رشته از صفر و یک ها برمی گرداند این رشته را گرفته ام و به یک وکتور از جنس bool (منطقی ) تبدیل کرده ام و صفر های آخر رشته را که  ارزشی ندارند را حذف کرده ام.

تابع محاسبه ی  عبارت b ^ n)  mod m) که با نام Modular Exponentiation  شناخته می شود

//this function calculate (b ^ n) mod m
int modularExponentiation(int b, int n, int m)
{
	vector<bool> binaryExpansion = decimalToBinary(n);

	int x = 1;
	int power = b % m;

	for (int i = binaryExpansion.size() - 1; i >= 0; i--)
	{
		if (binaryExpansion.at(i) == true)
		{
			x = (power * x) % m;
		}
		power = (power * power) % m;
	}

	return x;
}

در زیر کد کلی برنامه را  می بینید که در تابع main ورودی ها را می گیرد :

// Modular Exponentiation.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <bitset>
#include <vector>
#include <string>

using namespace std; 

vector<bool> decimalToBinary(int n)
{
	bitset<32> convertor(n);
	string binaryString = convertor.to_string();
	
	int finalIndex;
	for (int i = 0; i < binaryString.size(); i++)
	{
		finalIndex = i;
		
		if (binaryString.at(i) == '1')
		{
			break;
		}
	}

	vector<bool> output;
	for (int i = finalIndex; i < binaryString.size(); i++)
	{
		output.push_back( (binaryString.at(i) == '1') ? true : false );
	}

	return output;
}

//this function calculate (b ^ n) mod m
int modularExponentiation(int b, int n, int m)
{
	vector<bool> binaryExpansion = decimalToBinary(n);

	int x = 1;
	int power = b % m;

	for (int i = binaryExpansion.size() - 1; i >= 0; i--)
	{
		if (binaryExpansion.at(i) == true)
		{
			x = (power * x) % m;
		}
		power = (power * power) % m;
	}

	return x;
}

int main( )
{
	int b, n, m;
	cout << "Enter Base , power, Module (ex (4^2) mod 3 : 4 2 3) :" << endl;

	cin >> b >> n >> m;

	cout << "modularExponentiation ( " << b << " ^ " << n << " ) mod " << m << " = "
		<< modularExponentiation(b, n, m) << endl;
	
	return 0;
}

تصویر خروجی برنامه به ازای ورودی

(۵۶۳ ^ ۴۳۱۳۲۵۶) mod 245

را می بینیدکه همان طور مشاهده می کنید جواب ۱۴۱ می شود.

کد جاوا اسکریپت

کد محاسبه ی  عبارت b ^ n)  mod m) یا Modular Exponentiation با زبان جاوا اسکریپ (javascript)  :

// Modular Exponentiation.cpp : Defines the entry point for the console application.
//

 

function decimalToBinary ( n)
{
	return n.toString(2);
}


//this function calculate (b ^ n) mod m
function modularExponentiation( b, n, m)
{
	var binaryExpansion = decimalToBinary(n);

	var x = 1;
	var power = b % m;

	for (var i =  binaryExpansion.length - 1; i >= 0; i--)
	{
		if (binaryExpansion[i] === '1')
		{
			x = (power * x) % m;
		}
		power = (power * power) % m;
	}

	return x;
}

console.log(  modularExponentiation(563,4313256,245));