אז איך באמת בודקים ראשוניות (בעזרת אלגוריתם מילר-רבין)?

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

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

הדרך הפשוטה לבדוק ראשוניות של מספר \( n \) היא לעבור אחד אחד על כל המספרים הקטנים מ-\( n \) אבל גדולים מ-1 ולבדוק אם הם מחלקים אותו ללא שארית. אם נמצא כזה, המספר אינו ראשוני (זו ההגדרה של ראשוני - מספר המתחלק רק בעצמו וב-1). לתעלול הזה יש אופטימיזציה פשוטה - אם \( a \) מחלק את \( n \), כך גם \( n/a \) (כי מה זה אומר ש-\( a \) מחלק את \( n \)? שקיים \( b \) כך ש-\( n=ab \), כלומר גם \( b=n/a \) מחלק את \( n \) ללא שארית), ואם \( a \) גדול מהשורש של \( n \), אז \( b \) יהיה קטן ממנו (כי אם \( a,b>\sqrt{n} \) אז \( n=a\cdot b>\sqrt{n}\cdot\sqrt{n}=n \) - סתירה). לכן מספיק לבדוק את המספרים הקטנים מ-\( n \) “עד השורש” של \( n \). זמן הריצה של האלגוריתם הזה יהיה \( O\left(\sqrt{n}\right) \), זמן ריצה שנחשב טוב מאוד כשמתעסקים באלגוריתמים (להשוואה, זמן הריצה של אלגוריתמי המיון הכלליים הוא \( O\left(n\log n\right) \)). אם כן, מה הבעיה?

הבעיה היא שבכל הנוגע למספרים, מה שחשוב הוא לא גודל המספר עצמו אלא גודל הייצוג שלו - מספר הביטים שדרושים כדי לאחסן אותו בזכרון. כדי לאחסן את \( n \), צריך \( \lg n \) ביטים (\( \lg \) הוא לוגריתם על בסיס 2 - אם \( \lg n=k \) זה אומר ש-\( n=2^{k} \); כמובן ש-\( k \) עשוי שלא להיות מספר שלם, אז נעגל למעלה כשנצטרך להתייחס אליו כשלם). הסיבה שגודל הייצוג הוא מה שחשוב היא שהזמן שלוקח לבצע פעולות חשבון בסיסיות על מספרים - חיבור, חיסור, כפל, חילוק, השוואה בין שני מספרים - נמדד ביחס ל-\( \lg n \), לא ל-\( n \). למשל, השוואה של שני מספרים דורשת \( \lg n \) פעולות (חשבו על הצורה שבה אתם משווים שני מספרים שנתונים בבסיס עשרוני - אתם פשוט משווים ספרה ספרה), חיבור שלהם דורש \( \lg n \) פעולות (מחברים “ספרה ספרה” ולכל היותר זוכרים בע”פ שצריך להוסיף 1 לתוצאת החיבור הבאה), כפל דורש (במימוש נאיבי, כמו זה שתלמידים בבית הספר לומדים לבצע) \( \lg^{3}n \) פעולות, וכדומה. זה אומר שקל לנו לבצע פעולות על מספרים ענקיים, בני 500 ספרות ויותר (וגם מספרים בני מיליון ספרות הם עדיין משהו שאפשר להתמודד איתו), בזמן שלעבור על כל המספרים בני 500 ספרות, אפילו “עד השורש”, זה לחלוטין לא פרקטי. זו הייתה גם הנקודה המרכזית בפוסט הקודם שלי.

אם כן, אלגוריתם טוב לבדיקת ראשוניות צריך להיות בעל זמן ריצה שהוא לכל היותר חזקה כלשהי ב-\( \lg n \). כזה הוא מילר רבין, שזמן ריצתו חסום על ידי \( O\left(\lg^{3}n\right) \) (זמן ריצה מעולה עבור אלגוריתם שמבצע בדיקה של דבר מה “מסובך” כראשוניות). אלגוריתם AKS המפורסם לבדיקת ראשוניות - היחיד שידוע כיום שעובד באופן דטרמיניסטי ובזמן “סביר” לכל הראשוניים - דורש זמן ריצה של מעט יותר מ-\( O\left(\lg^{6}n\right) \), כלומר הוא פחות יעיל בכמה סדרי ממילר-רבין, ולכן עדיין מעדיפים את מילר-רבין בשימושים פרקטיים (דוגמת זה של הספריה OpenSSL שקישרתי אליה בפוסט הקודם). זה לא אומר שאין יישומים של AKS או שאי אפשר להשתמש בו אם רוצים לוודא ב-100 אחוזים סופר-דופר שמספר הוא ראשוני; אבל כמו שאסביר בהמשך (בפוסט נפרד), האקראיות של מילר-רבין נותנת 99 אחוזים (למעשה, אפילו יותר - אבל על כך בפוסט הבא) שלרוב הוא די והותר בשבילנו (ופרט ל-AKS יש עוד מבחנים שמוכיחים בודאות שמספר הוא ראשוני, אך לא מובטח שהם תמיד יעבדו בזמן פולינומי למרות שלעתים קרובות הם מהירים למדי, וגם על זה אפרט בעתיד).

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

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

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

האתגר הוא כמובן למצוא תכונות “גלובליות” שכאלו, ומה שמילר-רבין עושה למעשה הוא להשתמש בשתי תכונות גלובליות שונות; כשהאחת נכשלת (במובן זה של “לא מספקת עדות טובה לכך שהמספר לא ראשוני”), מובטח שהשניה תעבוד לעתים קרובות; ומה שנחמד הוא שאפשר לבדוק את שתיהן גם יחד. נתחיל מהתכונה הראשונה - היא מתבססת על מה שמכונה “המשפט הקטן של פרמה” שהוא האבחנה שעבור כל מספר ראשוני \( p \) וכל מספר אחר \( a \) שאינו מתחלק בידי \( p \), מתקיים ש-\( a^{p-1}-1 \) מתחלק על ידי \( p \). למשל, אם ניקח \( p=5 \), נקבל שכל מספר \( a \) שאינו מתחלק ב-5 מקיים ש-5 מחלק את \( a^{4}-1 \) (קחו \( a=2 \); \( 2^{4}-1=16-1=15 \) שמתחלק ב-5, וכו’ וכו’). בניסוח מודרני מסמנים זאת כ-\( a^{p-1}\equiv_{p}1 \) (קראו את השוויון שבאמצע כ”שקול מודולו \( p \)” - המשמעות הפורמלית היא בדיוק שהפרש שני האגפים מתחלק ב-\( p \), או אם תרצו, שחלוקת כל אחד מהאגפים ב-\( p \) נותן את אותה שארית).

פרמה גילה את המשפט מתוך משחקים במספרים והעלאת השערות; אוילר הוכיח לאחר מכן גרסה כללית יותר שלו, התקפה לכל מספר \( n \) ולא רק לראשוניים; בגרסה זו, החזקה שבה מעלים את \( a \) היא שונה (היא \( \phi\left(n\right) \) - פונקצית אוילר של \( n \), למי שמכיר) והיא תהיה \( n-1 \) אך ורק אם \( n \) ראשוני. אם כן, יש לנו קריטריון כלשהו לראשוניות: \( n \) אינו ראשוני אם \( a^{n-1}-1 \) לא מתחלק על ידי \( n \). לכן אלגוריתם לבדיקת ראשוניות \( n \) (אלגוריתם אמיתי, שנקרא על שם פרמה) יעבוד כך: בהינתן \( n \), הגרל \( a \) שאינו מתחלק על ידי \( n \), חשב את \( a^{n-1}-1 \) ובדוק אם הוא מתחלק ב-\( n \). אם לא, מובטח ש-\( n \) לא ראשוני. אם כן, בסבירות לא רעה \( n \) ראשוני (על עניין הסבירויות ארחיב בהמשך). מצאנו את האלגוריתם שרצינו.

האמנם?

צריך להיות זהירים פה. אמנם, המשפט של אוילר לא עובד עבור החזקה \( n-1 \) אם \( n \) אינו ראשוני, אבל זה רק אומר שלא מובטח לנו שמתקיים \( a^{n-1}\equiv_{n}1 \); זה בכל זאת עשוי לקרות לפעמים (למשל, אם \( a=1 \) זה יקרה תמיד). מה שהיינו רוצים שיקרה הוא שתתקיים תוצאה כמו “אם \( n \) אינו ראשוני, אז יש המון ערכים של \( a \) שעבורם \( a^{n-1}-1 \) אינו מתחלק ב-\( n \)” כי כל מספר \( a \) כזה “מוכיח” לנו ש-\( n \) אינו ראשוני. זה נכון לעתים קרובות; אלא שלרוע המזל, זה לא נכון תמיד. למעשה, יש מספרים פריקים שעבורם לכל \( a \) (שאין לו ול-n מחלקים משותפים, אבל הסיכוי להגריל \( a \) כזה הוא כמו הסיכוי לפרק לגורמים את \( n \) “במזל”) מתקיים \( a^{n-1}\equiv_{n}1 \), כלומר מספרים פריקים ש”בכל זאת” מקיימים את המשפט הקטן של פרמה ככתבו וכלשונו. למספרים הללו קוראים מספרי קרמייקל; הקטן ביותר שבהם הוא 561. התכונות שלהם ידועות לא רע - למשל, ניתן להוכיח די בקלות שכל מספר קרמייקל חייב להיות מכפלה של ראשוניים אי זוגיים שונים זה מזה (כלומר, מספר כמו \( 3\cdot3 \) או \( 2\cdot3 \) הוא מחוץ למשחק מראש); לא ניכנס לזה עכשיו. הנקודה היא שיש קבוצה ספציפית של מספרים “מרגיזים”, עם אפיונים ספציפיים משל עצמה, שעבורם השיטה של משפט פרמה נכשלת לחלוטין.

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

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

כעת לבעיה השניה. האבחנה המרכזית כאן היא שלא חייבים לכפול את \( a \) בעצמו \( n-1 \) פעמים כדי לחשב את \( a^{n-1} \). הנה דוגמה פשוטה לדרך שבה אפשר לבצע קיצורים: נניח שאני רוצה לחשב את \( a^{16} \) במעט פעולות כפל. מה שאעשה יהיה ראשית לכפול את \( a \) בעצמו ולקבל \( a^{2} \). כעת, במקום לכפול את התוצאה שוב ב-\( a \), אכפול את התוצאה בעצמה, כלומר אבצע את החישוב \( a^{2}\cdot a^{2}=a^{4} \). את התוצאה שוב אכפול בעצמה ואקבל \( a^{8} \), ואת זה שוב אכפול בעצמו ואקבל \( a^{16} \). סיימנו, וביצענו רק ארבע פעולות כפל במקום שש עשרה.

בואו ננסה משהו יותר מתוחכם. נניח שאנחנו רוצים לחשב את \( a^{13} \) עכשיו. מה עושים? פתרון פשוט הוא זה: כבר חישבנו לפני רגע את \( a^{4} \) ואת \( a^{8} \), אז פשוט נכפול אותם זה בזה וב-\( a \) ונקבל \( a\cdot a^{4}\cdot a^{8}=a^{13} \). כאן הסתמכנו על כך שניתן לכתוב את 13 כסכום של חזקות של 2: \( 13=1+4+8 \). מכיוון שאפשר לכתוב כל מספר באמצעות סכום של חזקות של 2 (זוהי פשוט ההצגה של המספר בבסיס בינארי), התעלול הזה עובד תמיד. הפאנץ’ הוא שאם אנחנו רוצים להעלות בחזקת \( n \) מספר כלשהו, אנחנו צריכים לחשב רק \( \lg n \) איברים של \( a \) בחזקת חזקות של 2 (למה? כי אנחנו צריכים את כל החזקות מהצורה \( 2^{i} \) עבורן \( 2^{i}\le n \), כלומר \( i\le\lg n \)) ולכפול את החזקות הרלוונטיות.

מה שאלגוריתם מילר-רבין עושה הוא לחשב את \( a^{n-1} \) בצורה דומה מאוד אבל לא זהה לגמרי - יש עוד טוויסט אחד, שהוא זה שעושה את כל ההבדל. הנה עוד דוגמה - נניח שאנחנו רוצים לחשב את \( a^{24} \). אפשר לעשות זאת בשתי דרכים: או לחשב את \( a^{8} \) ו-\( a^{16} \) ולכפול אותם, כפי שכבר ראינו; אבל אפשר גם לחשב את \( a^{3} \) ואז להעלות אותו שוב ושוב בריבוע, עד שמגיעים ל-\( a^{24} \). כדי להבין למה זה עובד, נשים לב לכך ש-\( 24=3\cdot2^{3} \). כלומר, אפשר לכתוב את המספר הזה בתור מכפלה של מספר אי זוגי וחזקה כלשהי של 2, ואז \( a^{24}=\left(a^{3}\right)^{2^{3}} \), כלומר ניתן לכתוב את \( a^{24} \) בתור העלאה בריבוע שלוש פעמים ברצף של \( a^{3} \). זה עובד גם באופן כללי, כמובן: כדי לחשב את \( a^{n-1} \) אפשר לכתוב \( n-1=m\cdot2^{k} \) כאשר \( m \) אי זוגי, ואז לחשב את \( a^{m} \), ואותו להעלות בריבוע \( k \) פעמים. כשמסיימים, בודקים אם קיבלנו 1 או לא.

אבל למעשה, אפשר לקצר את התהליך. נניח שחישבנו את \( a^{m} \) וקיבלנו 1; אז גם כשנעלה אותו בריבוע, ולא משנה כמה פעמים, נקבל 1. לכן אפשר לעצור כבר כאן ולהגיד שהמבחן הצליח (כלומר, נתן לנו תחושה טובה בבטן ש-\( n \) הוא ראשוני). באופן דומה, אם חישבנו את \( a^{m} \) וקיבלנו \( -1 \) אפשר לעצור - אחרי העלאה אחת בריבוע נקבל 1, ומכאן ואילך נמשיך לקבל 1. באותו אופן, אם \( a^{m} \) לא היה לא \( 1 \) ולא \( -1 \), היינו מצפים שמתישהו במהלך ההעלאות בריבוע שלו נקבל 1, וכאן נמצא לב לבו של מילר-רבין, והקריטריון הנכסף שלנו - איך מספר \( x \) שקודם לכן לא היה 1 הופך ל-1 אחרי שמעלים אותו בריבוע (מודולו \( n \))? מה \( x \) יכול להיות?

תשובת המחץ היא זו: אם \( n \) הוא ראשוני, \( x \) יכול להיות רק \( 1 \) (אבל אמרנו שהוא לא) או \( -1 \) (שכזכור, מסמן את \( n-1 \)). לעומת זאת, אם \( n \) אינו ראשוני, יכולים להיות ערכים נוספים שמקיימים זאת - “שורשים לא טריוויאליים של 1”. לדוגמה, אם \( n=8 \) אז מתקיים די בבירור \( 7^{2}=49\equiv_{8}1 \) (ו-\( 7 \) הוא בעצם מה שאנחנו מסמנים כ-\( -1 \)) אבל מתקיים גם \( 5^{2}=25\equiv_{8}1 \), ולכן \( 5 \) הוא שורש לא טריוויאלי של 1. מכאן שבמהלך החישוב של מילר-רבין, עבור ערך “מוצלח” של \( a \), ה-1 המובטח בסוף הדרך יתקבל דרך שורש לא טריוויאלי של 1, ואז נדע בודאות ש-\( n \) אינו ראשוני.

נסכם: האלגוריתם של מילר-רבין בוחר באקראי \( a \) קטן מ-\( n \) וזר לו (אם הוא אינו זר לו, קל לגלות זאת בעזרת האלגוריתם האוקלידי, וזה גם יוכיח ש-\( n \) אינו ראשוני). הוא מחשב את \( a^{n-1} \) על ידי כך שהוא מפרק את \( n-1 \) למכפלה \( n-1=m\cdot2^{k} \) (איך עושים זאת? מחלקים את \( n-1 \) שוב ושוב ב-2 עד שמתקבל מספר אי זוגי), מחשב את \( a^{m} \) בצורה מהירה בשיטת קיבוץ החזקות של 2 שהראיתי (או בשיטות אחרות - יש כאלו), ואז מעלה אותו בריבוע \( k \) פעמים תוך שהוא בודק אם במהלך החישוב צץ לו שורש לא טריוויאלי של 1 (מספר שהיה שונה מ-1 ומ-\( -1 \) אבל הפך ל-1 אחרי העלאתו בריבוע). אם צץ כזה שורש, או אם בסוף החישוב, כשהתקבל \( a^{n-1} \), התוצאה עדיין שונה מ-1, האלגוריתם דוחה; אחרת הוא אומר “סביר להניח ש-\( a \) ראשוני, אם כי אני לא בטוח”.

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

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