منبع اصلی نوشتار زیر در این لینک قرار دارد

محاسبه ی باقی مانده ی توان یک عدد – Modular Exponentiation

modular exponentiation

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

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

امروز برنامه ای خواهیم نوشت که با کم ترین هزینه ی ممکن عبارت 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

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

modular exponentiation

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

کد محاسبه ی  عبارت 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));

 

Digg This  Reddit This  Stumble Now!  Buzz This  Vote on DZone  Share on Facebook  Bookmark this on Delicious  Kick It on DotNetKicks.com  Shout it  Share on LinkedIn  Bookmark this on Technorati  Post on Twitter  Google Buzz (aka. Google Reader)  



برچسب ها : , , , , , ,

به سیاره لینوکس امتیاز دهید

به اين صفحه امتياز دهيد