אלגוריתם מילר-רבין – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
Matanyabot (שיחה | תרומות) מ בוט החלפות: \1\2\3 |
||
שורה 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 \leq s</math> כלשהו.
|