שינויים

[[89-214 תשעח סמסטר א|חזרה לדף הקורסקטגוריה:מערכי לימוד]]

*תהי חבורה G ותת חבורה H. יהי <math>a\in G</math>, נגדיר את '''המחלקה''' <math>a\cdot H:=\{a+\cdot h:h\in H\}</math>.

*יהיו שני טבעיים שלמים <math>a,b</math> ויהיו <math>r_a,r_b</math> השאריות שלהם בחלוקה בn. אזי <math>ab\equiv r_ar_b \mod n</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>. 

**למעשה התוצאה תקיפה לכל מספר טבעי <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.

*הצפנה; העברת מידע בערוץ פומבי כך שרק המשתתפים בהצפנה יוכלו להבין אותו, הוכחה לזהות כותב המידע (בין היתר כותב המידע לא יוכל להתנער ממנו), הוכחה לאמינות ושלימות המידע (המידע אינו חלקי ואף אחד לא שינה אותו).*[https://he.wikipedia.org/wiki/%D7%A6%D7%95%D7%A4%D7%9F_%D7%A1%D7%99%D7%9E%D7%98%D7%A8%D7%99 הצפנה סימטרית] - הצפנה בה לשני הצדדים יש סוד משותף שהעבירו מראש בערוץ שאינו פומבי (משאית ברינקס למשל, לנסוע לחנות לאסוף כרטיס sim).

**נזכור ש<math>U_p\mathbb{Z}_p</math> הוא '''שדה''' כיוון שמדובר במספר ראשוני, ולכן אין בו ב<math>U_p=\mathbb{Z}/\{0\}</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>g</math> של <math>U_p</math> (כלומר <math>U_p=<g></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>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>\varphi:G\to H</math> איזומורפיזם הומומורפיזם בין חבורות. אזי <math>G/\ker(\varphi)\cong im(\varphi) </math>

*נקבע פולינום <math>g(x)\in\mathbb{Z}_2[x]</math> כלשהו מדרגה nm.*עבור מידע <math>f(x)</math> נבצע חלוקה עם שארית של <math>x^m\cdot f(x)</math> ב<math>g(x)</math>*<math>x^m\cdot f(x^n ) =q(x)g(x)+r(x)</math>.*המילה שנשלח היא <math>f(x)^m\cdot f(x^n ) + r(x)</math> (שימו לב כי <math>r(x)=-r(x)</math>).

*קוד זה מוסיף n m ביטים של יתירות למידע.

***לכן עלינו לחלק את הפולינום <math>f(x)^3\cdot f(x^3) =x^6+x^4</math> בפולינום <math>g(x)=x^3+x+1</math>.

***לכן סה"כ המידע שנשלח הוא <math>f(x)^3\cdot f(x^3 ) + r(x)=x^6+x^4+x+1</math> שזה בעצם <math>1010011</math>.

===קידוד פולינומי ציקלי===*עבור הקידוד הציקלי נקבע את הפרמטרים הבאים:*נביט ב<math>R</math> חוג הפולינומים *יהי k אורך המידע, כלומר נקודד פולינומים עד דרגה <math>nk-1</math>בלבד.**יהי g פולינום מדרגה m, עם מקדמים מ<math>\mathbb{Z}_2</math>, יחד עם פעולת החיבור הרגילה, ופעולת הכפל מודולו הפולינום <math>x^n-1</math>לפי נקודד קידוד פולינומי.*נשים לב כי מתקיים *נסמן את אורך המילה המקודדת ב<math>x\cdot(a_{n-1}x^{n-1}+...+a_1x+a_0)=a_{n-2}x^{n-1}k+...+a_1x^2+a_0x+a_{n-1}m</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>g(x)</math> בעל דרגה <math>\deg(g(x))=n-k>1</math>.*נקודד נתאר את כל פולינומי המידע מדרגה שקטנה או שווה <math>k-1</math> בקידוד פולינומיההזה הציקלית באמצעות פעולה אלגברית.*שימו לב: כיוון ש*יהי <math>\deg (f(x)\cdot x^=a_{n-k1})\leq n-1</math> החלוקה בשארית כוללת אך ורק פולינומים מ<math>R</math>.  *טענה: הפולינום <math>g(x)</math> מחלק את <math>x^{n-1</math> אם ורק אם הקוד לעיל הינו ציקלי}+.*הוכחה:*בכיוון ראשון, נניח כי הקוד הינו ציקלי:**ראשית, נוכיח כי קבוצת המילים החוקיות <math>I</math> היא אידיאל של <math>R</math>.***תהי <math>f(x)\in I</math> מילה חוקית. כיוון שהקוד ציקלי גם <math>x\cdot f(x)\in I+a_0</math>.***באופן דומה, לכל <math>k</math> מתקיים כי אזי <math>x^k\cdot f(x)\in I</math>.***כיוון שהקוד לינארי, גם סכום של מילים חוקיות הוא מילה חוקית.***ביחד, <math>equiv a_{n-12}x^{n-1}f(x)+...+a_1xf(x)a_0x+a_0f(a_{n-1} \mod x)^n-1</math> הינה מילה חוקית.***לכן לכל פולינום כלומר ההזזה הציקלית של <math>hf(x)\in R</math> מתקיים היא השארית של <math>h(x)\cdot f(x)\in I</math>, כלומר אוסף המילים החוקיות הינו אידיאל.**כעת נבצע חילוק בשארית (בחוג הפולינומים הרגיל) בחלוקה ב<math>x^n-1=q(x)g(x)+r(x)</math>.**לכן ב<math>R</math> מתקיים כי <math>q(x)g(x)=r(x)</math> ולכן <math>r(x)\in I</math> (כיוון שמדובר באידיאל).הוכחה:**כלומר קיבלנו מילה חוקית *אכן <math>\deg(r(x))<\deg(g(x))</math> ולכן <math>rcdot f(x)=0</math>.  *בכיוון השני, נניח כי <math>x^a_{n-1=t(}x)g(x)</math> ונוכיח כי מדובר בקוד ציקלי^n+..**נוכיח כי לכל מילה חוקית <math>h(x)g(x)\in I</math> גם <math>xh(x)g(x)\in I</math> כאשר הכפל האחרון נעשה ב<math>R</math>.**נבצע חלוקה עם שארית <math>xh(x)+a_0x=q(x)ta_{n-1}(x^n-1)+r(x)</math> בחוג הפולינומים הרגיל.**נכפול את שני הצדדים ב<math>g(x)</math> ונקבל <math>xh(x)g(x)=q(x)(a_{n-1} + a_{n-2}x^{n-1)}+r(x)g(x)</math>.**לכן ב<math>R..+a_0x</math> מתקיים כי <math>xh(x)g(x)=r(x)g(x)</math>, ואכן <math>r(x)g(x)\in I</math>, כיוון ש<math>\deg(r(x)g(x))<n</math>. 

*טענהמשפט: קוד פולינומי ציקלי עם פולינום <math>g(x)</math> מדרגה <math>m</math> מסוגל לזהות כל כמות של שגיאות, בתנאי שכולן נמצאות בתוך טווח של <math>m</math> ביטים.

**נזיז את <math>m</math> הביטים כך שיהיה שיהיו בקצה הימני במקום של היתירות.