שינויים

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

*עבור <math>f\in S_n</math> נגדיר את הסימן <math>\mathrm{sign}(f):=\Pi_{i\neq j}\frac{x_{f(i)}-x_{f(j)}}{ix_i-jx_j}</math>.

**<math>\mathrm{sign}(f)\cdot\mathrm{sign}(circ g)=\Pi_{i\neq j}\frac{x_{f(g(i))}-x_{f(g(j))}}{ix_i-jx_j}\cdot =\Pi_{i\neq j}\frac{x_{f(g(i))}-x_{f(g(j))}}{i-j}</math>**נשנה את סדר המונים במכפלה השנייה ונקבל <math>\Pi_{i\neq j}\frac{x_{fg(i)}-x_{fg(j)}}{i-j}\cdot\frac{i-j}{x_{g^{-1}(i)}-x_{g^{-1}(j)}}{x_i-x_j}</math>**זה כיוון שg חח"ע ועל,אוסף הזוגות <math>i\neq j</math> שווה ל לאוסף הזוגות <math>g(i),g(j)</math>, ולכן <math>\Pi_{i\neq j}\frac{x_{f(g(g^{-1}(i)))}-x_{f(g(g^{-1}(j)))}}{x_{g^{-1}(i)}-x_{g^{-1}(j)}}=\mathrm{sign}(f)</math>.**סה"כ קיבלנו <math>\mathrm{sign}(f\circ g)=\mathrm{sign}(f)\cdot\mathrm{sign}(g)</math>.  <videoflash>Lmk0izbQR08</videoflash>

*דוגמאתכונות:

*הומומורפיזמים, איזומורפיזמיםהגדרה: גרעין של הומומורפיזם הוא אוסף האיברים שנשלחים לאיבר היחידה.*תמונה טענה: התמונה והגרעין של הומומורפיזם היא הינם תתי חבורות של הטוווח והתחום בהתאמה.**הוכחה לגבי התמונה:**יהי הומומורפיזם <math>f:G\to H</math>.**ראשית, <math>f(e_G)=e_H</math> ולכן <math>e_H\in Im(f)</math>.**שנית, יהיו <math>h_1,h_2\in Im(f)</math> לכן קיימים <math>g_1,g_2\in G</math> כך ש <math>f(g_i)=h_i</math>.**<math>h_1\cdot h_2^{-1}=f(g_1)\cdot \left(f(g_2)\right)^{-1}=f(g_1\cdot g_2^{-1})\in Im(f)</math>.**סה"כ הוכחנו כי <math>Im(f)</math> הינה תת חבורהשל <math>H</math>.

*משפט שיכון קיילי- כל :**תהי חבורה איזומורפית לתת חבורה של <math>G</math> ונגדיר את S להיות חבורת הפונקציות ההפיכות מ<math>G</math> לעצמה עם פעולת ההרכבה (חבורת תמורות).**לכל איבר <math>a\in G</math> נגדיר את התמורה המתאימה לו <math>f_a\in S</math> המוגדרת ע"י <math>f_a(x)=a\cdot x</math>.***הוכחה ש<math>f_a\in S</math>:***חח"ע: אם <math>f_a(x_1)=f_a(x_2)</math> אזי <math>a\cdot x_1=a\cdot x_2</math> ולפי תכונת הצמצום <math>x_1=x_2</math>.***על: עבור <math>y\in G</math> מתקיים כי <math>f_a(a^{-1}\cdot y)=a\cdot(a^{-1}\cdot y) =(a\cdot a^{-1})\cdot y=y </math>**הפונקציה <math>\varphi:G\to S</math> השולחת כל איבר לתמורה המתאימה לו <math>\varphi(a)=f_a</math> נקראת '''שיכון קיילי'''.

*תת תהי חבורה מחלקת 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>a^{-1}a=e\in H</math>***סימטריות: אם <math>a^{-1}b\in H</math> אזי גם ההופכי שלו <math>(קוסטיםa^{-1}b) שוות בגודלן לגודל תת החבורה^{-1}=b^{-1}a\in H</math>***טרנזיטיביות: נניח <math>a^{-1}b,b^{-1}c\in H</math> אזי לפי סגירות גם <math>a^{-1}bb^{-1}c=a^{-1}c\in H</math>**אכן <math>[a]_R=\{b|aRb\}=\{b|a^{-1}b=h\in H\}=\{b|b=ah,h\in H\}=a\cdot H</math>*טענה: לכל איבר <math>a\in G</math> מתקיים כי <math>|a\cdot H|=|H|</math>.*אינדקס תת החבורה הוא מספר מחלקות השקילות *הוכחה: **נביט בפונקציה <math>f:H\to a\cdot H</math> המוגדרת ע"י <math>f(h)=a\cdot h</math> ונוכיח שהיא מייצרת בחבורהחח"ע ועל.**חח"ע: אם <math>f(h_1)=f(h_2)</math> אזי <math>a\cdot h_1=a\cdot h_2</math> ולפי תכונת הצמצום <math>h_1=h_2</math>.**על: יהי <math>a\cdot h\in a\cdot H</math>, וזה בדיוק גודל החבורה חלקי גודל תת החבורה ברור ש<math>f(h)=a\cdot h</math>.  *הגדרה: האינדקס <math>[G:H]</math> מוגדר להיות מספר המחלקות השונות ש<math>H</math> מגדירה.*כיוון שראינו שהמחלקות הן בעצם מחלקות שקילות שוות בגודלן המחלקות את G, נובע '''משפט לגראנג')''':עבור חבורות סופיות, <math>|G|=|H|\cdot [G:H]</math>.*בחבורה סופית, לכל איבר יש נובע כי הגודל (סדר סופי ותת ) של כל תת חבורה צקלית בגודל , מחלק את הגודל (סדר האיבר) של החבורה כולה. לכן סדר כל *יהי <math>a\in G</math> איבר מסדר <math>n</math>. ראינו כי <math>|<a>|=n</math>, ולכן ביחד סדר האיבר מחלק את גודל החבורה.*תהי חבורה מגודל סופית עם מספר ראשוני חייבת להיות של איברים, אזי היא חבורה ציקלית. **אכן, וכל ניקח איבר פרט לאיבר היחידה יוצר אותהשונה מהנייטרלי, הסדר שלו חייב להיות המספר הראשוני (כי לראשוני אין מחלקים), ולכן החבורה הציקלית שלו שווה לכל החבורה. 

*יהיו שני טבעיים שלמים <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>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>\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>\varphi:G\to H</math> איזומורפיזם הומומורפיזם בין חבורות. אזי <math>G/\ker(\varphi)\cong im(\varphi) </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>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}_2n=k+m</math>, יחד עם פעולת החיבור הרגילה, ופעולת הכפל מודולו הפולינום .**מילה היא חוקית אם ורק אם היא מהצורה <math>h(x)g(x^n-1)</math>.*נשים לב כי מתקיים כאשר <math>x\cdotdeg(h(a_{n-1}x^{n-1}+...+a_1x+a_0)=a_{n-2}x^{n-1}+...+a_1x^2+a_0x+a_{n-1})<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>gf(x)=a_{n-1}x^{n-1}+...+a_0</math> בעל דרגה **אזי <math>x\deg(gcdot f(x))=\equiv a_{n-2}x^{n-1}+...+a_0x+a_{n-1} \mod x^n-k>1</math>.*נקודד את כל פולינומי המידע מדרגה שקטנה או שווה *כלומר ההזזה הציקלית של <math>kf(x)</math> היא השארית של <math>x\cdot f(x)</math> בחלוקה ב<math>x^n-1</math> בקידוד פולינומי.*שימו לב*הוכחה: כיוון ש***אכן <math>x\deg (cdot f(x)\cdot = a_{n-1}x^n+...+a_0x=a_{n-k1}(x^n-1)\leq + a_{n-1} + a_{n-2}x^{n-1}+...+a_0x</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</math>.***באופן דומה, לכל <math>k</math> מתקיים כי <math>x^k\cdot f(x)\in I</math>.***כיוון שהקוד לינארי, גם סכום של מילים חוקיות הוא מילה חוקית.***ביחד, <math>=a_{n-1}x^{n-1}f(x)+...+a_1xf(x)+a_0f(x)a_0</math> הינה מילה חוקית.***לכן לכל פולינום אם <math>h(x)\in Ra_n=0</math> מתקיים אזי ההזזה הציקלית היא <math>h(x)\cdot f(x)\in I</math>, כלומר אוסף המילים החוקיות הינו אידיאל.**כעת נבצע חילוק בשארית (בחוג הפולינומים הרגיל) אם <math>x^n-a_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(rcdot f(x))<\deg(g(x))</math> ולכן <math>r(x)=0</math>.  *בכיוון השני, נניח כי <math>+x^n-+1=t(x)g(x)</math> ונוכיח כי מדובר בקוד ציקלי.**נוכיח כי לכל מילה חוקית <math>h(x)g(x)\in I</math> גם <math>xh(x)g(x)\in I</math> כאשר הכפל האחרון נעשה ב<math>R</math>.**נבצע חלוקה עם שארית <math>xh(x)=q(x)t(x)+r(x)</math> בחוג הפולינומים הרגיל.**נכפול מכבים את שני הצדדים ב<math>g(x)</math> ונקבל <math>xh(x)g(x)=q(x)(x^n-1)+r(x)g(x)</math>.**לכן ב<math>R</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> הביטים כך שיהיה שיהיו בקצה הימני במקום של היתירות.

*<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>.