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

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

: <math>\ a^{r} \equiv 1 \pmod{n}</math>, או ש-

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