שינויים
/* דיפי-הלמן */
ההרצאות מבוססות באופן כללי על הספר [http://abstract.ups.edu/aata/ Abstarct Algebra - Theory and Applications by Thomas W. Judson]
==הרצאה 1 הקדמה; הסבר על קידוד והצפנה, מבוא למבנים אלגבריים ==
*לפני הרצאה זו, חזרו בבקשה על הנושא של יחסי שקילות. ניתן לצפות בסרטון הבא:
<videoflash>jKprPSfRysE</videoflash>
==הרצאה 5 חבורת אוילר, משפטי אוילר ופרמה; פרק 6 מ[http://abstract.ups.edu/aata/ הספר]==
===חלוקה עם שארית===
*זוג מספרים שלמים <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</math> מתקיים כי <math>gcd(n,k)=gcd(n-k,k)=a(n-k)+bk=an+(b-a)k</math>.
**שימו לב שהנחת האינדוקציה התקיימה עבור הזוג <math>n-k,k</math>.
מומלץ לקרוא ישירות את המאמר פורץ הדרך בו הוצגה השיטה:
*כעת בוב מעוניין לשלוח לאליס מידע שרק היא תוכל לפענח. *בוב בעצם הולך "לנעול" את המידע באמצעות המנעול <math>e,n</math> של אליס. כל אחד יכול לנעול אותו, ורק אליס יודעת לפתוח אותו.*המידע שבוב מעוניין לשלוח הוא מספר <math>x<n</math>, בוב שולח את המידע המוצפן <math>x^e\mod n</math>*אם בוב רוצה לשלוח יותר מידע, הוא יצטרך לפרק אותו לחתיכות. שימו לב שאם המנעול של אליס ישאר קבוע לחלוטין זה יהווה חולשה. *אליס מקבלת את המידע המוצפן ומפענחת אותו באופן הבא: <math>x=\left(x^e\right)^d \mod n</math>*הוכחה - נחלק לשני מקרים.*אם <math>gcd(x,n)=1</math>:**נתון כי <math>de=km+1=k\phi(n)+1</math>.**<math>\left(x^e\right)^d=x^{de}=x^{k\phi(n)+1}=\left(x^{\phi(n)}\right)^k\cdot x\equiv x \mod n</math>**זה נכון כיוון שלפי משפט אוילר <math>x^{\phi(n)}\equiv 1 \mod n</math>*אם <math>gcd(x,n)\neq 1</math>:**כיוון ש<math>n=p\cdot q</math> אז x הוא כפולה של p או q. נוכיח במקרה שx מתחלק בp.**קיים <math>h<q</math> עבורו <math>x=hp</math> וכמו כן x זר לq (אחרת בשני המקרים יוצא ש <math>x\geq n</math>).**לכן לפי פרמה הקטן יוצא ש <math>x^{q-1}\equiv 1 \mod q</math>**לכן <math>x^{km}=x^{k(p-1)(q-1)}=\left(x^{q-1}\right)^{k(p-1)}\equiv 1 \mod q</math>**לכן <math>x^{de}=x^{km+1}=x^{km}x=(1+tq)x=x+tqhp=x+th\cdot n\equiv x \mod n</math> *שימו לב: אמנם <math>4\equiv 1 \mod 3</math> אך <math>2^4 \not\equiv 2 \mod 3</math> כלומר לחשב את ההופכי של e מוד n זה אמנם קל, אך לא יעיל לשום דבר... ==הרצאה 7 המשך הצפנה - בדיקת ראשוניות, דיפי הלמן, חתימה, חישוב חזקות;== ===שיטת מילר-רבין לבדיקת ראשוניות===*חלק מהותי בשיטות שאנו לומדים הוא מציאת ראשוניים גדולים. כיצד הדבר נעשה? האם יש רשימה גדולה של כל הראשוניים בעולם?*ידוע שכמות הראשוניים עד המספר <math>n</math> היא בערך <math>\frac{n}{\ln(n)}</math>.*לכן הסיכוי בבחירת מספר אקראי עד <math>n</math> שהוא יהיה ראשוני הוא בערך <math>\frac{1}{\ln(n)}</math>.*אנו זקוקים למבחן ראשוניות - נגריל מספרים אקראיים ונבדוק האם הם ראשוניים, ומהר מאד נמצא אחד כזה בהתחשב בסיכוי הנ"ל.*זכרו שפירוק לגורמים ראשוניים היא בעייה קשה (אחרת RSA מיותר ממילא). *לפי משפט פרמה הקטן, אם <math>p</math> ראשוני, אזי לכל <math>a<p</math> מתקיים <math>a^{p-1}\equiv 1 \mod p</math>.*האם ההפך נכון? כלומר, האם <math>a^{p-1}\equiv 1 \mod p</math> רומז ש<math>p</math> ראשוני?*[https://he.wikipedia.org/wiki/%D7%9E%D7%A1%D7%A4%D7%A8_%D7%A7%D7%A8%D7%9E%D7%99%D7%99%D7%A7%D7%9C מספרי קרמייקל] מקיימים את התכונה הזו כמעט לכל <math>a</math> למרות שאינם ראשוניים. *טענה: אם <math>p</math> ראשוני, ו<math>x\in U_p</math> איבר כך ש <math>x^2=1</math> אזי <math>x=\pm 1</math>*הוכחה: **נזכור ש<math>\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> *אם <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> (נמוך מאד). ===דיפי-הלמן===מומלץ לקרוא ישירות את המאמר פורץ הדרך בו הוצגה השיטה: [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>. *כעת אליס ובוב שניהם יכולים לחשב בקלות את הסוד המשותף <math>g^{ab}</math>. *על מנת לשבור את ההצפנה צריך לחשב את <math>a</math> בהנתן <math>g^a \mod p</math>, זו בעיית הלוגריתם הדיסקרטי שנחשבת לקשה.*אם <math>g</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>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>41=2^5+2^3+1</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 העלאות בריבוע, ושלוש הכפלות, במקום 40 הכפלות. ==הרצאה 8 תת חבורות נורמליות, חבורות מנה, גרעין; פרקים 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>H=<(1\ 2)>=\{(1),(1\ 2)\}</math>.**אזי <math>(1\ 3)H=\{(1\ 3), (3\ 1\ 2)\}</math> אך <math>H(1\ 3)=\{(1\ 3),(2\ 1\ 3)\} </math> וקל לראות כי <math>(1\ 3)H\neq H(1\ 3)</math>.**אזי N תת חבורה לא נורמלית!*דוגמא נוספת:**נביט בחבורה הסימטרית <math>G=S_3</math> ובתת החבורה <math>N=<(1\ 2\ 3)></math> שהיא תת החבורה של כל התמורות הזוגיות במקרה זה.**קל לוודא שלכל תמורה זוגית מתקיים <math>fN=Nf=N</math> ולכל תמורה אי-זוגית מתקיים <math>fN=Nf</math> שווה לקבוצת כל התמורות האי-זוגיות. *טענה תהי N תת חבורה נורמלית אזי <math>(aN)(bN)=abN</math>*הוכחה - הכלה דו כיוונית:**יהי <math>anbk\in (aN)(bN)</math> כיוון ש <math>bN=Nb</math> אזי <math>anbk=abmk\in abN</math>.**יהי <math>abn\in abN</math> אזי <math>aebn\in (aN)(bN)</math>. *תהיינה G חבורה וN תת חבורה נורמלית, אזי <math>G/N=\{aN|a\in G\}</math> היא חבורה. *יהי הומומורפיזם בין חבורות <math>f:G\to H</math>. נגדיר את '''הגרעין''' <math>\ker(f)=\{a\in G|f(a)=e_H\}</math>.*נסמן <math>K=\ker(f)</math>*טענה:**לכל <math>a\in G</math> מתקיים כי <math>aK=\left\{b\in G|f(a)=f(b)\right\}</math>*הוכחה:**בכיוון ראשון, יהי <math>ak\in aK</math> אזי <math>f(ak)=f(a)f(k)=f(a)e_H=f(a)</math>**בכיוון שני, יהי <math>b\in G</math> כך ש <math>f(a)=f(b)</math> אזי <math>f(a^{-1}b)=e_H</math> ולכן <math>a^{-1}b=k\in K</math> ולכן <math>b=ak\in aK</math> *כיוון שהוכחה דומה עובדת מהצד השני, נובע כי <math>aK=Ka</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> עם פעולות חיבור וכפל, כך שהוא חבורה חילופית ביחד לחיבור, מקיים אסוציאטיביות בכפל, מכיל איבר יחידה ואת חוק הפילוג.
===חוג הפולינומים===
*יהי <math>\mathbb{F}</math> שדה, אזי <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>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/ הספר]===