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

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