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