אוף, כל הקטע עם השורש הריבועי באמת יוצא מסובך

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

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

בעיית הפירוק לגורמים שייכת ל-NP, מן הסתם: אולי לא קל לנו לפרק את n, אבל אם בא מישהו ונותן לנו שני ראשוניים p,q ואומר “אלו הגורמים של n”, קל לבדוק אותו - מכפילים אותם, ורואים אם קיבלנו n. זה מספיק כדי לזכות את שאלת הפירוק לגורמים בתואר “אולי אפשר לפתור ביעילות, אבל לא יודעים איך”. יתר על כן, ב-NP יש אוסף של בעיות שנחשבות “הקשות ביותר ב-NP”, מהטעם הפשוט שפתרון יעיל שלהן ייספק דרך יעילה לפתור כל בעיה ב-NP (ולכן P=NP). לבעיות הללו קוראים “בעיות NP-שלמות”. בעיית הפירוק לגורמים אינה מוכרת כבעיה NP שלמה; כלומר, גם אם נפתור אותה ביעילות, השמיים לא יפלו ושום בעיה מרכזית במדעי המחשב לא תוכרע באופן שנראה כרגע לא סביר.

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

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

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

אז יש לי איזה שהוא x שאני רוצה להוציא לו שורש ריבועי מודולו n. לא בטוח בכלל שקיים לו שורש שכזה, אבל בואו נעסוק במקרה שבו קיים (אם יודעים את הפירוק של n קל לבדוק אם קיים ל-x שורש). נניח שפתרתי את הבעיות הקלות יותר של הוצאת שורש ל-x מודולו p ומודולו q, כלומר - מצאתי \( y_p,y_q \) כך שמתקיים:

\( y_p^2\equiv x (mod p) \)

\( y_q^2\equiv x (mod q) \)

עכשיו, נניח שבדרך קסם כלשהי אני מוצא y שמודולו p שקול ל-\( y_p \), ומודולו q שקול ל-\( y_q \). מה קורה? אני אקבל ש:

\( y^2\equiv y_p^2\equiv x (mod p) \)

\( y^2\equiv y_q^2\equiv x (mod q) \)

ומזה נובע ש:

\( y^2\equiv x (mod n) \)

המעבר האחרון בפירוש אינו מובן מאליו. כדי להבין אותו, צריך לשוב להגדרות הבסיסיות: \( a\equiv b(mod p) \) פירושו ש-p מחלק את \( a-b \). באופן דומה, אם גם \( a\equiv b(mod q) \), נובע מכך שגם q מחלק את \( a-b \). כעת מגיעה טענה לא טריוויאלית (אך גם לא קשה מדי): אם שני מספרים שזרים זה לזה (אין להם מחלק משותף גדול מ-1) מחלקים שניהם גם יחד מספר כלשהו, אז גם מכפלתם מחלקת אותו.

כלומר, בהקשר שלנו, פירוש הדבר הוא ש-pq מחלק את \( a-b \), אבל הרי pq=n. לכן, כמו שראינו, שורש של x שהוא אותו הדבר הן מודולו p והן מודולו q נותן לנו שורש מודולו n של x.

נשאר רק להבין איך מתרחש ה”קסם”; איך לוקחים שני שורשים שונים של x מודולו מספרים שונים, ומאחדים אותם לפתרון בודד.

משפט השאריות הסיני הוא זה שעושה את הקסם הזה. מכיוון שיש למשפט הזה ניסוחים רבים ושונים, אסתפק באחד מהפשוטים והפרטיים שבהם - בדיוק זה שאני זקוק לו כעת. הרעיון הבסיסי הוא זה. נניח שנתונים לנו שני מספרים שלמים, \( a,n \) ואנחנו רוצים לפתור את המשוואה \( x\equiv a(mod n) \). האם אפשר לעשות זאת? כמובן, די בקלות; למשל, \( x=a \) הוא פתרון. אם כן, מה הלאה? מה אם יהיו לנו שתי משוואות, שאת שתיהן נרצה לפתור בו זמנית? כלומר, אם יש לנו \( n,m \) שלמים, ו-\( a,b \) שלמים, האם אפשר למצוא פתרון לשתי המשוואות הבאות:

\( x\equiv a(mod n) \)

\( x\equiv b(mod m) \)

התשובה היא שכלל לא בטוח שאפשר. נניח ש-\( n=2,m=4, a=1, b=0 \), אז פתרון לשתי המשוואות הוא מספר שמצד אחד מתחלק ללא שארית ב-4, ומצד שני משאיר שארית 1 בחלוקה ב-2, כלומר הוא אי זוגי - והרי כל מספר שמתחלק ב-4 הוא בפרט זוגי. לכן אין כאן פתרון למערכת.

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

הרעיון המרכזי בהוכחה הוא למצוא מספר \( x_n \) בעל שתי התכונות הנאות הבאות:

\( x_n\equiv a(mod n) \)

\( x_n\equiv 0(mod m) \)

ולמצוא \( x_m \) דומה, רק הפוך (שקול ל-\( b \) מודולו \( m \) ושקול לאפס מודולו \( n \)). אם מצאנו כאלו, הפתרון הסימולטני למשוואות הוא \( x_n+x_m \) (למה?)

איך מוצאים \( x_n \) שכזה? כאן נכנס החלק החישובי לסיפור. מכיוון ש-\( m,n \) זרים, אפשר להשתמש באלגוריתם האוקלידי המורחב (שראוי לפוסט משל עצמו) כדי למצוא מספרים שלמים \( \alpha,\beta \) כך ש- \( \alpha n+\beta m=1 \) (אם המחלק הגדול ביותר של \( m,n \) היה גדול מ-1, אפשר היה עדיין לכתוב סכום דומה כשבאגף ימין של השוויון יש את המחלק הזה; נסו לחשוב איזו הכללה של המשפט נובעת בשל כך למקרה שבו \( m,n \) לא זרים).

כעת, על ידי כפל שני האגפים ב-\( a \) והעברת אגף, מקבלים את המשוואה \( a\beta m=a-a\alpha n \). אם לוקחים את כל זה מודולו \( m \) ברור שמקבלים אפס (בגלל אגף שמאל), ואם לוקחים אותו מודולו \( n \) ברור שמקבלים \( a \) (בגלל אגף ימין), ולכן זה ה-\( x_n \) המבוקש.

זה סוגר את ההוכחה מלבד החור של האלגוריתם האוקלידי המורחב.

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

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

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

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

רק חוב אחד נשאר לי: הדבר שבשבילו בכלל עושים את כל המהומה הזו - השימוש שלה בקריפטוגרפיה.