שינויים

קפיצה אל: ניווט, חיפוש

מבנים אלגבריים למדעי המחשב - ארז שיינר

נוספו 52 בתים, 10:14, 28 בינואר 2019
/* שיטת מילר-רבין לבדיקת ראשוניות */
**בהנתן מספר n, ונסמן <math>n-1=2^s\cdot r</math> עבור r אי זוגי. אומרים שהמספר <math>1\leq a <n</math> הוא '''עד חזק''' לראשוניות של n אם אחד מהתנאים הבאים מתקיים:
***<math>a^r\equiv 1 \mod n</math>
***<math>a^{2^kr}\equiv n-1 \mod n</math> עבור <math>1\leq k \leq s-1</math>. *שימו לב- <math>n-1\equiv -1 \mod n</math>