שינויים

=[[קטגוריה:מערכי לימוד]] =ספר הקורס==

 * [[מדיה:19CSASnotes.pdf|סיכום ההרצאות מ2019 ע"י ספיר ביתן]]* [[מדיה:21CSASnotes.pdf|סיכום ההרצאות מ2021 ע"י רועי אוסקר]] =מבחנים לדוגמא= *[[מדיה:17ASExmTest1.pdf|מבחן לדוגמא 1 תשע"ח]]**[[מדיה:17ASExmTest1Sol.pdf|פתרון מבחן לדוגמא 1 תשע"ח]]*[[מדיה:17ASExmTest2.pdf|מבחן לדוגמא 2 תשע"ח]]**[[מדיה:17ASExmTest2Sol.pdf|פתרון מבחן לדוגמא 2 תשע"ח]]*[[מדיה:17ASExmTest3.pdf|מבחן לדוגמא 3 תשע"ח]]**[[מדיה:17ASExmTest3Sol.pdf|פתרון מבחן לדוגמא 3 תשע"ח]]*[[מדיה:17ASTestA.pdf|מבחן מועד א' תשע"ח]]*[[מדיה:17ASTestB.pdf|מבחן מועד ב' תשע"ח]]*[[מדיה:17ASTestC.pdf|מבחן מועד ג' תשע"ח]]*[[מדיה:18ASTestA.pdf|מבחן מועד א' תשע"ט]]**[[מדיה:18ASTestASol.pdf|פתרון מועד א' תשע"ט]]*[[מדיה:19ASTestB.pdf|מבחן מועד ב' תשע"ט]]**[[מדיה:18ASTestBSol.pdf|פתרון מועד ב' תשע"ט]]*[[מדיה:20ASTestA.pdf|מבחן מועד א' תש"ף]]*[[מדיה:20ASTestB.pdf|מבחן מועד ב' תש"ף]]*[[מדיה:21ASTestA.pdf|מבחן מועד א' תשפ"א]]**[[מדיה:21ASTestASol.pdf|פתרון מבחן מועד א' תשפ"א]]*[[מדיה:21ASTestB.pdf|מבחן מועד ב' תשפ"א]]*[[מדיה:21ASTestC.pdf|מבחן מועד ג' תשפ"א]]*[[מדיה:22ASTestA.pdf|מבחן מועד א' תשפ"ב]]*[[מדיה:22ASTestB.pdf|מבחן מועד ב' תשפ"ב]]   * [[89-214 מבחנים|מבחנים משנים קודמות]] =נושאי ההרצאות= [https://www.youtube.com/playlist?list=PLzSjdxrZD_hka_9hBlLKybpwG_5_T7FaY פלייליסט של הרצאות קבוצה 01 תשפ"א]  [https://www.youtube.com/playlist?list=PLzSjdxrZD_hlVTrX-RcrpYiTMyQBmIihV פלייליסט של הרצאות קבוצה 02 תשפ"א]  ==הרצאה 1 הקדמה; הסבר על קידוד והצפנה, מבוא למבנים אלגבריים ===

===הרצאה 2 חבורות ותת חבורות; פרקים 3,4 מ[http://abstract.ups.edu/aata/ הספר] =====חבורות===*חבורה היא קבוצה G עם פעולה המקיימת:**סגירות**אסוציאטיביות**איבר נייטרלי**לכל איבר יש איבר הופכי

 *תזכורת לגבי חבורותחבורה המקיימת את חוק החילוף נקראת חבורה אבלית, קומוטטיבית או חילופית  *תכונת הצמצום: תהי חבורה G, אזי לכל <math>a,b,c\in G</math> אם <math>ab=ac</math> אזי <math>b=c</math>.**הוכחה: נכפול באיבר ההופכי <math>a^{-1}(ab)=a^{-1}(ac)</math> ונשתמש באסוציאטיביות ובאיבר הנייטרלי. *יחידות האיבר ההופכי: נובע מתכונת הצמצום שלכל איבר בחבורה קיים איבר הופכי יחיד.**הוכחה: אם <math>ab=ac=e_G</math> אזי <math>b=c</math>.  *דוגמאות לחבורות:**<math>S_n</math> חבורת הפונקציות ההפיכות מקבוצה בגודל n לעצמה עם פעולת ההרכבה.**<math>GL_n(\mathbb{ZF},)</math> חבורת המטריצות ההפיכות עם כפל מטריצות.**<math>\mathbb{Z}_n,</math> חבורת השלמים עם חיבור.**<math>\mathbb{GLZ}_n</math> חבורת השאריות עם חיבור מודולו n. ===מכפלה קרטזית של חבורות=== *תהיינה חבורות <math>G,H</math> המכפלה הקרטזית של החבורות <math>G\times H</math> (אוסף הזוגות הסדורים) היא חבורה עם הפעולה הבאה: <math>(g_1,h_1)\cdot_{SLG\times H}_n(g_2,S_nh_2)=(g_1\cdot_G g_2,h_1\cdot_H h_2)</math>.*===תת חבורות; קווטרניונים, מעגל היחידה ושורשי יחידה, המרוכבים ללא אפס כתת ===*הגדרה: תהי חבורה G. תת קבוצה <math>H\subseteq G</math> נקראת תת חבורה של מטריצות ממשיות בגודל 2 על 2G אם היא חבורה ביחס לפעולה של G.

===הרצאה 3 חבורת תמורות*תהי G חבורה, לכל <math>a\in G, סימן התמורה; פרק 5 מ[httpn\in \mathbb{N}</math> נגדיר:**<math>a^0=e_G<//abstractmath>.ups.edu**<math>a^{-n}=(a^{-1})^n</aata/ הספר] ===math>

*הומומורפיזמיםתהי חבורה G, איזומורפיזמיםלכל <math>a\in G</math> נגדיר את הסדר של האיבר <math>o(a)</math> בתור החזקה החיובית הקטנה ביותר k עבורה <math>a^k=e_G</math>. אם אין חזקה כזו, ניתן לומר שהסדר הוא אינסוף.*תמונה של הומומורפיזם היא תת חבורהדוגמאות:**<math>o(e_G)=1</math>.*משפט קיילי- כל חבורה איזומורפית לתת חבורה *ב<math>\mathbb{Z}_5</math> מתקיים כי <math>o(2)=5</math>.**ב<math>\mathbb{Z}</math> הסדר של חבורת תמורותכל איבר שונה מאפס הוא אינסוף.

*תהי חבורה G, ויהי <math>a\in G</math>. תת החבורה הציקלית הנוצרת על ידי a הינה <math><a>=\{a^n|n\in\mathbb{Z}\}</math>*הוכחה שאכן מדובר בתת חבורה מחלקת :**<math>e_G=a^0\in<a></math>.**יהיו <math>a^n,a^k\in<a></math> אזי <math>a^n\cdot (a^k)^{-1}=a^n\cdot (a^{-1})^k=a^{n-k}\in<a></math>.  *תהי חבורה למחלקות שקילות G, אזי סדר כל איבר הוא גודל החבורה הציקלית שהוא יוצר, כלומר <math>|<a>|=o(קוסטיםa) שוות בגודלן לגודל תת </math>.*הוכחה:**ראשית נוכיח עבור המקרה בו סדר האיבר סופי <math>o(a)=n</math>.***רוצים להוכיח כי <math><a>=\{e_G,a,a^2,...,a^{n-1}\}</math> וכי כל האיברים בקבוצה זו שונים זה מזה (אחרת כמות האיברים קטנה יותר מn).***ברור שהחזקות של a שייכות לתת החבורההציקלית.*אינדקס **יהי k כלשהו, נסמן בr את השארית <math>r=k \mod n</math> כלומר <math>k=pn+r</math> עבור <math>p\in\mathbb{Z}, 0\leq r\leq n-1</math>.***<math>a^k=(a^n)^pa^r=e_G^pa^r=a^r</math>.***כעת נניח כי קיימות שתי חזקות שונות <math>0\leq r_1<r_2\leq n-1</math> כך ש <math>a^{r_1}=a^{r_2}</math>.***לכן <math>a^{r_2-r_1}=e_G</math>.***אבל <math>r_2-r_1\leq n-1 < n</math> בסתירה לכך ש<math>o(a)=n</math>.**כעת נניח כי סדר האיבר הוא אינסוף, ונוכיח כי גודל תת החבורה הציקלית שהוא יוצר הוא מספר מחלקות השקילות שהיא מייצרת בחבורהאינסוף.***נניח בשלילה ש <math><a></math> סופית, וזה בדיוק גודל החבורה חלקי לכן לפחות שתי חזקות שונות של a נותנות אותו איבר.***נסמן <math>n<k</math> כך ש <math>a^n=a^k</math>.***לכן <math>a^{k-n}=e_G</math> בסתירה לכך שסדר האיבר הוא אינסוף.  *מסקנה: תהי חבורה '''סופית''' G, אזי לכל איבר בחבורה יש סדר סופי.**הוכחה: גודל תת החבורה הציקלית חייב להיות סופי.  *תת חבורות ציקליות:**<math>2\mathbb{Z}</math>.**<math>\{z\in\mathbb{C}:z^n=1\}\subseteq \mathbb{C}\setminus \{0\}</math> שורשי היחידה מסדר n. ==הרצאה 3 חבורת תמורות, סימן התמורה; פרק 5 מ[http://abstract.ups.edu/aata/ הספר] == ===סימן של תמורה===*נביט בחבורת התמורות <math>S_n</math>.*עבור <math>f\in S_n</math> נגדיר את הסימן <math>\mathrm{sign}(f):=\Pi_{i\neq j}\frac{x_{f(i)}-x_{f(j)}}{x_i-x_j}</math>.*הסימן של תמורה הוא תמיד פלוס או מינוס 1.*אם סימן התמורה הוא מינוס אחד אומרים שהיא '''אי-זוגית''' או '''שלילית''', ואם הסימן הוא אחד אומרים שהיא '''זוגית''' או '''חיובית'''.  *כפליות הסימן: תהיינה שתי תמורות <math>f,g\in S_n</math>, אזי <math>\mathrm{sign}(f\circ g)=\mathrm{sign}(f)\cdot\mathrm{sign}(g)</math>.**הוכחה:**<math>\mathrm{sign}(f\circ g)=\Pi_{i\neq j}\frac{x_{f(g(i))}-x_{f(g(j))}}{x_i-x_j}=\Pi_{i\neq j}\frac{x_{f(g(i))}-x_{f(g(j))}}{x_{g(i)}-x_{g(j)}}\cdot\frac{x_{g(i)}-x_{g(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(i))}-x_{f(g(j))}}{x_{g(i)}-x_{g(j)}}=\mathrm{sign}(f)</math>.**סה"כ קיבלנו <math>\mathrm{sign}(f\circ g)=\mathrm{sign}(f)\cdot\mathrm{sign}(g)</math>.  <videoflash>Lmk0izbQR08</videoflash>  ===מחזורים===*מחזור <math>(a_1\ a_2\ \cdots \ a_k)</math> מייצג את התמורה f המקיימת <math>f(a_1)=a_2,...,f(a_{k-1})=a_k,f(a_k)=a_1</math> ולכל איבר אחר <math>f(a)=a</math>.*לדוגמא: <math>\begin{pmatrix}1&2&3&4&5\\4&2&5&3&1\end{pmatrix}=(1\ 4\ 3\ 5)\in S_5</math>  *כל תמורה ניתן להציג כהרכבה של מחזורים זרים, ואת תמורה הזהות ניתן להציג כ<math>(1)</math>.  *חילוף הוא מחזור באורך 2.*חילוף הוא תמורה אי זוגית.**נוכיח עבור <math>f=(1\ 2)\in S_n</math>. (זה מספיק כיוון שהשם של האיברים לא משנה.)**<math>\mathrm{sign}(f)=\left(\frac{x_2-x_1}{x_1-x_2}\cdot\frac{x_2-x_3}{x_1-x_3}\cdots \frac{x_2-x_n}{x_1-x_n}\right)\cdot\left(\frac{x_1-x_3}{x_2-x_3}\cdots\frac{x_1-x_n}{x_2-x_n}\right)\left(\cdot\frac{x_3-x_4}{x_3-x_4}\cdots\frac{x_{n-1}-x_n}{x_{n-1}-x_n}\right)=-1</math>   *כל מחזור ניתן להציג כהרכבה של חילופים:**<math>(a_1\ a_2\ \cdots \ a_k)=(a_1\ a_2)(a_2\ a_3)\cdot (a_{k-1}\ a_k)</math>**כל איבר שלא מוזכר במחזור נשלח לעצמו, ונציב בשני הצדדים את <math>a_1,...,a_{k-1}</math> ונראה כי הפונקציות שוות.**כיוון שמדובר בפונקציה הפיכה, אין צורך לבדוק את האיבר האחרון <math>a_k</math>.   *מסקנה: כיוון שסימן כל חילוף הוא שלילי ולפי כפליות הסימן, הסימן של מחזור באורך k הוא <math>(-1)^{k-1}</math>.*דוגמא:**<math>f=\begin{pmatrix}1&2&3&4&5&6&7\\4&2&5&3&1&7&6\end{pmatrix}=(1\ 4\ 3\ 5)(6\ 7)</math>.**לכן <math>\mathrm{sign}(f)=(-1)\cdot(-1)=1</math>, כלומר מדובר בתמורה זוגית.  <videoflash>oXntZnnoHfM</videoflash> ==הרצאה 4 הומומורפיזמים, איזומורפיזמים, משפט קיילי, משפט לגראנג'; פרקים 9 ו6 מ[http://abstract.ups.edu/aata/ הספר] == ===הומומורפיזם, איזומורפיזם===*הגדרה: תהיינה שתי חבורות G,H ותהי פונקציה <math>f:G\to H</math>. אזי f נקראת '''הומומורפיזם''' אם לכל <math>a,b\in G</math> מתקיים <math>f(a\cdot_G b)=f(a)\cdot_H f(b)</math>.*בחבורה סופיתשימו לב ש <math>\cdot_G</math> היא הפעולה של G, ו<math>\cdot_H</math> היא הפעולה של H.*הומומורפיזם שהוא פונקציה חח"ע ועל נקרא איזומורפיזם.*הומומורפיזם שומר במובן מסויים על המבנה של החבורה, ואיזומורפיזם מראה שהחבורות הן 'אותה גברת בשינוי אדרת'.  *תכונות:**אם <math>f:G\to H</math> הומומורפיזם אזי <math>f(e_G)=e_H</math>.***הוכחה:***<math>f(e_G)=f(e_G\cdot e_G)=f(e_G)\cdot f(e_G)</math>.***לפי תכונת הצמצום <math>f(e_G)=e_H</math>.**אם f הומומופיזם אזי <math>o(f(a))\leq o(a)</math>.***אם <math>o(a)=n</math> אזי <math>a^n=e_G</math>.***לכן <math>f(a^n)=\left(f(a)\right)^n=e_H</math>.***לכן <math>o(f(a))\leq n=o(a)</math>.**אם f איזומורפיזם אזי <math>o(f(a))= o(a)</math>.***נניח כי <math>o(a)=n</math>, הוכחנו ש<math>o(f(a))\leq n</math>.***נסמן <math>o(f(a))=k</math>.***לכן <math>\left(f(a)\right)^k=e_H</math>, ולכן <math>f(a^k)=e_H</math>.***כיוון שאיזומורפיזם הינו פונקציה חח"ע, נובע כי <math>a^k=e_G</math>, כלומר <math>o(a)\leq k</math>.***ביחד <math>k=n</math>.***לבסוף, נובע <math>o(f(a))</math> סופי אם"ם <math>o(a)</math> סופי, ולכן הם שווים גם אם אחד מהם הוא אינסוף.**אם f הומומורפיזם אזי <math>f(a^{-1})=\left(f(a)\right)^{-1}</math> (שימו לב שf לא צריכה להיות הפיכה, והסימון <math>f^{-1}(a)</math> לא בהכרח מוגדר ואינו קשור).***אכן <math>f(a)\cdot f(a^{-1})=f(e_G)=e_H</math>.  *הגדרה: גרעין של הומומורפיזם הוא אוסף האיברים שנשלחים לאיבר היחידה.*טענה: התמונה והגרעין של הומומורפיזם הינם תתי חבורות של הטוווח והתחום בהתאמה.**הוכחה לגבי התמונה:**יהי הומומורפיזם <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> נקראת '''שיכון קיילי'''.  *תכונות:*שיכון קיילי הינו הומומורפיזם.**<math>\varphi(a)\circ\varphi(b)=f_a\circ f_b</math>.**<math>f_a\circ f_b (x)=f_a(f_b(x))=a\cdot (b\cdot x)=(a\cdot b)\cdot (x) = f_{a\cdot b}(x)</math>.**לכן <math>\varphi(a)\circ\varphi(b)=\varphi(a\cdot b)</math>.*שיכון קיילי הינו חח"ע (לכן הוא נקרא שיכון).**אם <math>a\neq b</math>, אזי <math>f_a(e)=a\neq b=f_b(e)</math>.**כלומר <math>f_a\neq f_b</math> ולכן <math>\varphi(a)\neq\varphi(b)</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>, ולכן ביחד סדר האיבר מחלק את גודל החבורה.*תהי חבורה מגודל סופית עם מספר ראשוני חייבת להיות של איברים, אזי היא חבורה ציקלית. **אכן, וכל ניקח איבר פרט לאיבר היחידה יוצר אותהשונה מהנייטרלי, הסדר שלו חייב להיות המספר הראשוני (כי לראשוני אין מחלקים), ולכן החבורה הציקלית שלו שווה לכל החבורה. 

 ===הרצאה 5 חבורת אוילר, משפטי אוילר ופרמה; פרק 6 מ[http://abstract.ups.edu/aata/ הספר]=====חלוקה עם שארית===

*יהיו שני טבעיים שלמים <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.

===הרצאה 6 הצפנה סימטרית (מפתח פרטי), הצפנה אסימטרית (מפתח ציבורי), RSA; פרק 7 מ[http://abstract.ups.edu/aata/ הספר]=== *הצפנה; העברת מידע בערוץ פומבי כך שרק המשתתפים בהצפנה יוכלו להבין אותו, הוכחה לזהות כותב המידע (בין היתר כותב המידע לא יוכל להתנער ממנו), הוכחה לאמינות ושלימות המידע (המידע אינו חלקי ואף אחד לא שינה אותו).*[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).

====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>4\equiv 3 1 \mod 13</math> אך <math>2^4 \not\equiv 2 \mod 3</math> כלומר לחשב את ההופכי של e מוד n זה אמנם קל, אך לא יעיל לשום דבר...

===הרצאה 7 המשך הצפנה - בדיקת ראשוניות, דיפי הלמן, חתימה, חישוב חזקות;=== ====שיטת מילר-רבין לבדיקת ראשוניות====

**נזכור ש<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>.

====דיפי-הלמן====מומלץ לקרוא ישירות את המאמר פורץ הדרך בו הוצגה השיטה: [http://ee.stanford.edu/%7Ehellman/publications/24.pdf Diffie, Whitfield, and Martin E. Hellman. "New directions in cryptography."]  

*כמו כן הם מתאמים יוצר <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> ומוודאת ומוודא כי המידע שהיא קיבלה שהוא קיבל הוא המידע שבוב התכוון שאליס התכוונה לשלוח עד כדי המקרה הבלתי סביר של התנגשות.*אף אחד אחר לא יכל ליצור את הוכחת אמינות המידע הזו פרט לבובלאליס.

====חישוב חזקה====

===הרצאה 8 תת חבורות נורמליות, חבורות מנה, גרעין; פרקים 10,11 מ[http://abstract.ups.edu/aata/ הספר]===

*יהי הומומורפיזם בין חבורות <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>. 

===הרצאה 9 משפט האיזומורפיזם, מבוא לקידוד; פרק 11 מ[http://abstract.ups.edu/aata/ הספר]===*'''משפט האיזומורפיזם הראשון'''. יהי <math>\varphi:G\to H</math> איזומורפיזם הומומורפיזם בין חבורות. אזי <math>G/\ker(\varphi)\cong im(\varphi) </math>

====מבוא לקידוד====

 ===הרצאה 10 קידוד; פרק 8 מ[http://abstract.ups.edu/aata/ הספר]===

====קוד לינארי====

===הרצאה 11 המשך קידוד; פרק 8 מ[http://abstract.ups.edu/aata/ הספר]===

*<math>d_{min}\geq 3</math> אם ורק אם ב<math>H</math> אין עמודת אפסים וגם אין שתי עמודות זהות.

===הרצאה 12 חוג הפולינומים; פרקים 16,17 מ[http://abstract.ups.edu/aata/ הספר]===חלוקה עם שארית, אידיאלים, כל אידיאל הוא אידיאל ראשי.

===חוג הפולינומים=== *יהי <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>g(x)</math> מדרגה <math>m</math> מסוגל לזהות כל כמות של שגיאות, בתנאי שכולן נמצאות בתוך טווח של <math>m</math> ביטים.*הוכחה: **נניח שקרו טעויות בתוך טווח של <math>m</math> ביטים.**אם המילה החדשה חוקית, גם כל הזזה ציקלית שלה היא חוקית.**נזיז את <math>m</math> הביטים כך שיהיו בקצה הימני במקום של היתירות.**כיוון שהיתירות היא יחידה, בוודאות המילה אינה חוקית, סתירה.  *דוגמא:*<math>x^7-1=(1+x)(1+x+x^3)(1+x^2+x^3)</math>*לכן הקוד הנוצר על ידי הפולינום <math>g(x)=1+x+x^3</math> עבור וקטורי מידע באורך 4 הוא ציקלי. 

CRC בשימוש *פרוטוקול Ethernetמשתמש בתיקון שגיאות ציקלי הנקרא CRC32, ובפרט בפולינום:*<math>g(x)=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 מיליארד ביטים של מידע.