שינויים
/* דיפי-הלמן */
ההרצאות מבוססות באופן כללי על הספר [http://abstract.ups.edu/aata/ Abstarct Algebra - Theory and Applications by Thomas W. Judson]
* [[מדיה:19CSASnotes.pdf|סיכום ההרצאות מ2019 ע"י ספיר ביתן]]* [[מדיה:21CSASnotes.pdf|סיכום ההרצאות מ2021 ע"י רועי אוסקר]] =מבחנים לדוגמא= *[[מדיה:17ASExmTest1.pdf|מבחן לדוגמא 1 תשע"ח]]**[[מדיה:17ASExmTest1Sol.pdf|פתרון מבחן לדוגמא 1 תשע"ח]]*[[מדיה:17ASExmTest2.pdf|מבחן לדוגמא 2 תשע"ח]]**[[מדיה:17ASExmTest2Sol.pdf|פתרון מבחן לדוגמא 2 תשע"ח]]*[[מדיה:17ASExmTest3.pdf|מבחן לדוגמא 3 תשע"ח]]**[[מדיה:17ASExmTest3Sol.pdf|פתרון מבחן לדוגמא 3 תשע"ח]]*[[מדיה:17ASTestA.pdf|מבחן מועד א' תשע"ח]]*[[מדיה:17ASTestB.pdf|מבחן מועד ב' תשע"ח]]*[[מדיה:17ASTestC.pdf|מבחן מועד ג' תשע"ח]]*[[מדיה:18ASTestA.pdf|מבחן מועד א' תשע"ט]]**[[מדיה:18ASTestASol.pdf|פתרון מועד א' תשע"ט]]*[[מדיה:19ASTestB.pdf|מבחן מועד ב' תשע"ט]]**[[מדיה:18ASTestBSol.pdf|פתרון מועד ב' תשע"ט]]*[[מדיה:20ASTestA.pdf|מבחן מועד א' תש"ף]]*[[מדיה:20ASTestB.pdf|מבחן מועד ב' תש"ף]]*[[מדיה:21ASTestA.pdf|מבחן מועד א' תשפ"א]]**[[מדיה:21ASTestASol.pdf|פתרון מבחן מועד א' תשפ"א]]*[[מדיה:21ASTestB.pdf|מבחן מועד ב' תשפ"א]]*[[מדיה:21ASTestC.pdf|מבחן מועד ג' תשפ"א]]*[[מדיה:22ASTestA.pdf|מבחן מועד א' תשפ"ב]]*[[מדיה:22ASTestB.pdf|מבחן מועד ב' תשפ"ב]] * [[89-214 מבחנים|מבחנים משנים קודמות]] =נושאי ההרצאות= [https://www.youtube.com/playlist?list=PLzSjdxrZD_hka_9hBlLKybpwG_5_T7FaY פלייליסט של הרצאות קבוצה 01 תשפ"א] [https://www.youtube.com/playlist?list=PLzSjdxrZD_hlVTrX-RcrpYiTMyQBmIihV פלייליסט של הרצאות קבוצה 02 תשפ"א] ==הרצאה 1 הקדמה; הסבר על קידוד והצפנה, מבוא למבנים אלגבריים ===
*קידוד הוא שיטה להעברת מידע ובין היתר מטרתו היא להבטיח את נכונות המידע ולזהות (ולתקן) שגיאות.
*כתיב אקספוננט <math>g^n=g\cdots g</math> או כפל <math>ng=g+\cdots+g</math> בהתאם לסימון פעולת החבורה.
*סדר תהי G חבורה, לכל <math>a\in G,n\in \mathbb{N}</math> נגדיר:**<math>a^0=e_G</math>.**<math>a^{-n}=(a^{-1})^n</math> *הערה: קל להוכיח כי <math>(a^{-1})^n=(a^n)^{-1}</math> *תהי חבורה G, לכל <math>a\in G</math> נגדיר את הסדר של האיבר <math>o(a)</math> בתור החזקה החיובית הקטנה ביותר k עבורה <math>a^k=e_G</math>. אם אין חזקה כזו, ניתן לומר שהסדר הוא אינסוף.*דוגמאות:**<math>o(e_G)=1</math>.**ב<math>\mathbb{Z}_5</math> מתקיים כי <math>o(2)=5</math>.**ב<math>\mathbb{Z}</math> הסדר של כל איברשונה מאפס הוא אינסוף. *תהי חבורה G, ויהי <math>a\in G</math>. תת החבורה הציקלית הנוצרת על ידי a הינה <math><a>=\{a^n|n\in\mathbb{Z}\}</math>*הוכחה שאכן מדובר בתת חבורה ציקלית:**<math>e_G=a^0\in<a></math>.**יהיו <math>a^n, a^k\in<a></math> אזי <math>a^n\cdot (a^k)^{-1}=a^n\cdot (a^{-1})^k=a^{n-k}\in<a></math>. *תהי חבורה G, אזי סדר כל איבר הוא גודל החבורה הציקלית שהוא יוצר, כלומר <math>|<a>|=o(a)</math>.*הוכחה:**ראשית נוכיח עבור המקרה בו סדר האיבר סופי <math>o(a)=n</math>.***רוצים להוכיח כי <math><a>=\{e_G,a,a^2,...,a^{n-1}\}</math> וכי כל האיברים בקבוצה זו שונים זה מזה (אחרת כמות האיברים קטנה יותר מn).***ברור שהחזקות של a שייכות לתת החבורה הציקלית.***יהי k כלשהו, נסמן בr את השארית <math>r=k \mod n</math> כלומר <math>k=pn+r</math> עבור <math>p\in\mathbb{Z}, 0\leq r\leq n-1</math>.***<math>a^k=(a^n)^pa^r=e_G^pa^r=a^r</math>.***כעת נניח כי קיימות שתי חזקות שונות <math>0\leq r_1<r_2\leq n-1</math> כך ש <math>a^{r_1}=a^{r_2}</math>.***לכן <math>a^{r_2-r_1}=e_G</math>.***אבל <math>r_2-r_1\leq n-1 < n</math> בסתירה לכך ש<math>o(a)=n</math>.**כעת נניח כי סדר האיבר הוא אינסוף, ונוכיח כי גודל תת החבורה הציקליתשהוא יוצר הוא אינסוף.***נניח בשלילה ש <math><a></math> סופית, לכן לפחות שתי חזקות שונות של a נותנות אותו איבר.***נסמן <math>n<k</math> כך ש <math>a^n=a^k</math>.***לכן <math>a^{k-n}=e_G</math> בסתירה לכך שסדר האיבר הוא אינסוף. *מסקנה: תהי חבורה '''סופית''' G, אזי לכל איבר בחבורה יש סדר סופי.**הוכחה: גודל תת החבורה הציקלית חייב להיות סופי. *תת חבורות ציקליות:**<math>2\mathbb{Z}</math>.**<math>\{z\in\mathbb{C}:z^n=1\}\subseteq \mathbb{C}\setminus \{0\}</math> שורשי היחידה מסדר n. ==הרצאה 3 חבורת תמורות, סימן התמורה; פרק 5 מ[http://abstract.ups.edu/aata/ הספר] == ===סימן של תמורה===*נביט בחבורת התמורות <math>S_n</math>.*עבור <math>f\in S_n</math> נגדיר את הסימן <math>\mathrm{sign}(f):=\Pi_{i\neq j}\frac{x_{f(i)}-x_{f(j)}}{x_i-x_j}</math>.*הסימן של תמורה הוא תמיד פלוס או מינוס 1.*אם סימן התמורה הוא מינוס אחד אומרים שהיא '''אי-זוגית''' או '''שלילית''', ואם הסימן הוא אחד אומרים שהיא '''זוגית''' או '''חיובית'''. *כפליות הסימן: תהיינה שתי תמורות <math>f,g\in S_n</math>, אזי <math>\mathrm{sign}(f\circ g)=\mathrm{sign}(f)\cdot\mathrm{sign}(g)</math>.**הוכחה:**<math>\mathrm{sign}(f\circ g)=\Pi_{i\neq j}\frac{x_{f(g(i))}-x_{f(g(j))}}{x_i-x_j}=\Pi_{i\neq j}\frac{x_{f(g(i))}-x_{f(g(j))}}{x_{g(i)}-x_{g(j)}}\cdot\frac{x_{g(i)}-x_{g(j)}}{x_i-x_j}</math>**כיוון שg חח"ע ועל,אוסף הזוגות <math>i\neq j</math> שווה לאוסף הזוגות <math>g(i),g(j)</math>, ולכן <math>\Pi_{i\neq j}\frac{x_{f(g(i))}-x_{f(g(j))}}{x_{g(i)}-x_{g(j)}}=\mathrm{sign}(f)</math>.**סה"כ קיבלנו <math>\mathrm{sign}(f\circ g)=\mathrm{sign}(f)\cdot\mathrm{sign}(g)</math>. <videoflash>Lmk0izbQR08</videoflash> ===מחזורים===*מחזור <math>(a_1\ a_2\ \cdots \ a_k)</math> מייצג את התמורה f המקיימת <math>f(a_1)=a_2,...,f(a_{k-1})=a_k,f(a_k)=a_1</math> ולכל איבר אחר <math>f(a)=a</math>.*לדוגמא: <math>\begin{pmatrix}1&2&3&4&5\\4&2&5&3&1\end{pmatrix}=(1\ 4\ 3\ 5)\in S_5</math> *כל תמורה ניתן להציג כהרכבה של מחזורים זרים, ואת תמורה הזהות ניתן להציג כ<math>(1)</math>. *חילוף הוא מחזור באורך 2.*חילוף הוא תמורה אי זוגית.**נוכיח עבור <math>f=(1\ 2)\in S_n</math>. (זה מספיק כיוון שהשם של האיברים לא משנה.)**<math>\mathrm{sign}(f)=\left(\frac{x_2-x_1}{x_1-x_2}\cdot\frac{x_2-x_3}{x_1-x_3}\cdots \frac{x_2-x_n}{x_1-x_n}\right)\cdot\left(\frac{x_1-x_3}{x_2-x_3}\cdots\frac{x_1-x_n}{x_2-x_n}\right)\left(\cdot\frac{x_3-x_4}{x_3-x_4}\cdots\frac{x_{n-1}-x_n}{x_{n-1}-x_n}\right)=-1</math> *כל מחזור ניתן להציג כהרכבה של חילופים:**<math>(a_1\ a_2\ \cdots \ a_k)=(a_1\ a_2)(a_2\ a_3)\cdot (a_{k-1}\ a_k)</math>**כל איבר שלא מוזכר במחזור נשלח לעצמו, ונציב בשני הצדדים את <math>a_1,...,a_{k-1}</math> ונראה כי הפונקציות שוות.**כיוון שמדובר בפונקציה הפיכה, אין צורך לבדוק את האיבר האחרון <math>a_k</math>. *מסקנה: כיוון שסימן כל חילוף הוא שלילי ולפי כפליות הסימן, הסימן של מחזור באורך k הוא <math>(-1)^{k-1}</math>.*דוגמא:**<math>f=\begin{pmatrix}1&2&3&4&5&6&7\\4&2&5&3&1&7&6\end{pmatrix}=(1\ 4\ 3\ 5)(6\ 7)</math>.**לכן <math>\mathrm{sign}(f)=(-1)\cdot(-1)=1</math>, כלומר מדובר בתמורה זוגית. <videoflash>oXntZnnoHfM</videoflash> ==הרצאה 4 הומומורפיזמים, איזומורפיזמים, משפט קיילי, משפט לגראנג'; פרקים 9 ו6 מ[http://abstract.ups.edu/aata/ הספר] == ===הומומורפיזם, איזומורפיזם===*הגדרה: תהיינה שתי חבורות G,H ותהי פונקציה <math>f:G\to H</math>. אזי f נקראת '''הומומורפיזם''' אם לכל <math>a,b\in G</math> מתקיים <math>f(a\cdot_G b)=f(a)\cdot_H f(b)</math>. *שימו לב ש <math>\cdot_G</math> היא הפעולה של G, ו<math>\cdot_H</math> היא הפעולה של H.*הומומורפיזם שהוא פונקציה חח"ע ועל נקרא איזומורפיזם.*הומומורפיזם שומר במובן מסויים על המבנה של החבורה, ואיזומורפיזם מראה שהחבורות הן 'אותה גברת בשינוי אדרת'. *תכונות:**אם <math>f:G\to H</math> הומומורפיזם אזי <math>f(e_G)=e_H</math>.***הוכחה:***<math>f(e_G)=f(e_G\cdot e_G)=f(e_G)\cdot f(e_G)</math>.***לפי תכונת הצמצום <math>f(e_G)=e_H</math>.**אם f הומומופיזם אזי <math>o(f(a))\leq o(a)</math>.***אם <math>o(a)=n</math> אזי <math>a^n=e_G</math>.***לכן <math>f(a^n)=\left(f(a)\right)^n=e_H</math>.***לכן <math>o(f(a))\leq n=o(a)</math>.**אם f איזומורפיזם אזי <math>o(f(a))= o(a)</math>.***נניח כי <math>o(a)=n</math>, הוכחנו ש<math>o(f(a))\leq n</math>.***נסמן <math>o(f(a))=k</math>.***לכן <math>\left(f(a)\right)^k=e_H</math>, ולכן <math>f(a^k)=e_H</math>.***כיוון שאיזומורפיזם הינו פונקציה חח"ע, נובע כי <math>a^k=e_G</math>, כלומר <math>o(a)\leq k</math>.***ביחד <math>k=n</math>.***לבסוף, נובע <math>o(f(a))</math> סופי אם"ם <math>o(a)</math> סופי, ולכן הם שווים גם אם אחד מהם הוא אינסוף.**אם f הומומורפיזם אזי <math>f(a^{-1})=\left(f(a)\right)^{-1}</math> (שימו לב שf לא צריכה להיות הפיכה, והסימון <math>f^{-1}(a)</math> לא בהכרח מוגדר ואינו קשור).***אכן <math>f(a)\cdot f(a^{-1})=f(e_G)=e_H</math>. *הגדרה: גרעין של הומומורפיזם הוא אוסף האיברים שנשלחים לאיבר היחידה.*טענה: התמונה והגרעין של הומומורפיזם הינם תתי חבורות של הטוווח והתחום בהתאמה.**הוכחה לגבי התמונה:**יהי הומומורפיזם <math>f:G\to H</math>.**ראשית, <math>f(e_G)=e_H</math> ולכן <math>e_H\in Im(f)</math>.**שנית, יהיו <math>h_1,h_2\in Im(f)</math> לכן קיימים <math>g_1,g_2\in G</math> כך ש <math>f(g_i)=h_i</math>.**<math>h_1\cdot h_2^{-1}=f(g_1)\cdot \left(f(g_2)\right)^{-1}=f(g_1\cdot g_2^{-1})\in Im(f)</math>.**סה"כ הוכחנו כי <math>Im(f)</math> הינה תת חבורה של <math>H</math>. ===משפט קיילי===*שיכון קיילי:**תהי חבורה <math>G</math> ונגדיר את S להיות חבורת הפונקציות ההפיכות מ<math>G</math> לעצמה עם פעולת ההרכבה (חבורת תמורות).**לכל איבר <math>a\in G</math> נגדיר את התמורה המתאימה לו <math>f_a\in S</math> המוגדרת ע"י <math>f_a(x)=a\cdot x</math>.***הוכחה ש<math>f_a\in S</math>:***חח"ע: אם <math>f_a(x_1)=f_a(x_2)</math> אזי <math>a\cdot x_1=a\cdot x_2</math> ולפי תכונת הצמצום <math>x_1=x_2</math>.***על: עבור <math>y\in G</math> מתקיים כי <math>f_a(a^{-1}\cdot y)=a\cdot(a^{-1}\cdot y) =(a\cdot a^{-1})\cdot y=y </math>**הפונקציה <math>\varphi:G\to S</math> השולחת כל איבר לתמורה המתאימה לו <math>\varphi(a)=f_a</math> נקראת '''שיכון קיילי'''.
*תכונות:*שיכון קיילי הינו הומומורפיזם.**<math>\varphi(a)\circ\varphi(b)=f_a\circ f_b</math>.**<math>f_a\circ f_b (x)=f_a(f_b(x))=הרצאה 3 חבורת תמורות, סימן התמורה; פרק 5 מ[http:a\cdot (b\cdot x)=(a\cdot b)\cdot (x) = f_{a\cdot b}(x)</math>.**לכן <math>\varphi(a)\circ\varphi(b)=\varphi(a\cdot b)</abstractmath>.ups*שיכון קיילי הינו חח"ע (לכן הוא נקרא שיכון).edu**אם <math>a\neq b</aata/ הספר] =math>, אזי <math>f_a(e)=a\neq b=f_b(e)</math>.**כלומר <math>f_a\neq f_b</math> ולכן <math>\varphi(a)\neq\varphi(b)</math>.
*מסקנה: '''משפט קיילי''' כל חבורה איזומורפית לתת חבורה של חבורת תמורות.
**הוכחה: החבורה איזומורפית לתמונה שלה בשיכון קיילי.
===הרצאה 4 הומומורפיזמים, איזומורפיזמים, משפט קיילי, משפט לגראנג'; פרקים 9 ו6 מ===*תהי חבורה G ותת חבורה H. יהי <math>a\in G</math>, נגדיר את '''המחלקה''' <math>a\cdot H:=\{a\cdot h:h\in H\}</math>.*אלה הן למעשה מחלקות השקילות של היחס <math>aRb\iff a^{-1}b\in H</math>**הוכחה שמדובר ביחס שקילות:***רפלקסיביות: <math>a^{-1}a=e\in H</math>***סימטריות: אם <math>a^{-1}b\in H</math> אזי גם ההופכי שלו <math>(a^{-1}b)^{-1}=b^{-1}a\in H</math>***טרנזיטיביות: נניח <math>a^{-1}b,b^{-1}c\in H</math> אזי לפי סגירות גם <math>a^{-1}bb^{-1}c=a^{-1}c\in H</math>**אכן <math>[httpa]_R=\{b|aRb\}=\{b|a^{-1}b=h\in H\}=\{b|b=ah,h\in H\}=a\cdot H</math>*טענה:לכל איבר <math>a\in G</math> מתקיים כי <math>|a\cdot H|=|H|</abstractmath>.ups.edu**הוכחה: **נביט בפונקציה <math>f:H\to a\cdot H</aatamath> המוגדרת ע"י <math>f(h)=a\cdot h</ הספר] math> ונוכיח שהיא חח"ע ועל.**חח"ע: אם <math>f(h_1)=f(h_2)</math> אזי <math>a\cdot h_1=a\cdot h_2</math> ולפי תכונת הצמצום <math>h_1=h_2</math>.**על: יהי <math>a\cdot h\in a\cdot H</math>, ברור ש<math>f(h)=a\cdot h</math>.
*הגדרה: האינדקס <math>[G:H]</math> מוגדר להיות מספר המחלקות השונות ש<math>H</math> מגדירה.
*כיוון שראינו שהמחלקות הן בעצם מחלקות שקילות שוות בגודלן המחלקות את G, נובע '''משפט לגראנג' ''':עבור חבורות סופיות, <math>|G|=|H|\cdot [G:H]</math>.
*נובע כי הגודל (סדר) של כל תת חבורה, מחלק את הגודל (סדר) של החבורה כולה.
*יהי <math>a\in G</math> איבר מסדר <math>n</math>. ראינו כי <math>|<a>|=n</math>, ולכן ביחד סדר האיבר מחלק את גודל החבורה.
*תהי חבורה סופית עם מספר ראשוני של איברים, אזי היא חבורה ציקלית.
**אכן, ניקח איבר שונה מהנייטרלי, הסדר שלו חייב להיות המספר הראשוני (כי לראשוני אין מחלקים), ולכן החבורה הציקלית שלו שווה לכל החבורה.
<videoflash>jKprPSfRysE</videoflash>
*זוג מספרים שלמים <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>.
**קיום:
***יהי <math>a\in\mathbb{N}</math>
***אם <math>b=0</math> אזי <math>b=0\cdot a + 0</math>.
***יהי <math>b\geq 0</math> עבורו הטענה נכונה, נוכיח עבור <math>b+1</math>.
***<math>b+1=qa+r+1</math>.
***אם <math>r+1<a</math> סיימנו, אחרת <math>r+1=a</math> ולכן <math>b=(q+1)a+0</math>.
***אם <math>b<0</math> אזי <math>-b=qa+r</math>.
***אם <math>r=0</math> אזי <math>b=(-q)a+0</math> וסיימנו.
***אם <math>0<r<a</math> אזי <math>b=-qa-r=-qa-a+a-r=(-q-1)a+(a-r)</math> כאשר <math>0<a-r<a</math>.
**יחידות:
***נניח <math>b=q_1a+r_1=q_2a+r_2</math>.
***לכן <math>(q_1-q_2)a=r_2-r_1</math>.
***אבל <math>-(a-1)\leq r_2-r_2\leq a-1</math>, ולכן <math>r_2-r_1\neq ka</math>.
***לכן <math>q_1-q_2=0</math> כלומר <math>q_1=q_2</math> ולכן גם <math>r_1=r_2</math>.
*המספר q נקרא '''מנת''' החלוקה והמספר r נקרא '''שארית''' החלוקה.
*יהיו שני טבעיים שלמים <math>a,b</math> ויהיו <math>r_a,r_b</math> השאריות שלהם בחלוקה בn. אזי <math>ab\equiv r_ar_b \mod n</math>**<math>ab=(q_an+r_a)(q_bn+r_b)=(q_aq_bn+r_aq_b+q_ar_b)n+r_ar_b</math>*מסקנה: באותם תנאים, לכל k טבעי מתקיים כי <math>a^k\equiv r_a^k \mod n</math>.
===המחלק המשותף הגדול ביותר===
*לכל שני מספרים טבעיים <math>k<n</math> מתקיים כי <math>gcd(n,k)=gcd(n-k,k)</math>
**נוכיח שכל מספר שמחלק את <math>n,k</math> מחלק גם את <math>n-k,k</math> וההפך, ולכן הגדול ביותר הוא אותו האחד.
**אם <math>a</math> מחלק את <math>n,k</math> אזי <math>n=qa,k=ta</math>, לכן <math>n-k=(q-t)a</math>.
**אם <math>a</math> מחלק את <math>n-k,k</math> אזי <math>n-k=qa,k=ta</math> ולכן <math>n=(q+t)a</math>.
*לכל שני מספריים טבעיים <math>n,k</math> קיימים מספרים שלמים <math>a,b</math> כך ש <math>an+bk=gcd(n,k)</math>
**עבור <math>n=k=1</math> מתקיים כי <math>1\cdot 1 + 0\cdot 1 = 1 = gcd(הוכחה באינדוקציה על הגודל של 1,1)</math>.**נניח שהטענה נכונה לכל <math>n+k<m</math> נוכיח שהיא נכונה עבור <math>n+k=m</math>. **אם <math>n=k סיימנו</math> אזי <math>1\cdot n + 0\cdot k = n =gcd(n, n)=gcd(n,k)</math>.**אחרת , אם <math>n>k<n</math> אזי מתקיים כי <math>gcd(n,k)=gcd(n-k,k)=a(n-k)+bk=an+(b-a)k</math>).**שימו לב שהנחת האינדוקציה התקיימה עבור הזוג <math>n-k,k</math>.
*שני מספרים טבעיים n,k נקראים '''זרים''' אם <math>gcd(n,k)=1</math>
*ב<math>\mathbb{Z}_n</math> עם פעולת הכפל מודולו n האיברים ההפיכים הם בדיוק המספרים הזרים ל n.
**נניח <math>k\in\mathbb{Z}_n</math> אינו זר לn, כלומר <math>gcd(n,k)=a>1</math>.
***לכן <math>n=qa,k=ta</math> לכן <math>qk=tn</math> ולכן <math>qk=0\in\mathbb{Z}_n</math> כלומר k מחלק אפס ואינו הפיך.
**נניח <math>k\in\mathbb{Z}_n</math> זר לn כלומר <math>gcd(n,k)=1</math>.
***לכן קיימים שלמים כך ש <math>an+bk=1</math> לכן <math>b\cdot k \equiv 1 \mod n</math>.
*עבור מספר טבעי <math>1<n</math> קבוצת המספרים הטבעיים הזרים לn וקטנים ממנו מהווה חבורה ביחס לכפל מודולו n, היא נקראית '''חבורת אוילר''' ומסומנת <math>U_n</math>.
**הוכחה ש<math>U_n</math> חבורה:
**סגירות: מכפלת הפיכים היא הפיכה.
**אסוציאטיביות: נובע מהאסוציאטיביות של הכפל.
**איבר נייטרלי: 1.
**הפיכים: ברור מההגדרה.
*<math>\mathbb{Z}_n</math> עם פעולות חיבור וכפל מודולו n הוא שדה אם ורק אם n הינו מספר ראשוני.
**אכן, כל המספרים החיוביים הקטנים מn הפיכים אם"ם כולם זרים לו אם"ם הוא ראשוני.
===פונקצית אוילר, משפט אוילר והמשפט הקטן של פרמה===
*פונקצית אוילר <math>\phi(n)</math> היא מספר המספרים הטבעיים שקטנים או שווים לn וזרים לו.
*'''משפט אוילר''' - יהיו שני מספרים טבעיים '''זרים''' <math>a<n</math>. אזי <math>a^{\phi(n)}\equiv 1</math> מודולו n.
**עבור <math>n>1</math>, מתקיים כי <math>a\in U_n</math> וגם <math>|U_n|=\phi(n)</math>.
**הסדר של איבר בחבורה סופית חייב לחלק את סדר החבורה, נסמן <math>o(a)=k</math> ולכן <math>\phi(n)=t\cdot k</math>.
**לכן <math>a^{\phi(n)} = (a^k)^t=1</math> כאשר הכפל נעשה ב<math>U_n</math>.
*'''המשפט הקטן של פרמה''' - יהי p ראשוני ומספר טבעי <math>a<p</math> אזי <math>a^{p-1}\equiv 1</math> מודולו p.
**זו מסקנה ישירה ממשפט אוילר (אמנם למעשה אוילר הוא הכללה של פרמה), כיוון ש <math>\phi(p)=p-1</math>.
*בפרט, בתנאי המשפט, <math>a^p\equiv a</math> מודולו p.
**למעשה התוצאה תקיפה לכל מספר טבעי <math>a^p\equiv a</math>, מודולו p נכון לכל ראשוני p ולכל טבעי a. **כיוון ש שאם a זר לp מתקיים כי גם השארית <math>r_a</math> זרה ל <math>p</math> ולכן <math>a^{\phi(n)p-1}\equiv rr_a^{\phi(n)p-1} \mod nequiv 1</math>מודולו p.**אם a אינו זר לp אזי הוא חייב להתחלק בראשוני p, וגם השארית ולכן <math>r</math> זרה ל <math>na^p\equiv a \equiv 0</math>מודולו p.
==הרצאה 6 הצפנה סימטרית (מפתח פרטי), הצפנה אסימטרית (מפתח ציבורי), RSA; פרק 7 מ[http://abstract.ups.edu/aata/ הספר]==
*[https://he.wikipedia.org/wiki/%D7%9E%D7%A4%D7%AA%D7%97_%D7%A6%D7%99%D7%91%D7%95%D7%A8%D7%99 הצפנה פומבית] - הצפנה ללא סוד מתואם מראש, באמצעות מפתחות פומביים (שכולם רואים).
*[https://en.wikipedia.org/wiki/Transport_Layer_Security פרקטית] הצדדים מעבירים מפתח סודי באמצעות הצפנה פומבית, ואז עוברים להצפנה סימטרית.
**אורך המידע (בהנחה שהוא אינו מרופד באפסים).
*אליס בוחרת שני ראשוניים גדולים <math>\{p,q\}</math> זה הסוד שלה.
*אליס מחשבת את המכפלה <math>n=p\cdot q</math>
*שימו לב: אמנם <math>4\equiv 3 1 \mod 13</math> אך <math>2^4 \not\equiv 2 \mod 3</math> כלומר לחשב את ההופכי של e מוד n זה אמנם קל, אך לא יעיל לשום דבר...
==הרצאה 7 המשך הצפנה - בדיקת ראשוניות, דיפי הלמן, חתימה, חישוב חזקות;==
*חלק מהותי בשיטות שאנו לומדים הוא מציאת ראשוניים גדולים. כיצד הדבר נעשה? האם יש רשימה גדולה של כל הראשוניים בעולם?
*ידוע שכמות הראשוניים עד המספר <math>n</math> היא בערך <math>\frac{n}{\ln(n)}</math>.
*טענה: אם <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>
*הגדרה:
**בהנתן מספר 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>p</math> נתאר מבחן '''הסתברותי''' הבודק האם הוא ראשוני**נבחר מספר <math>1<a<p</math>.**אם <math>a,p</math> אינם זרים, אז <math>p</math> אינו ראשוני '''בוודאות''' וסיימנו.**אחרת, לפי משפט פרמה הקטן <math>a^{pn-1}\equiv 1 \mod p</math>.**המספר <math>p-1</math> הוא זוגי (ביננו, אף אחד לא יבדוק האם <math>p=2</math> ראשוני).**נחלק את <math>p-1</math> ב2 שוב ושוב עד שנגיע למספר אי זוגי r ולכן <math>p-1=2^s\cdot r</math>**כעת נביט במספר <math>a^r \mod p</math>, ידוע שאם נעלה אותו בריבוע s פעמים נקבל 1 (אם p ראשוני כמובן).**כלומר אם נעלה אותו בריבוע שוב ושוב נקבל את סדרת המספרים <math>a^r,a^{2r},a^{4r},...,a^{2^s\cdot r}</math> (מוד p כמובן).**אם אחד האיברים בסדרה אינו <math>\pm 1</math> והבא אחריה הוא כן 1, סימן ש<math>p</math> אינו ראשוני '''בוודאות''' וסיימנו.**אם אף אחד מהחזקות אינה 1 סימן ש<math>p</math> אינו ראשוני '''בוודאות''' וסיימנו.**אחרת <math>a</math> הינו '''עד חזק''' לראשוניות של <math>pn</math>.
*אם <math>p</math> ראשוני אזי כל המספרים <math>1<a<p</math> הם עדים חזקים לכך.**הוכחה:***לפי אוילר <math>a^{p-1}\equiv 1 \mod p</math> .***אם נעלה את <math>a^r</math> בריבוע s פעמים נקבל <math>a^{2^s\cdot r}=a^{p-1}\equiv 1 \mod p</math>.***לכן אם <math>a^r\not \equiv 1 \mod p</math>, בשלב כלשהו נעלה מספר שאינו 1 בריבוע ונקבל 1, לכן מספר זה חייב להיות <math>-1</math>.
*אם <math>p</math> אינו ראשוני, ידוע שלכל היותר רבע מבין המספרים <math>a</math> יכולים להיות עדים חזקים.
*לכן הסיכוי שמצאנו עד חזק למרות שהמספר שאנו בודקים אינו ראשוני הוא רבע.
*אם נבחן k מספרים אקראיים שונים, הסיכוי שכולם יהיו עדים חזקים אך המספר אינו ראשוני הוא <math>\frac{1}{4^k}</math> (נמוך מאד).
*למדנו שבעזרת RSA ניתן להעביר פיסת מידע באופן בטוח בערוץ פומבי, ולרוב נרצה להעביר מפתח סודי לצורך הצפנה סימטרית.
*אלגוריתם דיפי-הלמן הוא שיטה לתיאום מפתח סודי בלבד ולא להעברת מידע.
*אליס ובוב מתאמים מספר ראשוני גדול <math>p</math> שאינו סודי כמובן.
*כמו כן הם מתאמים יוצר <math>g</math> של <math>U_p</math> (כלומר <math>U_p=<g></math>), או לפחות איבר מסדר מאד גדול(בהמשך יש הסבר כיצד אפשר לעשות זאת).
*כעת אליס בוחרת מספר אקראי סודי <math>a\leq p-1</math> ושולחת לבוב את <math>g^a \mod p</math>.
*בוב בוחר מספר אקראי סודי <math>b\leq p-1</math> ושולח לאליס את <math>g^b \mod p</math>.
**נבחר את p להיות מספר ראשוני "בטוח", כלומר <math>p=2q+1</math> כאשר <math>q</math> ראשוני.
**כעת ב<math>|U_p|=2q</math> ולכן הסדר של כל איבר ב<math>U_p</math> הוא אחד מבין <math>1,2,q,2q</math>.
**נגריל איבר <math>g\neq \pm 1</math> כך ש(לכן <math>g^2\not\equiv 1 \mod p</math> ) וגם <math>g^q\not\equiv 1 \mod p</math>.
**האיבר שבחרנו הוא יוצר.
*פונקציות גיבוב (hash) - מעבירות קלט בגודל אקראי לקלט באורך קבוע.
*סיפרנו על אליס שייצרה מפתח פומבי <math>(n,e)</math>, ושמרה לעצמה את הערכים הסודיים <math>m,d</math>
*כעת בוב שרוצה לשלוח לה מידע ולהבטיח אליס רוצה להבטיח את זהותו זהותה ואת אמינות המידע, מייצר באופן דומה מפתח פומבי <math>(n',e')</math> ושומר ערכים סודיים <math>m',d'</math>*בוב מעביר היא מעבירה את המידע שלו שלה דרך פונקצית גיבוב ומקבל ומקבלת את הערך המגובב <math>a</math>.*בוב מחשב אליס מחשבת את <math>y=a^{d'} \mod n'</math> ושולח לאליס ושולחת אותו בנוסף למידע.*אפילו בהנתן <math>a</math> לא ניתן לחשב את <math>d'</math> (זו בעיית הלוגריתם הדיסקרטי).*אף אחד אחר לא יכול לחשב את y כיוון ש <math>d'</math> סודי.
*כעת אליס מחשבת בוב שרוצה לוודא את אמינות המידע מחשב את <math>a=y^{e'} \mod n'</math> ומוודאת ומוודא כי המידע שהיא קיבלה שהוא קיבל הוא המידע שבוב התכוון שאליס התכוונה לשלוח עד כדי המקרה הבלתי סביר של התנגשות.*אף אחד אחר לא יכל ליצור את הוכחת אמינות המידע הזו פרט לבובלאליס.
*שימו לב שעל מנת למנוע תקיפת 'אדם באמצע' באמצעות חתימה המפתחות הפומביים צריכים להיות מאומתים על פני ערוץ מאובטח (מקודדים בתוך הדפדפן למשל).
*[http://abstract.ups.edu/aata/section-method-of-repeated-squares.html שיטת הריבועים החוזרים] לחישוב חזקה.
*לדוגמא, אנו מעוניינים לחשב את <math>x^{41} \mod n</math> במעט פעולות
**<math>x^{41}=x^{2^5}\cdot x^{2^3}\cdot x</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 העלאות בריבוע, ושלוש הכפלות, במקום 41 40 הכפלות.
===הרצאות הרצאה 8-9 משפט האיזומורפיזםתת חבורות נורמליות, חבורות מנה, גרעין; פרקים 10,11 מ[http://abstract.ups.edu/aata/ הספר]===
*תהי חבורה G ותהי תת חבורה N. תת החבורה N נקראת '''נורמלית''' אם לכל <math>a\in G</math> מתקיים כי <math>aN=Na</math>.
*ברור שבחבורה אבלית כל חבורה היא תת חבורה נורמלית.
*דוגמא:
**נביט בחבורה הסימטרית <math>G=S_3</math> ובתת החבורה <math>NH=<(1\ 2)>=\{(1),(1\ 2)\}</math>.**אזי <math>(1\ 3)NH=\{(1\ 3), (3\ 1\ 2)\}</math> אך <math>NH(1\ 3)=\{(1\ 3),(2\ 1\ 3)\} </math> וקל לראות כי <math>(1\ 3)NH\neq NH(1\ 3)</math>.
**אזי N תת חבורה לא נורמלית!
*דוגמא נוספת:
**נביט בחבורה הסימטרית <math>G=S_3</math> ובתת החבורה <math>N=<(1\ 2\ 3)></math> שהיא תת החבורה של כל התמורות הזוגיות במקרה זה.
**קל לוודא שלכל תמורה זוגית מתקיים <math>fN=Nf=N</math> ולכל תמורה אי-זוגית מתקיים <math>fN=Nf</math> שווה לקבוצת כל התמורות האי-זוגיות.
*הוכחה - הכלה דו כיוונית:
**יהי <math>anbk\in (aN)(bN)</math> כיוון ש <math>bN=Nb</math> אזי <math>anbk=abmk\in abN</math>.
**יהי <math>abn\in abN</math> כיוון ש <math>bN=Nb</math> אזי <math>abn=amb=ambeaebn\in (aN)(bN)</math>.
*יהי הומומורפיזם בין חבורות <math>\varphif:G\to H</math>. נגדיר את '''הגרעין''' <math>\ker(\varphif)=\{a\in G|\varphif(a)=e_H\}</math>.*הגרעין הוא תת-חבורה נורמלית של <math>G</math>.*הוכחה - נסמן <math>K=\ker(\varphif)</math>*טענה:**ראשית עלינו להוכיח שמדובר בתת-חבורה: אכן <math>e_G\in K</math> ואם לכל <math>a,b\in KG</math> אז מתקיים כי <math>aK=\left\varphi(ab^{-1})=b\varphiin G|f(a)\left(\varphi=f(b)\right)^{-1\}=e_H</math>.*הוכחה:*כעת *בכיוון ראשון, יהי <math>aak\in GaK</math> עלינו להוכיח כי אזי <math>aKf(ak)=Kaf(a)f(k)=f(a)e_H=f(a)</math>. נעשה הכלה בכיוון אחד, הכיוון השני דומה.**בכיוון שני, יהי <math>akb\in aK</math> רוצים למצוא <math>m\in KG</math> כך ש <math>akf(a)=maf(b)</math>. **לכן עלינו לבחור אזי <math>m=akaf(a^{-1}b)=e_H</math>, נותר להוכיח שאכן ולכן <math>ma^{-1}b=k\in K</math>.**אכן ולכן <math>\varphi(m)b=ak\varphi(aka^{-1})=\varphi(a)e_H\left(\varphi(a)\right)^{-1}=e_Hin aK</math>.
*'''משפט האיזומורפיזם הראשון'''. יהי כיוון שהוכחה דומה עובדת מהצד השני, נובע כי <math>\varphi:G\to HaK=Ka</math> איזומורפיזם בין חבורותולכן הגרעין הינו תת חבורה נורמלית. אזי <math>G/\ker(\varphi)\cong im(\varphi) </math>
==הרצאה 9 משפט האיזומורפיזם, מבוא לקידוד; פרק 11 מ[http://abstract.ups.edu/aata/ הספר]==
*'''משפט האיזומורפיזם הראשון'''. יהי <math>\varphi:G\to H</math> הומומורפיזם בין חבורות. אזי <math>G/\ker(\varphi)\cong im(\varphi) </math>
*הוכחה:
**לצורך הנוחות נסמן <math>K=\ker(\varphi)</math> ו<math>M=im(\varphi)</math>.
**עלינו להראות שקיים איזומורפיזם (כלומר הומומורפיזם חח"ע ועל) <math>f:G/K\to M</math>.
**לכל <math>aK\in G/K</math> נגדיר <math>f(aK)=\varphi(a)</math>.
**ראשית, עלינו להוכיח כי מדובר בפונקציה מוגדרת היטב. כלומר, בהנתן <math>a,b\in G</math>, אם <math>aK=bK</math> עלינו להוכיח כי <math>f(aK)=f(bK)</math>.
***<math>a=ae\in aK</math> ולכן <math>a\in bK</math>. כלומר קיים <math>k\in K</math> כך ש <math>a=bk</math>.
***<math>\varphi(a)=\varphi(bk)=\varphi(b)\varphi(k)=\varphi(b)</math>.
***<math>f(aK)=\varphi(a)=\varphi(b)=f(bK)</math>.
**כעת, עלינו להוכיח ש<math>f</math> הינו הומומורפיזם.
***<math>f\left((aK)(bK)\right)=f(abK)=\varphi(ab)=\varphi(a)\varphi(b)=f(aK)f(bK)</math>
**עכשיו נוכיח ש<math>f</math> על.
***לכל איבר בתמונה <math>h\in M</math> קיים מקור <math>g\in G</math>. לכן <math>f(gK)=\varphi(g)=h</math>.
**ולבסוף, נוכיח ש<math>f</math> חח"ע.
***יהיו <math>aK,bK\in G/K</math> כך ש <math>f(aK)=f(bK)</math> עלינו להוכיח כי <math>aK=bK</math>.
***נתון <math>\varphi(a)=\varphi(b)</math> צ"ל <math>aK=bK</math>. שימו לב שלא צריך להוכיח כי <math>a=b</math>; אכן <math>\varphi</math> לא חייב להיות חח"ע.
***נראה הכלה בכיוון אחד, הכיוון השני דומה.
***יהי <math>ak\in aK</math> צ"ל <math>ak\in bK</math>.
***קל לראות ש <math>ak=bb^{-1}ak</math>, עלינו להוכיח כי <math>b^{-1}ak\in K</math>.
***אכן <math>\varphi(b^{-1}ak)=\left(\varphi(b)\right)^{-1}\varphi(a)\varphi(k)=\left(\varphi(a)\right)^{-1}\varphi(a)=e_H</math>
*דוגמא.
*נגדיר את הפונקציה <math>\varphi:\mathbb{Z}\to \mathbb{Z}_n</math> על ידי <math>\varphi(a)=a\mod n</math> (השארית של החלוקה של a בn).
*נוכיח שמדובר בהומומורפיזם.
**יהיו <math>a,b\in\mathbb{Z}</math> לפי ההגדרה <math>\varphi(a+b)= a+b \mod n</math>.
**נשים לב כי <math>a=\varphi(a)+kn, b=\varphi(b)+mn</math>.
**לכן <math>a+b\equiv \varphi(a)+\varphi(b) \mod n</math>.
**סה"כ <math>\varphi(a+b)=\varphi(a)+\varphi(b)</math> כיוון שהם שקולים מודולו n, ואנו עוסקים בחבורה <math>\mathbb{Z}_n</math>.
*כעת מתקיים כי <math>\ker\varphi=n\mathbb{Z}=\{na|a\in\mathbb{Z}\}</math>.
*לכן <math>\mathbb{Z}/n\mathbb{Z}\cong \mathbb{Z}_n</math>
*שאלה - האם בחיבור <math>1+7+5+8</math> ב<math>\mathbb{Z}_9</math> חשוב לבצע את פעולת המודולו בכל חיבור, או שמותר בסוף?*<math>\mathbb{Z}_9</math> איזומורפית לחבורה <math>\{0+9\mathbb{Z},...,8+9\mathbb{Z}\}</math>*נביט ב <math>(1+9\mathbb{Z})+(7+9\mathbb{Z})+(5+9\mathbb{Z})+(8+9\mathbb{Z})</math>*הוכחנו כי <math>(aN)(bN)=abN</math>. לכן <math>(1+9\mathbb{Z})+(7+9\mathbb{Z})+(5+9\mathbb{Z})+(8+9\mathbb{Z})=21+9\mathbb{Z}</math>.*כיוון ש <math>\varphi(21)=\varphi(3)</math>, נובע לפי הוכחת משפט האיזומורפיזם הראשון כי <math>21+9\mathbb{Z}=3+9\mathbb{Z}</math>, כלומר אכן מותר לעשות את המודולו בסוף. ===מבוא לקידוד===*קוד ISBN בעל 10 ספרות, כאשר הספרה האחרונה היא ספרת ביקורת.*הספרות שייכות לחבורה <math>\mathbb{Z}_{11}</math>, כאשר 9 הספרות הראשונות הן 0-9 והאחרונה יכולה להיות גם X.*קוד תקין מקיים את הנוסחא <math>10x_1+9x_2+...+x_{10}=0</math> (שימו לב שמדובר בפעולות מודולו 11).*לכן חישוב ספרת הביקורת הוא <math>x_{10}=-\left(10x_1+...+2x_9\right)</math>.*אם ספרה אחת בלבד מהקוד תשתנה בטעות, הקוד בוודאות לא יהיה תקין.**אם נחליף את <math>x_i</math> בספרה <math>y_i</math> על מנת שהקוד החדש יהיה תקין צריך ש <math>a_i(y_i-x_i)=0</math>, אבל <math>a_i\neq 0</math> ו<math>\mathbb{Z}_{11}</math> הוא שדה.*אם נחליף במיקום של זוג ספרות כלשהן נקבל קוד בלתי תקין.**<math>a_ix_i+a_jx_j-a_ix_j-a_jx_i=(a_i-a_j)(x_i-x_j)\neq 0</math>.*שימו לב שקוד זה מוגבל במספר הספרות, ואכן כשהוסיפו ספרות שינו אותו באופן דומה במידה מסוימת לתעודת הזהות שנלמד בהמשך. ==הרצאה 10 קידוד; פרק 8 מ[http://abstract.ups.edu/aata/ הספר]==*תעודת זהות בישראל.*עבור ספרת הביקורת של תעודת הזהות אנו לא מרשים שימוש בספרה X ולכן עובדים ב<math>\mathbb{Z}_{10}</math>.*הבעייה - זה אינו שדה ויש מחלקי אפס. למשל <math>5\cdot 0 = 5\cdot 2</math>, לכן הקוד לעיל לא יזהה בהכרח החלפת ספרה.*תאור מילולי של חישוב ספרת ביקורת (אלגוריתם Luhn):**לכל ספרה בתעודת הזהות ניתן משקל - 2 עבור הספרה הימנית ביותר (שאינה ספרת הביקורת) 1 עבור הבאה, וכך הלאה בסירוגין.**נכפיל כל ספרה במשקל שלה, אם הכפלנו ספרה ב2 וקיבלנו מספר בן שתי ספרות - נסכום את הספרות.**נסכום את כל התוצאות הללו.**המספר הקטן ביותר שנוסיף לסכום לעיל על מנת להשלים אותו לכפולה שלימה של 10, הוא ספרת הביקורת.*לדוגמא - מספר התעודת הזהות הראשון שניתן הוא 1. נכפול ב2 ונקבל 2. נשלים ל10 וספרת הביקורת היא 8, לכן תעודת הזהות היא 18.*לדוגמא - נניח שתעודת הזהות היא 1789 (כמובן ללא ביקורת). אזי 9 כפול 2 זה 18, ולכן נסכום 9, 8 כפול 1 זה 8, 7 כפול 2 זה 14 שנותן 5, ו1 כפול 1 זה 1.**סה"כ קיבלנו 9+8+5+1=22 ולכן ספרת הביקורת היא 8. *תאור מתמטי:*ראשית נביט בכפל ב2 **הספרות <math>\{0,1,2,3,4\}</math> נשלחות לספרות <math>\{0,2,4,6,8\}</math> בהתאמה. **הספרות <math>\{5,6,7,8,9\}</math> נשלחות לספרות <math>\{1,3,5,7,9\}</math> בהתאמה.**הספרות <math>\{5,6,7,8,9\}</math> כפול 2 שוות ל <math>10+x</math> ונשלחות ל<math>1+x</math>. **נשים לב כי פעמיים הספרה שקול ל <math>x</math> מודולו 10.**סה"כ הגדרנו את הפונקציה הבאה על הספרות <math>f(a)=\begin{cases}2a & a\leq 4 \\ 2a+1 & a\geq 5\end{cases}</math>.*שימו לב שכפל רגיל ב2 לא היה עובד, כיוון ש<math>2\cdot 5 = 2\cdot 0</math>. *מדוע אם כך בחרנו דווקא במשקל 2 שאינו זר ל 10 (ולכן אינו הפיך)?**ההפיכים מודולו 10 הם אי זוגיים. **ההפרש בין כל שניים מהם הוא זוגי, ולכן כל חילוף של שתי ספרות בהפרש 5 לא היה מתגלה.** לדוגמא נניח כי המשקלים הם 1 ו3. **<math>1\cdot a+3\cdot (a+5)=a+3a+15=1\cdot(a+5)+3\cdot a</math>. *נניח שספרות תעודת הזהות הן <math>x_9,...,x_1</math> כאשר <math>x_1</math> היא ספרת הביקורת והימנית ביותר.*לפי החישוב לעיל ספרת הביקורת נבחרה כך ש <math>x_9+f(x_8)+x_7+...+f(x_2)+x_1=0</math>.*נעביר אגף ונקבל נוסחא לספרת הביקורת. *קל לראות שתעודת זהותשנפלה בה טעות בספרה אחת אינה תקינה יותר. **אם הספרה השונה היא במקום אי זוגי אז <math>1\cdot x_i\neq 1\cdot yi</math>.**אם הספרה השונה היא במקום אי זוגי אז <math>f(x_i)\neq f(y_i)</math> כיוון ש<math>f</math> חח"ע.*אם החלפנו את הספרות 0, 9 במקומות סמוכים לא נזהה את השגיאה.**אכן, <math>1\cdot 0 + f(9) = 9 = 1\cdot 9 + f(0)</math>.*אם החלפנו שתי ספרות שונות במקומות סמוכים שאינן הזוג 0,9 אז נזהה את השגיאה.**אם שתי הספרות קטנות או שוות ל4, נקבל <math>x_i+2x_j-x_j-2x_i=x_j-x_i\neq 0</math>.**אם שתי הספרות גדולות או שוות ל5 נקבל <math>x_i+2x_j+1-x_j-2x_i-1=x_j-x_i\neq 0</math>.**אם <math>0\leq x_i\leq 4</math> אבל <math>5\leq x_j\leq 9</math> נקבל <math>x_i+2x_j+1-x_j-2x_i=x_j-x_i+1</math>.**הדרך היחידה ש<math>x_j-x_i+1=0</math>היא אם <math>x_j-x_i=9</math> וזה בדיוק הזוג 0,9. ===קוד לינארי===*המידע שאנו מעוניים לשלוח הוא וקטור של ביטים <math>\mathbb{Z}_2^k</math>.*נכפיל את המידע במטריצה הבינארית <math>G=\begin{pmatrix} I_k \\ A\end{pmatrix}</math> ונקבל קוד ב<math>\mathbb{Z}_2^n</math>.*דוגמא **נביט במטריצה <math>G=\begin{pmatrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1\\ 1 & 1 & 1\end{pmatrix}</math>.**כפל במטריצה זו מוסיף למידע באורך 3 ביט יתירות הבודק זוגיות (parity bit). *עבור <math>G=\begin{pmatrix} I_k \\ A\end{pmatrix}</math> נגדיר את המטריצה <math>H=\begin{pmatrix}A & I_{n-k}\end{pmatrix}</math>.*טענה: *לכל וקטור <math>Hv=0</math> אם ורק אם <math>v</math> הוא מהצורה <math>v=Gx</math>.**הוכחה:**כיוון ראשון:***נוכיח ראשית ש<math>HG=0</math>, ולכן ברור שאם <math>v=Gx</math> אזי <math>Hv=0</math>.***<math>HG=\begin{pmatrix}A & I_{n-k}\end{pmatrix}\begin{pmatrix}I_k \\ A\end{pmatrix}=A+A=0</math> (זכרו שאנו מעל השדה <math>\mathbb{Z}_2</math>).**בכיוון ההפוך:***נניח כי <math>Hv=0</math> ונסמן <math>v=\begin{pmatrix}x\\u\end{pmatrix}</math> כאשר <math>x\in\mathbb{Z}_2^k</math>.***נוכיח כי <math>Gx=v</math>.***נסמן <math>Gx=\begin{pmatrix}x\\u'\end{pmatrix}</math>, צריך להוכיח כי <math>u=u'</math>.***נתון כי <math>Hv=0</math>, ומכיוון קודם ידוע כי <math>HGx=0</math> ולכן ביחד <math>H(Gx-v)=0</math>.***לכן <math>0=H(Gx-v)=H\begin{pmatrix}0\\u'-u\end{pmatrix}=\begin{pmatrix}A & I_{n-k}\end{pmatrix}\begin{pmatrix}0\\u'-u\end{pmatrix}=u'-u</math>**כלומר קוד <math>v</math> הינו תקין אם ורק אם <math>Hv=0</math>. *שימו לב כי נובע מההוכחה לעיל שעבור וקטור מידע <math>x</math> יש בדיוק וקטור יתירות יחיד <math>u</math> עבורו <math>\begin{pmatrix}x\\u\end{pmatrix}</math> תקין.*כלומר, ניתן לזהות כל כמות טעויות המשנה אך ורק את וקטור היתירות. ==הרצאה 11 המשך קידוד; פרק 8 מ[http://abstract.ups.edu/aata/ הספר]== *עד כה הראנו שיש לנו דרך לקודד מידע ולוודא שהמידע שהגיע הוא קוד תקין.*השאלה: כיצד שגיאות עשויות להשפיע על הקוד? כמה שגיאות יכולות להעביר אותנו ממילה חוקית אחת לאחרת?*מרחק המינג- המרחק בין שני וקטורים ב<math>\mathbb{Z}_2^n</math> הוא כמות העמודות בהן הם נבדלים.**דוגמא: <math>d((1,0,1,0),(0,1,1,0))=2</math>. *נסמן ב<math>d_{min}</math> את המרחק הקטן ביותר בין שתי מילים חוקיות כלשהן <math>Gx_1,Gx_2</math>.*טענה: אם <math>d_{min}\geq 2n+1</math> אז הקוד מסוגל לזהות עד <math>2n</math> שגיאות ולתקן עד <math>n</math> שגיאות.*הוכחה:**אם כמות השגיאות קטנה או שווה ל<math>2n</math> המילה שהתקבלה בוודאות אינה חוקית, כיוון שהמרחק המינימלי בין שתי מילים חוקיות גדול או שווה ל<math>2n+1</math>.**אם כמות השגיאות קטנה או שווה ל<math>n</math> יש בדיוק מילה חוקית אחת שיכולה להיות המקור. **אחרת, ניתן להגיע ע"י n שגיאות משתי מילים חוקיות למילה שקיבלנו, כלומר המרחק בין שתי המילים החוקיות קטן או שווה ל<math>2n</math>, בסתירה. *דוגמא: בקוד ביט parity מתקיים כי <math>d_{min}=2</math> והקוד יכול לזהות שגיאה אחת ולא לתקן בכלל. *טענה:*הקוד מסוגל לזהות לפחות שגיאה אחת אם ורק אם ב<math>H</math> אין עמודת אפסים.**הוכחה:**תהי מילה חוקית <math>v</math> ונוסיף לה שגיאה אחת בדיוק <math>v+e_i</math>.**אזי <math>H(v+e_i)=Hv+He_i=0+C_i(H)</math>. *טענה:*<math>d_{min}\geq 3</math> אם ורק אם ב<math>H</math> אין עמודת אפסים וגם אין שתי עמודות זהות.*במקרה זה ניתן לזהות לפחות שתי שגיאות, ולתקן לפחות שגיאה אחת.**הוכחה:**תהי מילה חוקית <math>v</math> ונוסיף לה שתי שגיאות <math>v+e_i+e_j</math>.**אזי <math>H(v+e_i+e_j)=C_i(H)+C_j(H)</math>.**זה שווה אפס (כלומר המילה החדשה חוקית) אם ורק אם <math>C_i(H)=C_j(H)</math>. *הערה:*נניח שהוספנו <math>n-k</math> ביטים למידע, זה משאיר ל<math>A</math> כמות של <math>2^{n-k}-(n-k)-1</math> עמודות שיכולות להיות שונות מאפס, ושונות מהעמודות של <math>I_{n-k}</math>.*כלומר על מנת לתקן שגיאה אחת, כמות הביטים שעלינו להוסיף לוגריתמית ביחס לכמות המידע. *דוגמא (קוד המינג)*<math>H=\begin{pmatrix} 0 & 1 & 1 & 1 & 1& 0 & 0\\ 1& 0 & 1&1&0&1&0\\1&1&0&1&0&0&1\end{pmatrix}</math>*כיוון שסכום שלושת העמודות הראשונות הוא אפס <math>d_{min}\leq 3</math>.*מצד שני, כיוון שאין ב<math>H</math> שתי עמודות זהות <math>d_{min}\geq 3</math>.*ביחד <math>d_{min}= 3</math>. *מציאת שגיאה, בהנתן שהתרחשה בדיוק שגיאה אחת:*נניח שהמילה שנשלחה היא <math>v</math> והמילה שהתקבלה היא <math>v+e_i</math>.*לכן <math>H(v+e_i)=C_i(H)</math>.*כלומר מיקום העמודה במטריצה <math>H</math> הוא מיקום הטעות. *דוגמא:*<math>v=Gx=\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\\0 & 1 & 1 & 1\\1& 0 & 1&1\\1&1&0&1\end{pmatrix}\begin{pmatrix}1\\1\\0\\1\end{pmatrix}=\begin{pmatrix}1\\1\\0\\1\\0\\0\\1\end{pmatrix}</math>*נניח שהתקבלה בצד השני המילה יחד עם טעות אחת <math>u=\begin{pmatrix}1\\0\\0\\1\\0\\0\\1\end{pmatrix}</math>.*נחשב <math>Hu=\begin{pmatrix}1\\0\\1\end{pmatrix}</math>.*כך אנו יודעים שהטעות הייתה בביט השני.
checksum בפרוטוקולי IP, TCP, UDP.
==הרצאה 12 חוג הפולינומים; פרקים 16,17 מ[http://abstract.ups.edu/aata/ הספר]==
*תזכורת: חוג הוא קבוצה <math>R</math> עם פעולות חיבור וכפל, כך שהוא חבורה חילופית ביחד לחיבור, מקיים אסוציאטיביות בכפל, מכיל איבר יחידה ואת חוק הפילוג. ===הרצאה 11 חוג הפולינומים; פרקים 16=== *יהי <math>\mathbb{F}</math> שדה,17 אזי <math>\mathbb{F}[x]</math> הוא חוג הפולינומים עם פעולות כפל וחיבור רגילות.**כלומר <math>\mathbb{F}[x]=\{a_nx^n+...+a_1x+a_0|n\in\mathbb{N},a_i\in\mathbb{F}\}</math>.*עבור פולינום <math>a_nx^n+...+a_1x+a_0</math> כאשר <math>a_n\neq 0</math> אומרים ש'''הדרגה''' שלו היא <math>n</math>.*עבור פולינום האפס אפשר להגיד שדרגתו היא <math>-1</math>. *טענה (חלוקה עם שארית): יהיו שני פולינומים <math>f(x),g(x)\in\mathbb{F}[x]</math> כך ש<math>g(x)</math> אינו פולינום האפס, אזי קיימים פולינומים יחידים <math>q(x),r(x)</math> כך ש:**<math>f(x)=q(x)g(x)+r(x)</math>.**<math>\deg(r(x))<\deg(g(x))</math>.*הוכחה:*קיום:**יהי <math>g(x)</math> כזה. **אם <math>\deg(f)<\deg(g)</math> אזי <math>f=0\cdot g + f</math>.**אם <math>\deg(f)\geq\deg(g)</math> נוכיח באינדוקציה על הדרגה של <math>f</math>.**נסמן <math>f(x)=a_nx^n+...+a_0</math>, <math>g(x)=b_mx^m+...+b_0</math> כאשר נתון <math>n\geq m</math>.**הפולינום <math>f(x)-\frac{a_n}{b_m}x^{n-m}g(x)</math> הוא מדרגה קטנה ממש מ<math>n</math> ולכן מקיים את הטענה לפי הנחת האינדוקציה.**לכן <math>f(x)-\frac{a_n}{b_m}x^{n-m}g(x)=q(x)g(x)+r(x)</math>.**לכן <math>f(x)=(\frac{a_n}{b_m}x^{n-m}+q(x))g(x)+r(x)</math>.*יחידות:**נניח <math>f(x)=q_1(x)g(x)+r_1(x)=q_2(x)g(x)+r_2(x)</math>.**לכן <math>(q_1(x)-q_2(x))g(x)=r_1(x)-r_2(x)</math>.**אבל <math>\deg(r_1(x)-r_2(x))<\deg(g(x))</math> ולכן <math>q_1(x)-q_2(x)=0</math> ולכן גם <math>r_1(x)-r_2(x)=0</math>. *מסקנה: עבור פולינום <math>f(x)</math> ועבור נקודה <math>a\in\mathbb{F}</math> מתקיים כי <math>f(a)=0</math> אם"ם קיים פולינום <math>q(x)</math> כך ש <math>f(x)=q(x)(x-a)</math>.*במילים: a הינו שורש של הפולינום f אם"ם הפולינום f מתחלק בפולינום x-a.*הוכחה:**לפי משפט החלוקה עם שארית קיימים פולינומים <math>q(x),r(x)</math> כך ש:***<math>f(x)=q(x)(x-a)+r(x)</math>.***<math>\deg(r(x))<\deg(x-a)=1</math>, כלומר <math>r(x)=r\in\mathbb{F}</math> הוא קבוע.**נציב <math>a</math> ונקבל <math>f(a)=r</math>.**לכן <math>f(x)=q(x)(x-a)</math> אם ורק אם <math>f(a)=0</math>. ===קודים פולינומיים=== *כעת נביט בפולינומים מעל השדה הבינארי <math>\mathbb{Z}_2[x]</math>.*כל פולינום מדרגה n מתאים לוקטור המקדמים ב<math>\mathbb{Z}_2^{n+1}</math>.*למשל, וקטור המידע <math>10110</math> מתאים לפולינום <math>x^4+x^2+x</math>. *נקבע פולינום <math>g(x)\in\mathbb{Z}_2[x]</math> כלשהו מדרגה m.*עבור מידע <math>f(x)</math> נבצע חלוקה עם שארית של <math>x^m\cdot f(x)</math> ב<math>g(x)</math>*<math>x^m\cdot f(x) =q(x)g(x)+r(x)</math>.*המילה שנשלח היא <math>x^m\cdot f(x) + r(x)</math> (שימו לב כי <math>r(x)=-r(x)</math>).*המילה תקינה אם ורק אם היא מתחלקת ב<math>g(x)</math>.*זהו קוד לינארי:**אם <math>f(x),h(x)</math> מתאימים לוקטורי מידע, <math>f(x)=q_1(x)g(x)+r_1(x)</math> ו<math>h(x)=q_2(x)g(x)+r_2(x)</math> אז השארית של <math>f(x)+h(x)</math> היא <math>r_1(x)+r_2(x)</math>.*קוד זה מוסיף m ביטים של יתירות למידע. *דוגמא:*נבחר את הפולינום <math>g(x)=x^3+x+1</math> (מוסיף 3 ביטי יתירות).**נקודד מידע:***נניח כי המידע שלנו הוא <math>1010</math> כלומר הפולינום <math>f(x)=x^3+x</math>.***לכן עלינו לחלק את הפולינום <math>x^3\cdot f(x) =x^6+x^4</math> בפולינום <math>g(x)=x^3+x+1</math>.***לאחר אלגוריתם חלוקה עם שארית נקבל <math>x^6+x^4=(x^3+1)(x^3+x+1)+x+1</math>.***לכן סה"כ המידע שנשלח הוא <math>x^3\cdot f(x) + r(x)=x^6+x^4+x+1</math> שזה בעצם <math>1010011</math>.**נבדוק תקינות מידע:***האם המידע <math>1101101</math> תקין?***זה בעצם הפולינום <math>x^6+x^5+x^3+x^2+1</math>, זה קוד תקין אם"ם הוא מתחלק ב<math>g(x)</math>.***נבצע חלוקה עם שארית ונקבל שארית <math>x^2</math>, לכן הקוד אינו תקין. ==הרצאה 13 קודים ציקליים; פרק 22 מ[http://abstract.ups.edu/aata/ הספר]== ===קידוד פולינומי ציקלי===חלוקה *עבור הקידוד הציקלי נקבע את הפרמטרים הבאים:**יהי k אורך המידע, כלומר נקודד פולינומים עד דרגה <math>k-1</math> בלבד.**יהי g פולינום מדרגה m, לפי נקודד קידוד פולינומי.**נסמן את אורך המילה המקודדת ב<math>n=k+m</math>.**מילה היא חוקית אם ורק אם היא מהצורה <math>h(x)g(x)</math> כאשר <math>deg(h(x))<k</math> *קוד נקרא ציקלי אם לכל מילה חוקית <math>(a_{n-1}\ a_{n-2}\ \cdots\ a_1\ a_0)</math> גם ההזזה הציקלית <math>(a_{n-2}\ a_{n-3}\ \cdots\ a_0\ a_{n-1})</math> היא מילה חוקית. *נתאר את ההזה הציקלית באמצעות פעולה אלגברית.**יהי <math>f(x)=a_{n-1}x^{n-1}+...+a_0</math>**אזי <math>x\cdot f(x) \equiv a_{n-2}x^{n-1}+...+a_0x+a_{n-1} \mod x^n-1</math>**כלומר ההזזה הציקלית של <math>f(x)</math> היא השארית של <math>x\cdot f(x)</math> בחלוקה ב<math>x^n-1</math>.**הוכחה:***אכן <math>x\cdot f(x)= a_{n-1}x^n+...+a_0x=a_{n-1}(x^n-1) + a_{n-1} + a_{n-2}x^{n-1}+...+a_0x</math> *במילים פשוטות: **יהי <math>f(x)=a_{n-1}x^{n-1}+...+a_0</math>**אם <math>a_n=0</math> אזי ההזזה הציקלית היא <math>x\cdot f(x)</math>**אם <math>a_n=1</math> אזי ההזה הציקלית היא <math>x\cdot f(x) +x^n +1</math>***(מכבים את הביט האחרון, ומוסיפים ביט ראשון) *משפט: הפולינום <math>g(x)</math> מחלק את <math>x^n+1</math> אם ורק אם הקוד הפולינומי הינו ציקלי.*שימו לב: n הוא אורך המילה המקודדת, שכולל הן את המידע והן את היתירות.**הוכחה:**בכיוון ראשון, נניח כי הקוד הוא ציקלי:***<math>x^{k-1}g(x)</math> היא מילה חוקית***כיוון שהקוד ציקלי, גם ההזזה הציקלית <math>x\cdot x^{k-1}g(x)+x^n+1</math> חוקית***כלומר <math>x^k g(x)+x^n+1=h(x)g(x)</math>***לכן <math>x^n+1=(h(x)+x^k) g(x)</math>, כפי שרצינו.**בכיוון שני, נניח כי <math>x^n+1=t(x)g(x)</math>***נשים לב כי <math>deg(t(x))=k</math>***תהי מילה חוקית <math>h(x)g(x)</math>***אם <math>deg(h\cdot g)<n</math> אז ההזזה הציקלית היא <math>xh(x)g(x)</math> והיא מילה חוקית כי <math>deg(xh(x))<k</math>***אחרת, נניח כי <math>deg(h\cdot g)=n</math> ולכן ההזזה הציקלית היא <math>xh(x)g(x)+x^n+1</math>***כלומר ההזזה הציקלית היא <math>xh(x)g(x)+t(x)g(x)=(xh(x)+t(x))\cdot g(x)</math>***כיוון ש <math>deg(xh(x))=deg(t(x))=k</math> נובע כי <math>deg(xh(x)+t(x))<k</math>***לכן <math>(xh(x)+t(x))\cdot g(x)</math> מילה חוקית, כפי שרצינו. *משפט: קוד פולינומי ציקלי עם שאריתפולינום <math>g(x)</math> מדרגה <math>m</math> מסוגל לזהות כל כמות של שגיאות, בתנאי שכולן נמצאות בתוך טווח של <math>m</math> ביטים.*הוכחה: **נניח שקרו טעויות בתוך טווח של <math>m</math> ביטים.**אם המילה החדשה חוקית, גם כל הזזה ציקלית שלה היא חוקית.**נזיז את <math>m</math> הביטים כך שיהיו בקצה הימני במקום של היתירות.**כיוון שהיתירות היא יחידה, בוודאות המילה אינה חוקית, אידיאליםסתירה.
*דוגמא:*<math>x^7-1=(1+x)(1+x+x^3)(1+x^2+x^3)</math>*לכן הקוד הנוצר על ידי הפולינום <math>g(x)==הרצאה 12 קודים ציקליים; פרק 22 מ[http:1+x+x^3<//abstractmath> עבור וקטורי מידע באורך 4 הוא ציקלי.ups.edu/aata/ הספר]===