ועכשיו למשהו מסובך יותר - הוצאת שורש ריבועי!

בפוסט הקודם דיברתי על מספר שיטות למציאת שורש ריבועי. מה שלא אמרתי במפורש בשום מקום הוא מהי “זירת המשחק” שלי - שהייתה, באופן מובלע, המספרים הממשיים. בממשיים יש שורשים למספרים כמו 2 (שאין להם שורש רציונלי), ולכן אפשר להוציא בהם שורש לכל מספר טבעי - וזה מה שאנחנו עושים בדרך כלל. למספרים שליליים לא יכלתי להוציא שורש, אבל ההרחבה עבורם אינה מסובכת (עבור מינוס x, הוצא שורש ל-x וכפול את התוצאה במספר המדומה i). אגב, כל השיטות שלי נתנו למעשה רק קירוב רציונלי לשורש, כך שכלל לא חרגתי מגבולות ארגז החול של המספרים הרציונליים.

אלא שהמספרים הממשיים/מרוכבים/רציונליים רחוקים מלהיות סוף הסיפור. אפשר להגדיר מושג של שורש לכל קבוצה שיש בה מושג של כפל - וכאלו יש רבות ושונות. בפוסט הזה אני רוצה לדבר על קבוצה קצת אחרת, שבה בעיית השורש היא שונה לגמרי, וקשה הרבה יותר. בפוסט הקודם דיברתי על פירוק לגורמים ראשוניים של מספר בתור דוגמה לשיטה אפשרית אחת להוצאת שורש; אז זו הייתה דרך מסובכת לעשות משהו פשוט. עבור הקבוצה שאדבר עליה הפעם, פירוק לגורמים (אם כי לא של מי שמוציאים לו שורש) הוא, במובן מסויים, הדרך הפשוטה ביותר הידועה להוצאת שורש - ולמעשה, שתי הבעיות שקולות בקושי החישובי שלהן. מכיוון שלעת עתה בעיית הפירוק לגורמים נחשבת קשה, התוצאה היא בעיה קשה “חדשה” - ומכאן קצרה הדרך לשימושים בקריפטוגרפיה.

את הקבוצה שאני רוצה לדבר עליה כבר הזכרתי פעם - חבורת אוילר מודולו \( n \). הזכרתי אותה באותו הקשר בדיוק - של הקושי בהוצאת שורשים. עם זאת, אז השתמשתי בבעיה כדי להדגים פרוטוקול אפס-ידע; הפעם אדבר על משהו קצת שונה.

תזכורת קצרה לגבי מהי חבורת אוילר: אנו לוקחים את כל המספרים הטבעיים בין 0 ובין \( n \) (לא כולל), כאשר \( n \) הוא מספר טבעי כלשהו. אנו משנים קצת את הגדרת הכפל עבורם - כופלים שני מספרים כרגיל, אבל אחר כך מחלקים את התוצאה ב-\( n \) ולוקחים את השארית. כך למשל עבור \( n=7 \), נקבל תוצאה מוזרה כמו \( 3\cdot 5=1 \). כלומר, כאן 5 הוא ה”הופכי” של 3 - המכפלה של שניהם נותנת 1. במילים אחרות, בקבוצה הזו מתקיימת התכונה המשונה של \( 5=3^{-1} \)

כדי שהקבוצה עם פעולת הכפל הזו תהיה זכאית למילה “חבורה”, צריך לבצע סיכול ממוקד של חלק מאיבריה. הסיבה לכך היא ש”חבורה” הוא שם למבנה עם פעולת כפל שלכל איבר בה יש הופכי. לכן צריך להעיף מהקבוצה כל מספר שאין לו הופכי - ומתברר שלמספר אין הופכי אם ורק אם יש מחלק משותף גדול מ-1 לו ול-\( n \) (נתתי רמז לגבי איך מוכיחים זאת בפוסט הקודם ההוא).

אם כן, יש לנו את חבורת אוילר. עבור מספר ראשוני p, חבורת אוילר מודולו p היא פשוטה במיוחד - כל המספרים הטבעיים (לא כולל אפס) שקטנים מ-p (למה?). מכיוון שיש כפל אפשר לדבר על שורש - למשל, אם נביט בחבורת אוילר מודולו 7, וניקח למשל את 3 ונעלה אותו בריבוע - נקבל את השארית של חלוקת 9 ב-7, כלומר 2. מכאן ששורש ריבועי אחד של 2 הוא 3. השורש השני הוא 4 (אתגר: איך גיליתי זאת מייד, בלי לחשב, רק מתוך הידיעה ששורש אחד של 2 הוא 3?), וניתן להוכיח שבאופן כללי, בחבורה מודולו ראשוני יהיו רק שני שורשים ולא יותר מכך (הסיבה לכך היא שהחבורה, אם מכניסים גם את 0 פנימה הופכת לשדה - אפשר להגדיר עליה פעולת חיבור ש”תסתדר טוב” עם הכפל - וזה לא נכון בחבורות אוילר שאינן מודולו ראשוני).

בדומה לכך שלא לכל המספרים הטבעיים יש שורש טבעי, כך גם ישנם איברים בחבורת אוילר בלי שורש (למשל - בחבורה מודולו 7, האם יש ל-3 שורש?). אפשר לבצע כאן הרחבה על ידי “הוספת” שורשים, בדומה לתהליך שכבר ראינו בעבר (עם בניית המרוכבים, למשל), אבל זה לא קשור לעניין שאני רוצה לעסוק בו. השאלה “האם לאיבר בחבורה יש שורש?” היא שאלה מעניינת בזכות עצמה, ואיבר שיש לו שורש שכזה זכה לשם מיוחד - “שארית ריבועית” (שארית, כי אנו עוסקים בשאריות של חלוקה ב-n, וריבועית - כי היא ריבוע של איבר אחר).

הבדיקה האם איבר הוא שארית ריבועית מודולו ראשוני מסויים אינה קשה במיוחד, בזכות “משפט ההדדיות הריבועית” שהוכיח גאוס (אחד מהמשפטים האהובים עליו, אם לשפוט לפי זה שהוא כינה אותו “משפט הזהב” , ומצא לו שש הוכחות שונות). המשפט עצמו (ובפרט השימוש בו) הוא טכני למדי ולא אכנס אליו כעת - אולי בעתיד.

אז לבדוק האם למספר יש שורש (מודולו ראשוני) זה לא קשה. מה עם מציאת שורש שכזה? כאן אנחנו נכנסים למים עמוקים בהרבה. מסתבר שעבור חלק מהראשוניים, הוצאת שורש היא קלה מאוד - ממש טריוויאלית, ואילו עבור אחרים זה מסובך בהרבה. ההפרדה מתבצעת על פי השארית שהראשוני משאיר בחלוקה ב-4.

ראשית, נשים לב שהשארית הזו היא בהכרח 1 או 3, כי מספר אי זוגי שמחולק במספר זוגי משאיר שארית אי זוגית, וכל הראשוניים פרק ל-2 אי זוגיים (המקרה של 2 טריוויאלי ולא עוסקים בו). המקרה הפשוט הוא זה שבו השארית היא 3, והקשה הוא זה שבו היא 1. זו לא הדוגמה היחידה מתורת המספרים שבה הראשוניים מתחלקים באופן הזה: למשל, משפט ידוע ששיער פרמה (והוכיח אוילר) הוא שראשוני אי זוגי ניתן לכתיבה כסכום של שני ריבועים אם ורק אם הוא שקול ל-1 מודולו 4. (למשל, 13 ניתן להצגה כסכום הריבועים 4 ו-9, אבל לכו תציגו את 19 באופן דומה).

כדי להציג את הפתרון הפשוט במקרה שבו הראשוני שקול ל-3 מודולו 4, צריך לציין עובדה בסיסית על שאריות ריבועיות: אם \( a \) הוא שארית ריבועית מודולו \( p \), אז מתקיים \( a^{\frac{p-1}{2}}=1 \) (השוויון הוא בחבורת אוילר המתאימה, כמובן). צריך לשים לב לכך ש-\( \frac{p-1}{2} \) הוא מספר שלם, כי \( p \) הוא כאמור אי זוגי, ולכן אם מפחיתים ממנו 1, מקבלים מספר זוגי (ולמה זה חשוב? כי בחבורת אוילר אין משמעות בדרך כלל לחזקה שאינה מספר שלם). הסיבה שבגללה התוצאה נכונה היא משפט אחר, “המשפט הקטן של פרמה”, שאומר (בערך) שבחבורת אוילר מודולו \( p \) ראשוני מתקיים תמיד, לכל מספר, ש-\( a^{p-1}=1 \). לא אוכיח את המשפט כאן - עושים זאת בכל קורס סטנדרטי בתורת החבורות, אחרי היכרות כלשהי עם המשפטים והמושגים הבסיסיים (בהינתן שהם ידועים, ההוכחה מיידית - יישום מסקנה ממשפט לגראנז' לחבורה הכפלית מודולו \( p \)). למה זה מוכיח זאת? כי אם יש \( b \) כך ש-\( b^2=a \), אז מתקבלת שרשרת המשוואות הבאה:

\( a^{\frac{p-1}{2}}=(b^2)^{\frac{p-1}{2}}=b^{p-1}=1 \)

עכשיו, הדרך למציאת שורש היא טריוויאלית. אם \( a \) הוא שארית ריבועית מודולו \( p \) ששקול ל-3 מודולו 4, אז בפרט \( p+1 \) מתחלק ב-4, ואז הברנש הבא הוא שורש: \( b=a^{\frac{p+1}{4}} \). למה? כי אם נעלה את \( b \) בריבוע, נקבל:

\( b^2=a^{\frac{p+1}{2}}=a\cdot a^{\frac{p-1}{2}}=a\cdot 1=a \)

והעניין הזה תם ונשלם.

עכשיו, אחרי שהתשתי אתכם עם המקרה הפשוט, אני יכול להגיד באלגנטיות “גם למקרה השני יש פתרון יעיל, הוא מסובך ולא אציג אותו מתוך רחמים עליכם”. אלא שבפועל, גם אני לא ממש מכיר פתרון משביע רצון. אני מכיר פתרון יעיל אחד (מסובך יותר מהפתרון למקרה הפשוט, אבל לא כל כך נורא), אבל הוא הסתברותי. אמנם, הוא אלגוריתם הסתברותי מהסוג שמכונה “אלגוריתם לאס-וגאס” - אלגוריתם שתמיד עונה תשובה נכונה, והעוקץ במקרה שלו נובע מכך שקיימת הסתברות כלשהי שהוא לא יהיה יעיל (ייקח יותר מדי זמן). בפועל, כולם משתמשים בשיטה הזו ולא דווח על נפילות מטוסים. עם זאת, טהרנים כמוני עשויים לרצות אלגוריתם לא הסתברותי שכן יהיה יעיל - בחיפוש קצר מצאתי מאמר שטוען שעלה בידו לעשות זאת, אבל ההכרות שלי עם עקומים אליפטיים בפרט ותורת המספרים בכלל היא שטחית מכדי שאבדוק זאת בעצמי.

ומה עם הוצאת שורש מודולו \( n \) כללי, לאו דווקא ראשוני? ואיך זה קשור לקריפטוגרפיה, חוץ מפרוטוקול אפס-הידע שכבר הראיתי? את זה נשאיר לפעם הבאה.