חשבון של שעון.

שלב 1 מתוך 6

שארית

ההצפנה של היום בנויה על חשבון שבו המספרים לא גדלים לעולם: הם מסתובבים. כשמחלקים מספר שלם $a$⁠ במספר $n$⁠, נשארת שארית בין $0$⁠ ל־$n - 1$⁠. את השארית הזאת כותבים $a \bmod n$⁠, וקוראים „$a$⁠ מודולו $n$⁠”.

בסצנה, אליס ובוב משני צדי צינור פתוח, ואיב מקשיבה באמצע. מבט פנימה פתוח על המתמטיקה: באמצע הלוח עומדת חוגה עם $23$⁠ מקומות, $0$⁠ עד $22$⁠, כמו שעון. כל מספר נוחת על המקום של השארית שלו בחלוקה ב־$23$⁠.

שלב 2 מתוך 6

סביב השעון

שעון רגיל הוא חשבון מודולו $12$⁠: אחרי $11$⁠ באה שוב $0$⁠, שאותה אנחנו קוראים $12$⁠. כדי לדעת מה השעה בעוד כמה שעות, מחברים ולוקחים שארית. אותו דבר עובד בכפל: אפשר לקחת שארית אחרי כל צעד, והתוצאה לא משתנה.

שלב 3 מתוך 6

חזקות במודולו

בהחלפת מפתחות לא מחברים אלא מעלים בחזקה. בוחרים מספר ראשוני $p$⁠, כאן $23$⁠, ומספר $g$⁠, כאן $5$⁠. אליס בוחרת מספר סודי $a$⁠ ומחשבת

$A = g^a \bmod p$⁠

הסוד של אליס קבוע עכשיו על $a = 2$⁠, והמתמטיקה מוסתרת. חשבו את $A$⁠ בעצמכם.

שלב 4 מתוך 6

צעד אחרי צעד

אין צורך לחשב את $5^{10}$⁠, מספר בן שמונה ספרות, כדי לדעת מה זה $5^{10} \bmod 23$⁠. כל חזקה היא הקודמת כפול $g$⁠, ואפשר לקחת שארית אחרי כל כפל. כך המספרים נשארים תמיד קטנים מ־$p$⁠, וכך מחשבים גם חזקות של מספרים בני מאות ספרות.

שנו את הסוד של אליס והסתכלו על הלוח שלה ועל המחוג שלה בחוגה.

שלב 5 מתוך 6

דילוגים

החזקות של $5$⁠ מודולו $23$⁠ לא עולות בסדר: $5$⁠, $2$⁠, $10$⁠, ואז קפיצה. המחוג מדלג על פני החוגה, ואין דרך לדעת לאן הוא יגיע בלי לחשב.

שלב 6 מתוך 6

סיבוב שלם

ל־$5$⁠ יש תכונה מיוחדת מודולו $23$⁠: החזקות שלו מגיעות לכל מקום על החוגה מלבד $0$⁠, כל מקום פעם אחת. מספר כזה נקרא יוצר. בשיעור האחרון ביחידה הוא יהיה ה־$g$⁠ של החלפת המפתחות.