שינויים
/* דיפי-הלמן */
*[[מדיה:21ASTestA.pdf|מבחן מועד א' תשפ"א]]
**[[מדיה:21ASTestASol.pdf|פתרון מבחן מועד א' תשפ"א]]
*[[מדיה:21ASTestB.pdf|מבחן מועד ב' תשפ"א]]
*[[מדיה:21ASTestC.pdf|מבחן מועד ג' תשפ"א]]
*[[מדיה:22ASTestA.pdf|מבחן מועד א' תשפ"ב]]
*[[מדיה:22ASTestB.pdf|מבחן מועד ב' תשפ"ב]]
***נניח <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>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>
*פרוטוקול 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 מיליארד ביטים של מידע.
