[[89-214 תשעח סמסטר א|חזרה לדף הקורסקטגוריה:מערכי לימוד]]
=ספר הקורס=
ההרצאות מבוססות באופן כללי על הספר [http://abstract.ups.edu/aata/ Abstarct Algebra - Theory and Applications by Thomas W. Judson]
* [[מדיה:19CSASnotes.pdf|סיכום ההרצאות מ2019 ע"י ספיר ביתן]]
* [[מדיה:21CSASnotes.pdf|סיכום ההרצאות מ2021 ע"י רועי אוסקר]]
=מבחנים לדוגמא=
*[[מדיה: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>\mathbb{Z}</math> חבורת השלמים עם חיבור.
**<math>\mathbb{Z}_n</math> חבורת השאריות עם חיבור מודולו n.
===מכפלה קרטזית של חבורות===
*תהיינה חבורות <math>G,H</math> המכפלה הקרטזית של החבורות <math>G\times H</math> (אוסף הזוגות הסדורים) היא חבורה עם הפעולה הבאה:
<math>(g_1,h_1)\cdot_{G\times H}(g_2,h_2)=(g_1\cdot_G g_2,h_1\cdot_H h_2)</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>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>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>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>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>.
===המחלק המשותף הגדול ביותר===
===RSA===
מומלץ לקרוא ישירות את המאמר פורץ הדרך בו הוצגה השיטה:
[https://people.cs.umass.edu/~emery/classes/cmpsci691st/readings/Sec/Rsapaper.pdf Rivest, Ronald L., Adi Shamir, and Leonard Adleman. "A method for obtaining digital signatures and public-key cryptosystems."]
*אליס בוחרת שני ראשוניים גדולים <math>\{p,q\}</math> זה הסוד שלה.
*אליס מחשבת את המכפלה <math>n=p\cdot q</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>n-1\equiv -1 \mod n</math>
===דיפי-הלמן===
מומלץ לקרוא ישירות את המאמר פורץ הדרך בו הוצגה השיטה:
[http://ee.stanford.edu/%7Ehellman/publications/24.pdf Diffie, Whitfield, and Martin E. Hellman. "New directions in cryptography."]
*למדנו שבעזרת 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>.
**האיבר שבחרנו הוא יוצר.
*סיפרנו על אליס שייצרה מפתח פומבי <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> ומוודאת ומוודא כי המידע שהיא קיבלה שהוא קיבל הוא המידע שבוב התכוון שאליס התכוונה לשלוח עד כדי המקרה הבלתי סביר של התנגשות.*אף אחד אחר לא יכל ליצור את הוכחת אמינות המידע הזו פרט לבובלאליס.
**<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/ הספר]==
*יהי הומומורפיזם בין חבורות <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>aK=Ka</math> ולכן הגרעין הינו תת חבורה נורמלית.
==הרצאה 9 משפט האיזומורפיזם, מבוא לקידוד; פרק 11 מ[http://abstract.ups.edu/aata/ הספר]==
**אם <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_mb_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>a</math> ונקבל <math>f(a)=r</math>.
**לכן <math>f(x)=q(x)(x-a)</math> אם ורק אם <math>f(a)=0</math>.
===אידיאלים===
*יהי חוג <math>R</math>. תת קבוצה <math>I\subseteq R</math> נקראת '''אידיאל''' (דו-צדדי) אם:
**<math>I</math> מקיימת את כל התכונות של חוג, פרט אולי לקיום איבר יחידה כפלי.
**לכל <math>r\in R</math> ולכל <math>a\in I</math> מתקיים כי <math>ar,ra\in I</math> (כלומר האידיאל "בולע" איברים בכפל).
*דוגמא:
*<math>k\mathbb{Z}</math> הוא אידיאל של <math>\mathbb{Z}</math>.
*טענה: אם <math>I\subseteq\mathbb{F}[x]</math> הוא אידיאל אזי קיים פולינום <math>g(x)</math> עבורו <math>I=\langle g(x)\rangle=\{f(x)g(x)|f(x)\in\mathbb{F}[x]\}</math>.
*(קוראים לאידיאל כזה הנוצר ממכפלות באיבר אחד - אידיאל ראשי.)
*הוכחה:
**נביט בפולינום <math>g(x)\in I</math> בעל דרגה מינימלית מבין כל הפולינומים השונים מאפס ב<math>I</math>.
**יהי <math>f(x)\in I</math> נבצע חלוקה עם שארית ונקבל <math>f(x)=q(x)g(x)+r(x)</math>.
**כיוון שמדובר באידיאל גם <math>r(x)=f(x)-q(x)g(x)\in I</math>.
**כיוון ש<math>\deg(r(x))<\deg(g(x))</math> אבל הדרגה של <math>g(x)</math> היא מינימלית, נובע כי <math>r(x)=0</math>.
**לכן <math>f(x)=q(x)g(x)</math>.
**כמובן גם שלכל <math>q(x)</math> מתקיים כי <math>q(x)g(x)\in I</math> כיוון שמדובר באידיאל.
**יהי g פולינום מדרגה m, לפי נקודד קידוד פולינומי.
**נסמן את אורך המילה המקודדת ב<math>n=k+m</math>.
**מילה היא חוקית אם ורק אם היא מהצורה <math>h(x)g(x)</math> כאשר <math>deg(h(x))<k</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>I</math> את אוסף כל המילים החוקיות, כלומר כל הפולינומים מהצורה <math>f(x)g(x)</math> כאשר <math>\deg(f)<k</math>.**כעת, בכיוון ראשון, נניח כי הקוד הינו הוא ציקלי:***נחלק את <math>x^n{k-1</math> ב<math>}g(x)</math> עם שארית, ונוכיח כי השארית היא אפס.מילה חוקית***כיוון שהקוד ציקלי, גם ההזזה הציקלית <math>x\cdot x^n{k-1=h(x)}g(x)+r(x)^n+1</math>חוקית***שימו לב שכלומר <math>h(x)g(x)\not\in I</math> כיוון ש<math>\deg(h)=k</math>.***נסמן <math>h(x)=x^k+t(x)</math> ולכן <math>h(x)g(x)=+x^kg(x)n+t1=h(x)g(x)</math>.***כעת לכן <math>x^kgn+1=(h(x) = x\cdot +x^{k-1}) g(x)</math>, כפי שרצינו.***נחשב את השארית מודולו בכיוון שני, נניח כי <math>x^n-+1</math> ונקבל ההזזה ציקלית של המילה החוקית <math>x^{k-1}g(x)\in I</math>.***כיוון שהקוד ציקלי, גם המילה המוזזת הינה חוקית, ולכן <math>x^kg(x)\equiv q=t(x)g(x) \mod x^n-1</math>.***נחזור לחלוקה בשארית המקורית, נחשב את השאריות מודולו נשים לב כי <math>x^n-1</math> ונקבל:****<math>0=qdeg(x)g(x)+t(x)g(x)+r(x)=k</math>****תהי מילה חוקית <math>rh(x)=(q(x)+t(x))g(x)</math>***כיוון ש אם <math>\deg(r)<h\deg(cdot g)<n</math> נובע כי אז ההזזה הציקלית היא <math>rxh(x)g(x)=0</math>.**בכיוון השני, נניח והיא מילה חוקית כי <math>x^n-1=tdeg(xh(x)g(x)<k</math> ונוכיח כי מדובר בקוד ציקלי.***נוכיח אחרת, נניח כי לכל מילה חוקית <math>deg(h(x)\cdot g(x)\in I=n</math> גם השארית ולכן ההזזה הציקלית היא <math>xh(x)g(x) \mod +x^n-+1</math> היא מילה חוקית.***נבצע חלוקה עם שארית של כלומר ההזזה הציקלית היא <math>xh(x\cdot h)g(x)</math> ב<math>+t(x)</math>.***<math>xhg(x)=q(xh(x)+t(x)+r)\cdot g(x)</math>***כיוון ש<math>\deg(xh(x))=deg(t(x))=k</math>, מתקיים נובע כי <math>\deg(r)<k</math>, ולכן <math>rxh(x)g+t(x)\in I)<k</math>.***נכפול את שני הצדדים בלכן <math>g(x)</math> ונקבל <math>xh(x)g(x)=q(x)(x^n-1)+rt(x)g(x)</math>.***לכן אכן השארית של <math>xh(x)\cdot g(x)</math> מודולו <math>x^n-1</math> היא מילה חוקית, כפי שרצינו.
*פרוטוקול Ethernet משתמש בתיקון שגיאות ציקלי הנקרא CRC32, ובפרט בפולינום:
*<math>g(zx)=x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1</math>.
*הפולינום <math>g(x)</math> מחלק את <math>x^{2^{32}-1}-1</math>, כלומר הוא מתאים לקידוד של עד למעלה מ4 מיליארד ביטים של מידע.