به‌توان‌رسانی پیمانه‌ای

توان‌رسانی پیمانه‌ای (به انگلیسی: Modular Exponentiation) یک به توان رساندن است که روی ضریب (Modulus) اجرا می‌شود و در علوم کامپیوتر به‌خصوص در مبحث public-key cryptography کاربرد فراوان دارد. در واقع در رمزنگاری لازم است که توانایی یافتن پاسخ b^e mod m به صورت مؤثرتر و کاراتر را داشته باشیم. عمل توان‌رسانی پیمانه‌ای باقی‌مانده را در حالتی که عدد صحیح b به توان e برسد حساب می‌کند. یعنی، b^e، بر عدد صحیح مثبت m تقسیم شده‌است. اگر بخواهیم آن را با نمادگذاری نشان دهیم به شکل زیر خواهد بود: c ≡ b^e (mod m) برای مثال اگر b=۵ و e=۳ و m=۱۳ باشد، آنگاه c=۸ باقی‌مانده تقسیم ۵^۳ یعنی ۱۲۵ بر ۱۳ خواهدبود. برای اعداد دلخواه b و e و عدد صحیح مثبت m، پاسخ منحصربفرد c با مشخصه ۰ ≤ c <m وجود خواهدداشت. توان‌رسانی پیمانه‌ای با توان منفی e هم می‌تواند با یافتن d (معکوس ضرب پیمانه‌ای b modulo m) بوسیله الگوریتم تعمیم یافته اقلیدس اجرا شود. یعنی:c ≡ b^e ≡ d^−e mod m که e<0 و b ⋅ d ≡ 1 mod m.

توان رسانی‌های پیمانه‌ای مانند مثال بالا برای محاسبه بنظر راحت هستند، حتی اگر اعداد بکار رفته بسیار بزرگ باشند. از طرفی لگاریتم گسسته از نظر محاسبه سخت است. این قضیه توان‌رسانی پیمانه‌ای را یک گزینه خوب برای استفاده در الگوریتم‌های رمزنگاری می‌کند.

متد سرراست (Straight-forward)

سرراست‌ترین متد محاسبه توان‌رسانی پیمانه‌ای محاسبه مستقیم b^e است، سپس باقی‌مانده آن را بر m بدست می‌آوریم. درمثال زیر b = ۴، e = ۱۳ و m = ۴۹۷ است داریم:

c ≡ ۴^۱۳ mod ۴۹۷

یک راه اینست که ۴^۱۳ را، با ماشین حساب، حساب کنیم که حاصل آن برابرست با ۶۷٬۱۰۸٬۸۶۴. تقسیم این عدد بر ۴۹۷ برابر است با ۴۴۵. دقت کنید که b تنها یک رقم، e دو رقم و b^e دارای ۸ رقم دسیمال است.

در رمزنگاری‌های بزرگ b دارای ۲۵۶ بیت است (۷۸ رقم دسیمال). فرض کنید b = ۵ × ۱۰^۷۶ و e = ۱۷ باشد که هردو آن‌ها اعداد بزرگی هستند. در این مثال b دارای ۷۷ رقم دسیمال و e دارای ۲ رقم دسیمال است اما b^e دارای ۱۳۰۴ رقم دسیمال است. این‌گونه محاسبات در کامپیوترهای مدرن ممکن هستند، اما بزرگی اعداد آن‌ها باعث کندی قابل توجهی در محاسبات می‌گردد.

متد memory-efficient

متد دوم که در اینجا مورد بحث قرار گرفته عملیات بیشتری برای محاسبه توان‌رسانی پیمانه‌ای نسبت به متد قبل نیاز دارد. این روش مقدار حافظه بسیار کمتری اشغال می‌کند و عملیات آن نسبت به قبل زمان کمتری را تلف می‌کند. پس می‌توان نتیجه گرفت که این الگوریتم سریع تر است.

این الگوریتم از یک اصل استفاده می‌کند و آن اینست که برای دو عدد دلخواه a و b دو عبارت زیر باهم هم ارز هستند:

c mod m = (a ⋅ b) mod m

c mod m = [(a mod m) ⋅ (b mod m)] mod

الگوریتم به صورت زیر است:

ابتدا قرار می‌دهیم c = ۱ و e′ = 0
e′ = e′ + ۱
قرار می‌دهیم c = (b ⋅ c) mod m
اگر e′ < e آنگاه دوباره مرحله ۲ را اجرا کن. درغیراینصورت c جواب c ≡ b^e mod m را دارد.

به‌طور خلاصه این الگوریتم ′e را آنقدر افزایش می‌دهد تا مقدار آن به e برسد و هربار که آن را افزایش می‌دهد در b ضرب می‌کند و عملیات پیمانه‌ای را اجرا می‌کند.

برای مثال فرض کنید b = ۴ و e = ۱۳ و m = ۴۹۷ باشد داریم:(سه مرحله اول ۱۳ بار تکرار می‌شوند)

e′ = ۱. c = (۱ ⋅ ۴) mod ۴۹۷ = ۴ mod ۴۹۷ = ۴.
e′ = ۲. c = (۴ ⋅ ۴) mod ۴۹۷ = ۱۶ mod ۴۹۷ = ۱۶.
e′ = ۳. c = (۱۶ ⋅ ۴) mod ۴۹۷ = ۶۴ mod ۴۹۷ = ۶۴.
e′ = ۴. c = (۶۴ ⋅ ۴) mod ۴۹۷ = ۲۵۶ mod ۴۹۷ = ۲۵۶.
e′ = ۵. c = (۲۵۶ ⋅ ۴) mod ۴۹۷ = ۱۰۲۴ mod ۴۹۷ = ۳۰.
e′ = ۶. c = (۳۰ ⋅ ۴) mod ۴۹۷ = ۱۲۰ mod ۴۹۷ = ۱۲۰.
e′ = ۷. c = (۱۲۰ ⋅ ۴) mod ۴۹۷ = ۴۸۰ mod ۴۹۷ = ۴۸۰.
e′ = ۸. c = (۴۸۰ ⋅ ۴) mod ۴۹۷ = ۱۹۲۰ mod ۴۹۷ = ۴۲۹.
e′ = ۹. c = (۴۲۹ ⋅ ۴) mod ۴۹۷ = ۱۷۱۶ mod ۴۹۷ = ۲۲۵.
e′ = ۱۰. c = (۲۲۵ ⋅ ۴) mod ۴۹۷ = ۹۰۰ mod ۴۹۷ = ۴۰۳.
e′ = ۱۱. c = (۴۰۳ ⋅ ۴) mod ۴۹۷ = ۱۶۱۲ mod ۴۹۷ = ۱۲۱.
e′ = ۱۲. c = (۱۲۱ ⋅ ۴) mod ۴۹۷ = ۴۸۴ mod ۴۹۷ = ۴۸۴.
e′ = ۱۳. c = (۴۸۴ ⋅ ۴) mod ۴۹۷ = ۱۹۳۶ mod ۴۹۷ = ۴۴۵.

جواب نهایی c مقدار ۴۴۵ است، درست مانند جوابی که در متد قبل بدست آوردیم. شبه کد این متد در زیر آورده شده است:

//b: integer, n = (a(k-1)a(k-2) ... a(1)a(0)), m: positive integer
x := 1
power := b mod m
for i := 0 to k-1
    if a(i) = 1 then x := (x.power) mod m
    power := (power.power) mod m
return x{x equals b(n) mod m}