הצגת המקור של הדף "אלגוריתם מילר-רבין"

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

יש לאלגוריתם גרסה [[אלגוריתם אקראי|הסתברותית]] מהירה יחסית, שמזהה כל [[מספר ראשוני]] ככזה, אבל עשויה, ב[[הסתברות]] נמוכה ככל שנרצה, להכריז כך גם על [[מספר פריק]]. גרסה זו, שפותחה על ידי פרופ' [[מיכאל רבין]] מן [[האוניברסיטה העברית]], היא המבחן המקובל לבדיקת ראשוניות (תפקיד אותו מילא קודם [[מבחן סולוביי-שטרסן]].{{הערה|{{צ-מאמר|מחבר=R. Solovay, V. Strassen|שם=A Fast Monte-Carlo Test for Primality|כתב עת=SIAM Journal on Computing|כרך=6|עמ=84–85|שנת הוצאה=1977-03-01|doi=10.1137/0206006|קישור=http://epubs.siam.org/doi/abs/10.1137/0206006}}}})

==תיאור המבחן==

בהינתן מספר אי-זוגי שלם <math> n>2 </math>, ניתן לכתוב <math>\ n-1=2^sr</math>, כאשר s מספר טבעי ו-r מספר טבעי אי-זוגי. יהי a [[מספר שלם]], כך ש a ו-n [[מספרים זרים]]. אם n ראשוני, אז המשפט הקטן של פרמה מבטיח ש- <math>\ a^{n-1}\equiv 1 \pmod{n}</math>. מכיוון שב[[חשבון מודולרי|חשבון מודולו]] מספר ראשוני יש ל-1 בדיוק שני שורשים ריבועיים, <math>\ \pm 1</math>, בהכרח מתקיים 
: <math>\ a^{r} \equiv 1 \pmod{n}</math>, או ש- 
: <math>\ a^{2^j\cdot r} \equiv -1 \pmod{n}</math> עבור <math>\ 0\leq j \leq s-1</math> כלשהו. 
תנאי זה חייב להתקיים אם n ראשוני. [[סיבוכיות]] הבדיקה כ- <math>\ O(\log^3(n))</math> פעולות.

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

===קוד של אלגוריתם מילר רבין===

להלן מימוש של האלגוריתם בשפת [[פייתון (שפת תכנות)|פייתון]]:
<syntaxhighlight lang="python">
from random import randrange

def surely_composite(n, d, s, a):
    'n-1 == 2**s * d'
    x = pow(a, d, n) # a^d mod n, efficiently        
    if x == 1 or x == n - 1:
        return False
    for _ in range(s):
        x = pow(x, 2, n)
        if x == 1: return True
        if x == n - 1: return False
    return True

def miller_rabin(n, number_of_rounds):    
    (d, s) = n - 1, 0
    while d % 2 == 0:
        (d, s) = (d//2, s+1)
    
    for round in range(number_of_rounds):
        if surely_composite(n, d, s, randrange(2, n - 1)):
            return "Composite"
    return "Probably Prime"
</syntaxhighlight>

==דוגמה==

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

==לקריאה נוספת==
* תומאס ה. קורמן, צ'ארלס א. לייזרסון, רונאלד ל. ריבסט, '''מבוא לאלגוריתמים''', [[הוצאת MIT]], תורגם לעברית על ידי [[האוניברסיטה הפתוחה]].

==קישורים חיצוניים==
* {{MathWorld}}

==הערות שוליים==
{{הערות שוליים}}

[[קטגוריה:ערכים שבהם תבנית בריטניקה אינה מתאימה]]
[[קטגוריה:מבחני ראשוניות]]
[[קטגוריה:אלגוריתמים|מילר-רבין]]
[[קטגוריה:ישראל: המצאות]]