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

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

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

== متد سرراست (Straight-forward) ==
سرراست‌ترین متد محاسبه توان‌رسانی پیمانه‌ای محاسبه مستقیم *be* است، سپس باقی‌مانده آن را بر m بدست می‌آوریم. درمثال زیر b = ۴، e = ۱۳ و m = ۴۹۷ است داریم:

*c* ≡ ۴<sup>۱۳</sup> mod ۴۹۷

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

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

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

این الگوریتم از یک اصل استفاده می‌کند و آن اینست که برای دو عدد دلخواه a و b دو عبارت زیر باهم هم ارز هستند:
:<syntaxhighlight lang="text">
c mod m = (a ⋅ b) mod m

c mod m = [(a mod m) ⋅ (b mod m)] mod
</syntaxhighlight>
الگوریتم به صورت زیر است:
# ابتدا قرار می‌دهیم *c* = ۱ و *e′* = 0
# *e′ = e′ + ۱*
# قرار می‌دهیم *c* = (b ⋅ c) mod *m*
# اگر *e′* < *e* آنگاه دوباره مرحله ۲ را اجرا کن. درغیراینصورت c جواب *c* ≡ *b*<sup>e</sup> 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 مقدار ۴۴۵ است، درست مانند جوابی که در متد قبل بدست آوردیم. شبه کد این متد در زیر آورده شده است:
```text
//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}
```


رده:الگوریتم‌های رمزنگاری
رده:الگوریتم‌های نظریه اعداد
رده:حساب پیمانه‌ای