שורש, ההוכחה (חלק א’)

אם השעה היא 19:00 ושואלים אותנו מה תהיה השעה עוד שש שעות, אנו עונים שהיא תהיה 1:00. איך אנחנו יודעים? אנחנו מחברים 6 ל-19, מקבלים 25, ומחסרים 24 מהתוצאה, כי הרי בשעון, כל 24 שעות “מתחילים מהתחלה”.

זו דוגמה לאריתמטיקה מודולרית - במקרה הזה, אריתמטיקה מודולו 24. המשמעות היא פשוטה: האיברים שלנו הם מספרים שלמים בתחום מ-0 עד 23, ופעולות החשבון הבסיסיות (חיבור וכפל) מתבצעות כרגיל, פרט לכך שאחרי סיומן אנו מחלקים את התוצאה ב-24 ולוקחים רק את השארית. אלו מכם שיש להם נסיון בתכנות ודאי מכירים אופרטור שמצוי ברוב השפות הקיימות (ב-++C ושפות בעל תחביר דומה הוא “%”) שמבצע פעולת חילוק-ולקיחת-שארית שכזו. כך למשל באריתמטיקת השעון שלנו מתקיים \( 5\cdot 7=11 \) כי את התוצאה במספרים “רגילים”, 35, אנו מחלקים ב-24 ולוקחים שארית. עוד מתקיים גם \( 3\cdot 8=0 \), כי כאן התוצאה היא 24, והשארית על כן היא 0.

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

מה באשר לשאר פעולות החשבון הבסיסיות? חיסור לא מציב שום בעיה, כל עוד מוכנים לבצע מציאת שארית בצורה קצת שונה מזו שהמחשב עושה: כך למשל ה”שארית” של מינוס 2 באריתמטיקה מודולו 24 היא 22 דווקא (כי זה המספר היחיד בטווח מ-0 ועד 23 שהמרחק שלו ממינוס 2 הוא כפולה שלמה של 24). חילוק, לעומתו, זה סיפור שונה לגמרי.

ברור שחילוק “רגיל” לא עוזר לנו. כך למשל \( 7/2=3.5 \) היא לא תוצאה קבילה, כי \( 3.5 \) הוא לא מספר שלם בין 0 ל-23. לכן עלינו לשאול את עצמנו ראשית כל מה אנו רוצים.

חילוק, באופן כללי, הוא הפעולה ההפוכה לכפל. כלומר, \( a/b=x \) פירושו שמתקיים \( b\cdot x=a \). תוצאת החלוקה של \( a \) ב-\( b \) היא המספר שכאשר כופלים אותו ב-\( b \) מקבלים את \( a \). בפועל, קל להראות (נסו!) שמספר זה הוא בדיוק המספר אשר מתקבל כאשר כופלים את \( a \) בהופכי הכפלי של \( b \) - כלומר, במספר \( t \) כלשהו (אני נמנע בכוונה מהסימון המקובל) שעבורו מתקיים \( b\cdot t=1 \).

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

כאשר עוסקים במספרים ממשיים, אפס הוא המספר הבעייתי היחידי. לעומת זאת, באריתמטיקה מודולו n, יכולים להיות מספרים בעייתיים נוספים. אפשר להראות (שוב, ללא קושי רב - נסו!) שכל זוג מספרים שונים מאפס המקיימים \( a\cdot b=0 \) (מספרים כאלו נקראים מחלקי אפס, וכבר הזכרתי אותם בעבר) אינם הפיכים. עם עוד קצת מאמץ אפשר לראות שמספר שהוא זר ל-\( n \) (כלומר, אין מספר פרט ל-1 שמחלק גם אותו וגם את \( n \)) הוא הפיך, ואילו מספר שאינו זר ל-\( n \) הוא מחלק אפס, ולכן אינו הפיך. נסו להוכיח זאת. (רמז: אם מספר \( a \) הוא זר ל-\( n \) אז קיימים \( x,y \) שלמים כך ש-\( xa+yn=1 \); אם מספר לא זר ל-\( n \) אז קיים מספר קטן ממש מ-\( n \) שמחלק גם אותו וגם את \( n \)).

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

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

סיימנו עם ארבע פעולות החשבון הבסיסיות. הפעולה הבאה בתור היא הוצאת שורש. שוב, שורש כאן אינו שורש במובן הרגיל, של “שורש 2 הוא \( 1.41421356\dots \)”, אלא במובן של “איבר בחבורה שכשמכפילים אותו בעצמו מקבלים את 2”. למשל, בחבורת אוילר מסדר 7, המספר 3 הוא (באופן מפתיע?) שורש של 2: 3 כפול עצמו זה 9, ומודולו 7 מקבלים 2. באופן דומה גם 4 הוא שורש.

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

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

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

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

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