שינויים

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

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

נוספו 39 בתים, 11:06, 8 בדצמבר 2019
/* הרצאה 7 המשך הצפנה - בדיקת ראשוניות, דיפי הלמן, חתימה, חישוב חזקות; */
*טענה: אם <math>p</math> ראשוני, ו<math>x\in U_p</math> איבר כך ש <math>x^2=1</math> אזי <math>x=\pm 1</math>
*הוכחה:
**נזכור ש<math>U_p\mathbb{Z}_p</math> הוא '''שדה''' כיוון שמדובר במספר ראשוני, ולכן אין בו ב<math>U_p=\mathbb{Z}/\{0\}</math> מחלקי אפס.
**<math>x^2=1</math> אם"ם <math>(x-1)(x+1)=0</math> אם"ם <math>x=\pm 1</math>
**<math>x^{41}=\left(\left(\left(\left(x^2\right)^2\right)^2\right)^2\right)^2\cdot \left(\left(x^2\right)^2\right)^2 \cdot x</math>
**סה"כ חישבנו את החזקה עם 8 העלאות בריבוע, ושלוש הכפלות, במקום 40 הכפלות.
 
==הרצאה 8 תת חבורות נורמליות, חבורות מנה, גרעין; פרקים 10,11 מ[http://abstract.ups.edu/aata/ הספר]==