אלגוריתם מילר-רבין

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

נתון מספר אי-זוגי n>2. כותבים n-1 = 2^s · r, כאשר r אי-זוגי.
בוחרים מספר a שמקיים gcd(a,n)=1 (כלומר a ו-n זרים). אם n ראשוני, אז לפי משפט פרמה a^{n-1}≡1 (שארית של 1 בחלוקה ב-n). מכאן נובע שאחד מהמצבים הבאים חייב להתקיים:
1) a^{r} ≡ 1 (מעל מודולו n), או
2) קיימת j בין 0 ל-s-1 כך ש־a^{2^j·r} ≡ -1 (כלומר שארית n-1).
אם אף אחד מהתנאים הללו לא מתקיים, n פריק. אם אחד מהם מתקיים, אומרים ש-a הוא "עד חזק" (strong witness) לראשוניות של n, כלומר הוא מעיד ש-n עלול להיות ראשוני, אבל זו לא הוכחה סופית.

אם n פריק, ניתן להראות שרק עד ארבע מהמספרים עד n-1 יכולים להיות עדות חזקות. לכן בדיקה עם t עדים אקראיים מורידה את ההסתברות לטעות ל־4^{-t}. זוהי גרסה הסתברותית מהירה, מקובלת בפרקטיקה (למשל לשימוש ב־RSA).

סיבוכיות הבדיקה היא בערך O(log^3 n) פעולות חשבוניות.

מימוש נפוץ בפייתון מבצע את השלבים הבאים:
1. מפרידים את n-1 ל־r ו־s על ידי חלוקה ב־2 עד ש־r אי-זוגי.
2. חוזרים על מספר סיבובים: בוחרים בסיס a אקראי בין 2 ל־n-2.
3. מחשבים x = a^r mod n. אם x שווה ל־1 או ל־n-1, עוברים לסיבוב הבא.
4. אחרת מריצים הלולאה s-1 פעמים: מרבעים x מודולו n ובודקים אם מתקבל n-1.
5. אם לא נמצא n-1, מכריזים על n כפריק. אחרת ממשיכים.

נבחן n = 781. כתוצאה נקבל n-1 = 2^2 · 195.
בסיס 5: 5^{195} ≡ 1 (מודולו 781), לכן 5 הוא עד חזק.
בסיס 17: 17^{195} ≡ -1, גם הוא עד חזק.
בסיס 2: 2^{780} ≡ 243, כלומר התנאים לא מתקיימים, ולכן 781 פריק. אכן 781 = 11 · 71.

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

קודם כותבים את n-1 בצורה n-1 = 2^s · r. זאת אומרת: מחלקים ב-2 עד שהשארית r אי-זוגית. (r הוא המספר שנותר.)
בוחרים מספר a שלא מתחלק ב-n. מחשבים חזקות של a ומסתכלים על השארית בחלוקה ב-n.
אם התוצאה היא שארית 1, או אם על ידי חיבור ריבועים של התוצאה מקבלים שארית n-1, אז a "מעיד" שייתכן ש-n ראשוני.
אם זה לא קורה, אומרים ש-n פריק (לא ראשוני).
חוזרים על הבדיקה כמה פעמים כדי להקטין את הסיכוי לטעות.

יש תוכנית פייתון קצרה שמממשת את השלבים: מפצלים את n-1, בוחרים a אקראי, מחשבים שאריות ומרבעים עד שמחליטים.

נבדוק n = 781. יש כאן n-1 = 2^2 · 195.
עם a=5 מקבלים שארית 1, לכן 5 מעיד לטובת ראשוניות.
עם a=17 מקבלים שארית שלילית (שזה n-1), גם זה מעיד לטובת ראשוניות.
עם a=2 מקבלים שארית אחרת, וזה מראה ש-781 פריק. בפועל 781 = 11 · 71.