محاسبه ی باقی مانده ی توان یک عدد – 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) تابع  زیر را نوشته ام :

 

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

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

 

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

 

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

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

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

modular exponentiation

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

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

 

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)

Leave a Reply

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *