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

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

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

[עריכה] תאור המבחן

נתון מספר אי-זוגי n. אפשר לכתוב \ n-1=2^sr, כאשר r אי-זוגי. אם n ראשוני, אז המשפט הקטן של פרמה מבטיח ש-\ a^{n-1}\equiv 1 \pmod{n}. מכיוון שמודולו מספר ראשוני יש ל- 1 בדיוק שני שורשים, \ \pm 1, בהכרח מתקיים

\ a^{r} \equiv 1 \pmod{n}, או ש-
\ a^{2^j\cdot r} \equiv -1 \pmod{n} עבור \ 0\leq j < s כלשהו.

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

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

[עריכה] דוגמה

נבדוק את המספר \ n=781, שעבורו \ n-1=2^2\cdot 195. בבדיקת הבסיס 5 מתברר ש- \ 5^{195} \equiv 1\pmod{781} (שהרי \ 5^5=1+4n). לכן 5 הוא עד חזק לראשוניות של 781. עבור הבסיס 17, מקבלים \ 17^{195} \equiv -1\pmod{781}, ולכן גם 17 הוא עד חזק. לעומת זאת, בדיקת הבסיס 2 נותנת \ 2^{780}\equiv 243, ומכאן ש- 781 אינו יכול להיות ראשוני. ואכן, \ 781=11\cdot 71.