שינויים
/* הרצאה 7 המשך הצפנה - דיפי הלמן, חישוב חזקות, חתימה; */
===הרצאה 7 המשך הצפנה - דיפי הלמן, חישוב חזקות, חתימה;===
====שיטת מילר-רבין לבדיקת ראשוניות====
*חלק מהותי בשיטות שאנו לומדים הוא מציאת ראשוניים גדולים. כיצד הדבר נעשה? האם יש רשימה גדולה של כל הראשוניים בעולם?
*ידוע שכמות הראשוניים עד המספר <math>n</math> היא בערך <math>\frac{n}{\ln(n)}</math>.
*לכן הסיכוי בבחירת מספר אקראי עד <math>n</math> שהוא יהיה ראשוני הוא בערך <math>\frac{1}{\ln(n)}</math>.
*אנו זקוקים למבחן ראשוניות - נגריל מספרים אקראיים ונבדוק האם הם ראשוניים, ומהר מאד נמצא אחד כזה בהתחשב בסיכוי הנ"ל.
*זכרו שפירוק לגורמים ראשוניים היא בעייה קשה (אחרת RSA מיותר ממילא).
*טענה: אם <math>p</math> ראשוני, ו<math>x\in U_p</math> איבר כך ש <math>x^2=1</math> אזי <math>x=\pm 1</math>
*הוכחה:
**נזכור ש<math>U_p</math> הוא '''שדה''' כיוון שמדובר במספר ראשוני, ולכן אין בו מחלקי אפס.
**<math>x^2=1</math> אם"ם <math>(x-1)(x+1)=0</math> אם"ם <math>x=\pm 1</math>
*בהנתן מספר <math>p</math> נתאר מבחן '''הסתברותי''' הבודק האם הוא ראשוני
**נבחר מספר
====דיפי-הלמן====
*למדנו שבעזרת RSA ניתן להעביר פיסת מידע באופן בטוח בערוץ פומבי, ולרוב נרצה להעביר מפתח סודי לצורך הצפנה סימטרית.
**<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 העלאות בריבוע, ושלוש הכפלות, במקום 41 הכפלות.
===הרצאות 8-9 משפט האיזומורפיזם; פרקים 10,11 מ[http://abstract.ups.edu/aata/ הספר]===
