אלגוריתם מילר-רבין – הבדלי גרסאות

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