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

תוכן שנמחק תוכן שנוסף
Matanyabot (שיחה | תרומות)
מ בוט החלפות: \1תיאור\2
שורה 3:
יש לאלגוריתם גרסה [[אלגוריתם אקראי|הסתברותית]] מהירה יחסית, שמזהה כל מספר ראשוני ככזה, אבל עשויה, ב[[הסתברות]] נמוכה ככל שנרצה, להכריז כך גם על [[מספר פריק]]. גרסה זו, שפותחה על ידי פרופ' [[מיכאל רבין]] מן [[האוניברסיטה העברית]], היא המבחן המקובל לבדיקת ראשוניות, (תפקיד אותו מילא קודם [[אלגוריתם סולוואי-סטרסן]] (''[[:en:Solovay-Strassen primality test|Solovay-Strassen]]'')).
 
==תאורתיאור המבחן==
נתון מספר אי-זוגי 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>, או ש-