|
|
|
</syntaxhighlight>
הצפנה ופענוח דורשים פעולות העלאה בחזקה עם מעריך גדול. הדרך הנאיבית לחישוב חזקה אינה יעילה במקרה זה. קיימים מספר אלגוריתמים לחישוב חזקות גדולות באריתמטיקה מודולרית. להלן תיאור שיטה רקורסיבית בסיסית שנקראת Square and Multiply או "העלאה בחזקה משמאל לימין". הרעיון הוא שאפשר לחשב את <math>\ a^k\ \mbox{mod}\ n</math> באמצעות סדרת הריבועים <math>\ a, a^2, a^4, a^8,...</math> עד <math>\ a^k</math>, אפשר להכין סדרה כזו באופן רקורסיבי על ידי העלאות חוזרות בריבוע של: <math>\ a_i</math> וצמצום ב=a_{i-<math>1}^2\text{ mod }n</math>. (היותלפי שהחישובים מתבצעיםחוקי תמידהאריתמטיקה מודולו <math>n</math> אפשר לבצע את הצמצום המודולרי לאחר כל הכפלההעלאה בריבוע במקום לבצע את הצמצום בסוף ובכך להימנע מהתנפחות התוצאה). ואז לפי [[חוקי חזקות|חוקי החזקות]] אפשר לקבל את <math>\ a^k</math> כמכפלה של ערכים מתוך הסדרה האמורה, אותם אפשר לקבל על ידי הייצוג הבינארי של המעריך, דהיינו כאשר מופיע אחד במעריך יש לכלול את האיבר המתאים במכפלה. הטבלה הבאה מדגימה את <math>245^{3125}\mbox{ mod } 10237</math>. הפרמטר <math>k</math> בטבלה מכיל את הייצוג הבינארי של המעריך: <math>\{1,1,0,0,0,0,1,1,0,1,0,1\}_2</math> כאשר הסיבית הימנית היא הסיבית הכי פחות משמעותית והסיבית השמאלית היא הסיבית המשמעותית ביותר. התוצאה תהיה מכפלת ערכי <math>a</math> בעמודות בהן <math>k_i=1</math> כלומר
:<math>245^{3125}\equiv (a_1\cdot a_3\cdot a_5 \cdot a_6 \cdot a_{11} \cdot a_{12}) \mbox{ mod } 10237\equiv (245\cdot 6579\cdot 8608\cdot 2258\cdot 9942\cdot 5129)\text{ mod }10237\equiv 9737</math>
|
