מחשבון מבחן ראשוניות מילר-רבין

אודות מחשבון זה

מבחן מילר-רבין בודק ראשוניות על ידי כתיבת n − 1 כ-2ˢ·d כאשר d אי-זוגי, ואז בדיקה אם בסיס עד a מקיים aᵈ ≡ 1 (mod n) או a^(2ʳ·d) ≡ −1 (mod n) עבור r < s כלשהו. עד בודד נותן רק תוצאה הסתברותית, אך בדיקה מול קבוצה קטנה ומוכחת של בסיסי עדים קבועים (למשל 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) הופכת את המבחן לדטרמיניסטי לכל מספר שלם הנמוך מכ-3.18 × 10²³ — הרבה מעבר למה שרוב היישומים צריכים אי פעם.

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