אלגוריתם מילר-רבין – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
←תאור המבחן: תמיד היא מילה חזקה |
|||
שורה 4:
==תאור המבחן==
נתון מספר אי-זוגי n. אפשר לכתוב <math>\ n-1=2^sr</math>, כאשר r אי-זוגי. אם 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 < s</math> כלשהו.
| |||