שינויים

*קידוד הוא שיטה להעברת מידע ובין היתר מטרתו היא להבטיח את נכונות המידע ולזהות (ולתקן) שגיאות. *הצפנה היא שיטה להסתרת מידע במקום בו כולם רואים את התוכן המועבר, ובנוסף דרך להבטיח מי הוא מקור המידע (חתימה). *המבנים האלגבריים שאנו עוסקים בהם בקורס הם חבורה, חוג ושדה.

*תזכורת לגבי חבורות, תכונת הצמצום. *<math>\mathbb{Z},\mathbb{Z}_n,{GL}_n,{SL}_n,S_n</math>. *תת חבורות; קווטרניונים, מעגל היחידה ושורשי יחידה, המרוכבים ללא אפס כתת חבורה של מטריצות ממשיות בגודל 2 על 2. *תנאי מקוצר לבדיקת תת חבורה. *כתיב אקספוננט <math>g^n=g\cdots g</math> או כפל <math>ng=g+\cdots+g</math> בהתאם לסימון פעולת החבורה. *סדר של איבר, תת חבורה ציקלית, סדר האיבר הוא גודל החבורה הציקלית.

*הגדרת סימן של תמורה לפי חלוקת פולינומים, הוכחת כפליות הסימן. *הצגת תמורה כמחזורים זרים, הצגת מחזורים כהרכבה של חילופים, סימן חילוף הוא שלילי.

*הומומורפיזמים, איזומורפיזמים. *תמונה של הומומורפיזם היא תת חבורה. *משפט קיילי- כל חבורה איזומורפית לתת חבורה של חבורת תמורות. *תת חבורה מחלקת חבורה למחלקות שקילות (קוסטים) שוות בגודלן לגודל תת החבורה. *אינדקס תת החבורה הוא מספר מחלקות השקילות שהיא מייצרת בחבורה, וזה בדיוק גודל החבורה חלקי גודל תת החבורה (משפט לגראנג'). *בחבורה סופית, לכל איבר יש סדר סופי ותת חבורה צקלית בגודל סדר האיבר. לכן סדר כל איבר מחלק את גודל החבורה. *חבורה מגודל ראשוני חייבת להיות ציקלית, וכל איבר פרט לאיבר היחידה יוצר אותה.

*זוג מספרים שלמים <math>a,b</math> נקראים שקולים מודולו n אם קיים שלם <math>q</math> כך ש <math>a=b+q\cdot n</math> *חלוקה עם שארית: לכל מספר טבעי a ולכל מספר שלם b קיים זוג שלמים '''יחיד''' <math>q,r</math> כך ש <math>b=q\cdot a+r</math> וגם <math>0\leq r < a</math>. *המספר q נקרא '''מנת''' החלוקה והמספר r נקרא '''שארית''' החלוקה. *<math>ab\equiv c</math> שקול מודולו n אם ורק אם מכפלת למכפלת השאריות של <math>a,b</math> בחלוקה בn שקולה לc מודולו n.  לכל שני מספרים טבעיים <math>k<n</math> מתקיים כי <math>gcd(n,k)=gcd(n-k,k)</math> לכל שני מספריים טבעיים <math>n,k</math> קיימים מספרים שלמים <math>a,b</math> כך ש <math>an+bk=gcd(n,k)</math> (הוכחה באינדוקציה על הגודל של n+k. אם n=k סיימנו, אחרת אם <math>k<n</math> אזי <math>gcd(n,k)=gcd(n-k,k)=a(n-k)+bk=an+(b-a)k</math>)  שני מספרים טבעיים n,k נקראים '''זרים''' אם <math>gcd(n,k)=1</math> ב<math>\mathbb{Z}_n</math> עם פעולת הכפל מודולו n האיברים ההפיכים הם בדיוק המספרים הזרים ל n. עבור מספר טבעי <math>1<n</math> קבוצת המספרים הטבעיים הזרים לn וקטנים ממנו מהווה חבורה ביחס לכפל מודולו n, היא נקראית '''חבורת אוילר''' ומסומנת <math>U_n</math>. <math>\mathbb{Z}_n</math> עם פעולות חיבור וכפל מודולו n הוא שדה אם ורק אם n הינו מספר ראשוני.

פונקצית אוילר *לכל שני מספרים טבעיים <math>\phik<n</math> מתקיים כי <math>gcd(n,k)=gcd(n-k,k)</math> היא מספר המספרים הטבעיים שקטנים או שווים לn וזרים לו*לכל שני מספריים טבעיים <math>n,k</math> קיימים מספרים שלמים <math>a,b</math> כך ש <math>an+bk=gcd(n,k)</math>*(הוכחה באינדוקציה על הגודל של n+k.אם n=k סיימנו, אחרת אם <math>k<n</math> אזי <math>gcd(n,k)=gcd(n-k,k)=a(n-k)+bk=an+(b-a)k</math>)

*שני מספרים טבעיים n,k נקראים '''המשפט הקטן של פרמהזרים''' - יהי p ראשוני ומספר אם <math>gcd(n,k)=1</math>*ב<math>\mathbb{Z}_n</math> עם פעולת הכפל מודולו n האיברים ההפיכים הם בדיוק המספרים הזרים ל n.*עבור מספר טבעי <math>a1<pn</math> אזי קבוצת המספרים הטבעיים הזרים לn וקטנים ממנו מהווה חבורה ביחס לכפל מודולו n, היא נקראית '''חבורת אוילר''' ומסומנת <math>a^U_n</math>.*<math>\mathbb{p-1Z}\equiv 1_n</math> עם פעולות חיבור וכפל מודולו pn הוא שדה אם ורק אם n הינו מספר ראשוני.

*פונקצית אוילר <math>\phi(n)</math> היא מספר המספרים הטבעיים שקטנים או שווים לn וזרים לו.*'''משפט אוילר''' - יהיו שני מספרים טבעיים '''זרים''' <math>a<n</math>. אזי <math>a^{\phi(n)}\equiv 1</math> מודולו n.*'''המשפט הקטן של פרמה''' - יהי p ראשוני ומספר טבעי <math>a<p</math> אזי <math>a^{p-1}\equiv 1</math> מודולו p.*בפרט, בתנאי המשפט, <math>a^p\equiv a</math> מודולו p.*למעשה התוצאה תקיפה לכל מספר טבעי <math>a</math>, כיוון ש <math>a^p{\phi(n)}=\left(qn+r\right)^p{\phi(n)}\equiv r^p{\phi(n)}</math>, וגם <math>r</math> זר ל <math>n</math>.