שינויים
/* דיפי-הלמן */
=ספר הקורס=
ההרצאות מבוססות באופן כללי על הספר [http://abstract.ups.edu/aata/ Abstarct Algebra - Theory and Applications by Thomas W. Judson]
* [[מדיה:19CSASnotes.pdf|סיכום ההרצאות מ2019 ע"י ספיר ביתן]]
* [[מדיה:21CSASnotes.pdf|סיכום ההרצאות מ2021 ע"י רועי אוסקר]]
=מבחנים לדוגמא=
*[[מדיה:19ASTestB.pdf|מבחן מועד ב' תשע"ט]]
**[[מדיה:18ASTestBSol.pdf|פתרון מועד ב' תשע"ט]]
*[[מדיה:20ASTestA.pdf|מבחן מועד א' תש"ף]]
*[[מדיה:20ASTestB.pdf|מבחן מועד ב' תש"ף]]
*[[מדיה:21ASTestA.pdf|מבחן מועד א' תשפ"א]]
**[[מדיה:21ASTestASol.pdf|פתרון מבחן מועד א' תשפ"א]]
*[[מדיה:21ASTestB.pdf|מבחן מועד ב' תשפ"א]]
*[[מדיה:21ASTestC.pdf|מבחן מועד ג' תשפ"א]]
*[[מדיה:22ASTestA.pdf|מבחן מועד א' תשפ"ב]]
*[[מדיה:22ASTestB.pdf|מבחן מועד ב' תשפ"ב]]
* [[89-214 מבחנים|מבחנים משנים קודמות]]
=נושאי ההרצאות=
**<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>
===תת חבורות===
***נניח <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>
===דיפי-הלמן===
מומלץ לקרוא ישירות את המאמר פורץ הדרך בו הוצגה השיטה:
[http://ee.stanford.edu/%7Ehellman/publications/24.pdf Diffie, Whitfield, and Martin E. Hellman. "New directions in cryptography."]
*למדנו שבעזרת RSA ניתן להעביר פיסת מידע באופן בטוח בערוץ פומבי, ולרוב נרצה להעביר מפתח סודי לצורך הצפנה סימטרית.
*אלגוריתם דיפי-הלמן הוא שיטה לתיאום מפתח סודי בלבד ולא להעברת מידע.
**אם <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>.
**יהי 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 מיליארד ביטים של מידע.
