מבנים אלגבריים למדעי המחשב - ארז שיינר

ספר הקורס

ההרצאות מבוססות באופן כללי על הספר Abstarct Algebra - Theory and Applications by Thomas W. Judson

• סיכום ההרצאות מ2019 ע"י ספיר ביתן
• סיכום ההרצאות מ2021 ע"י רועי אוסקר

מבחנים לדוגמא

• מבחן לדוגמא 1 תשע"ח
  • פתרון מבחן לדוגמא 1 תשע"ח
• מבחן לדוגמא 2 תשע"ח
  • פתרון מבחן לדוגמא 2 תשע"ח
• מבחן לדוגמא 3 תשע"ח
  • פתרון מבחן לדוגמא 3 תשע"ח
• מבחן מועד א' תשע"ח
• מבחן מועד ב' תשע"ח
• מבחן מועד ג' תשע"ח
• מבחן מועד א' תשע"ט
  • פתרון מועד א' תשע"ט
• מבחן מועד ב' תשע"ט
  • פתרון מועד ב' תשע"ט
• מבחן מועד א' תש"ף
• מבחן מועד ב' תש"ף
• מבחן מועד א' תשפ"א
  • פתרון מבחן מועד א' תשפ"א
• מבחן מועד ב' תשפ"א
• מבחן מועד ג' תשפ"א
• מבחן מועד א' תשפ"ב
• מבחן מועד ב' תשפ"ב

• מבחנים משנים קודמות

נושאי ההרצאות

פלייליסט של הרצאות קבוצה 01 תשפ"א

פלייליסט של הרצאות קבוצה 02 תשפ"א

הרצאה 1 הקדמה; הסבר על קידוד והצפנה, מבוא למבנים אלגבריים

• קידוד הוא שיטה להעברת מידע ובין היתר מטרתו היא להבטיח את נכונות המידע ולזהות (ולתקן) שגיאות.
• הצפנה היא שיטה להסתרת מידע במקום בו כולם רואים את התוכן המועבר, דרך להבטיח מי הוא מקור המידע (חתימה) ודרך להבטיח את אמינות המידע (ללא חוסרים וללא שינויים).
• המבנים האלגבריים שאנו עוסקים בהם בקורס הם חבורה, חוג ושדה.

הרצאה 2 חבורות ותת חבורות; פרקים 3,4 מהספר

חבורות

• חבורה היא קבוצה G עם פעולה המקיימת:
  • סגירות
  • אסוציאטיביות
  • איבר נייטרלי
  • לכל איבר יש איבר הופכי

• חבורה המקיימת את חוק החילוף נקראת חבורה אבלית, קומוטטיבית או חילופית

• תכונת הצמצום: תהי חבורה G, אזי לכל [math]\displaystyle{ a,b,c\in G }[/math] אם [math]\displaystyle{ ab=ac }[/math] אזי [math]\displaystyle{ b=c }[/math].
  • הוכחה: נכפול באיבר ההופכי [math]\displaystyle{ a^{-1}(ab)=a^{-1}(ac) }[/math] ונשתמש באסוציאטיביות ובאיבר הנייטרלי.

• יחידות האיבר ההופכי: נובע מתכונת הצמצום שלכל איבר בחבורה קיים איבר הופכי יחיד.
  • הוכחה: אם [math]\displaystyle{ ab=ac=e_G }[/math] אזי [math]\displaystyle{ b=c }[/math].

• דוגמאות לחבורות:
  • [math]\displaystyle{ S_n }[/math] חבורת הפונקציות ההפיכות מקבוצה בגודל n לעצמה עם פעולת ההרכבה.
  • [math]\displaystyle{ GL_n(\mathbb{F}) }[/math] חבורת המטריצות ההפיכות עם כפל מטריצות.
  • [math]\displaystyle{ \mathbb{Z} }[/math] חבורת השלמים עם חיבור.
  • [math]\displaystyle{ \mathbb{Z}_n }[/math] חבורת השאריות עם חיבור מודולו n.

מכפלה קרטזית של חבורות

• תהיינה חבורות [math]\displaystyle{ G,H }[/math] המכפלה הקרטזית של החבורות [math]\displaystyle{ G\times H }[/math] (אוסף הזוגות הסדורים) היא חבורה עם הפעולה הבאה:

[math]\displaystyle{ (g_1,h_1)\cdot_{G\times H}(g_2,h_2)=(g_1\cdot_G g_2,h_1\cdot_H h_2) }[/math]

תת חבורות

• הגדרה: תהי חבורה G. תת קבוצה [math]\displaystyle{ H\subseteq G }[/math] נקראת תת חבורה של G אם היא חבורה ביחס לפעולה של G.

• קרטריון מקוצר לבדיקת תת חבורה:
• תת קבוצה H של חבורה G הינה תת חבורה אם ורק אם מתקיימים שני התנאים הבאים:
  • [math]\displaystyle{ e_G\in H }[/math].
  • לכל שני איברים [math]\displaystyle{ a,b\in H }[/math] מתקיים כי [math]\displaystyle{ ab^{-1}\in H }[/math].

• הוכחת הקריטריון המקוצר:
• בכיוון ראשון נניח כי H תת חבורה:
  • נוכיח כי [math]\displaystyle{ e_G\in H }[/math].
    • נניח H תת חבורה, לכן קיים בה איבר נייטרלי [math]\displaystyle{ e_H }[/math].
    • כיוון שמדובר באיבר נייטרלי בH מתקיים כי [math]\displaystyle{ e_H\cdot e_H=e_H }[/math].
    • מצד שני ברור ש[math]\displaystyle{ e_H\cdot e_G=e_H }[/math].
    • לכן [math]\displaystyle{ e_H\cdot e_H=e_H\cdot e_G }[/math] ולפי תכונת הצמצום נובע ש [math]\displaystyle{ e_H=e_G }[/math].
  • נוכיח כי לכל שני איברים [math]\displaystyle{ a,b\in H }[/math] מתקיים כי [math]\displaystyle{ ab^{-1}\in H }[/math].
    • יהיו [math]\displaystyle{ a,b\in H }[/math].
    • קיים בH הופכי לb, נקרא לו c.
    • לכן [math]\displaystyle{ bc=bb^{-1}=e_G }[/math] (הרי הוכחנו כבר ש[math]\displaystyle{ e_H=e_G }[/math]).
    • שוב לפי תכונת הצמצום נובע כי [math]\displaystyle{ b^{-1}=c\in H }[/math].
    • לפי הסגירות של H נובע כי [math]\displaystyle{ ab^{-1}\in H }[/math].
• בכיוון השני, נוכיח כי H תת חבורה:
  • סגירות:
    • יהיו [math]\displaystyle{ a,b\in H }[/math].
    • ידוע כי [math]\displaystyle{ e_G\in H }[/math], לכן [math]\displaystyle{ e_G\cdot b^{-1}\in H }[/math], כלומר [math]\displaystyle{ b^{-1}\in H }[/math].
    • לכן [math]\displaystyle{ a\cdot \left(b^{-1}\right)^{-1}\in H }[/math] כלומר [math]\displaystyle{ a\cdot b \in H }[/math].
  • אסוציאטיביות:
    • נתון כי הפעולה אסוציאטיבית, הרי זו הפעולה של G וG חבורה.
  • איבר נייטרלי:
    • נתון כי [math]\displaystyle{ e_G\in H }[/math].
  • איברים הופכיים:
    • יהי [math]\displaystyle{ a\in H }[/math].
    • לכן [math]\displaystyle{ a^{-1}=e_G\cdot a^{-1}\in H }[/math] בדומה להוכחת הסגירות.

• תת חבורות;
  • [math]\displaystyle{ SL_n(\mathbb{F}) }[/math] חבורת המטריצות בעלות דטרמיננטה שווה 1, עם כפל מטריצות.
  • קווטרניונים [math]\displaystyle{ \left\{ \pm\begin{pmatrix}1&0\\0&1\end{pmatrix}, \pm\begin{pmatrix}0&1\\-1&0\end{pmatrix}, \pm\begin{pmatrix}0&i\\i&0\end{pmatrix}, \pm\begin{pmatrix}i&0\\0&-i\end{pmatrix} \right\}\subseteq GL_2\left(\mathbb{C}\right) }[/math]
  • [math]\displaystyle{ \mathbb{C}\setminus \{0\}=\left\{\begin{pmatrix}a&b\\-b&a\end{pmatrix}:(a,b)\neq (0,0)\right\}\subseteq GL_2\left(\mathbb{R}\right) }[/math].
  • [math]\displaystyle{ \{z\in\mathbb{C}:|z|=1\}\subseteq \mathbb{C}\setminus \{0\} }[/math] מעגל היחידה.

תת חבורות ציקליות

• כתיב אקספוננט [math]\displaystyle{ g^n=g\cdots g }[/math] או כפל [math]\displaystyle{ ng=g+\cdots+g }[/math] בהתאם לסימון פעולת החבורה.

• תהי G חבורה, לכל [math]\displaystyle{ a\in G,n\in \mathbb{N} }[/math] נגדיר:
  • [math]\displaystyle{ a^0=e_G }[/math].
  • [math]\displaystyle{ a^{-n}=(a^{-1})^n }[/math]

• הערה: קל להוכיח כי [math]\displaystyle{ (a^{-1})^n=(a^n)^{-1} }[/math]

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

• תהי חבורה G, ויהי [math]\displaystyle{ a\in G }[/math]. תת החבורה הציקלית הנוצרת על ידי a הינה [math]\displaystyle{ \lt a\gt =\{a^n|n\in\mathbb{Z}\} }[/math]
• הוכחה שאכן מדובר בתת חבורה:
  • [math]\displaystyle{ e_G=a^0\in\lt a\gt }[/math].
  • יהיו [math]\displaystyle{ a^n,a^k\in\lt a\gt }[/math] אזי [math]\displaystyle{ a^n\cdot (a^k)^{-1}=a^n\cdot (a^{-1})^k=a^{n-k}\in\lt a\gt }[/math].

• תהי חבורה G, אזי סדר כל איבר הוא גודל החבורה הציקלית שהוא יוצר, כלומר [math]\displaystyle{ |\lt a\gt |=o(a) }[/math].
• הוכחה:
  • ראשית נוכיח עבור המקרה בו סדר האיבר סופי [math]\displaystyle{ o(a)=n }[/math].
    • רוצים להוכיח כי [math]\displaystyle{ \lt a\gt =\{e_G,a,a^2,...,a^{n-1}\} }[/math] וכי כל האיברים בקבוצה זו שונים זה מזה (אחרת כמות האיברים קטנה יותר מn).
    • ברור שהחזקות של a שייכות לתת החבורה הציקלית.
    • יהי k כלשהו, נסמן בr את השארית [math]\displaystyle{ r=k \mod n }[/math] כלומר [math]\displaystyle{ k=pn+r }[/math] עבור [math]\displaystyle{ p\in\mathbb{Z}, 0\leq r\leq n-1 }[/math].
    • [math]\displaystyle{ a^k=(a^n)^pa^r=e_G^pa^r=a^r }[/math].
    • כעת נניח כי קיימות שתי חזקות שונות [math]\displaystyle{ 0\leq r_1\lt r_2\leq n-1 }[/math] כך ש [math]\displaystyle{ a^{r_1}=a^{r_2} }[/math].
    • לכן [math]\displaystyle{ a^{r_2-r_1}=e_G }[/math].
    • אבל [math]\displaystyle{ r_2-r_1\leq n-1 \lt n }[/math] בסתירה לכך ש[math]\displaystyle{ o(a)=n }[/math].
  • כעת נניח כי סדר האיבר הוא אינסוף, ונוכיח כי גודל תת החבורה הציקלית שהוא יוצר הוא אינסוף.
    • נניח בשלילה ש [math]\displaystyle{ \lt a\gt }[/math] סופית, לכן לפחות שתי חזקות שונות של a נותנות אותו איבר.
    • נסמן [math]\displaystyle{ n\lt k }[/math] כך ש [math]\displaystyle{ a^n=a^k }[/math].
    • לכן [math]\displaystyle{ a^{k-n}=e_G }[/math] בסתירה לכך שסדר האיבר הוא אינסוף.

• מסקנה: תהי חבורה סופית G, אזי לכל איבר בחבורה יש סדר סופי.
  • הוכחה: גודל תת החבורה הציקלית חייב להיות סופי.

• תת חבורות ציקליות:
  • [math]\displaystyle{ 2\mathbb{Z} }[/math].
  • [math]\displaystyle{ \{z\in\mathbb{C}:z^n=1\}\subseteq \mathbb{C}\setminus \{0\} }[/math] שורשי היחידה מסדר n.

הרצאה 3 חבורת תמורות, סימן התמורה; פרק 5 מהספר

סימן של תמורה

• נביט בחבורת התמורות [math]\displaystyle{ S_n }[/math].
• עבור [math]\displaystyle{ f\in S_n }[/math] נגדיר את הסימן [math]\displaystyle{ \mathrm{sign}(f):=\Pi_{i\neq j}\frac{x_{f(i)}-x_{f(j)}}{x_i-x_j} }[/math].
• הסימן של תמורה הוא תמיד פלוס או מינוס 1.
• אם סימן התמורה הוא מינוס אחד אומרים שהיא אי-זוגית או שלילית, ואם הסימן הוא אחד אומרים שהיא זוגית או חיובית.

• כפליות הסימן: תהיינה שתי תמורות [math]\displaystyle{ f,g\in S_n }[/math], אזי [math]\displaystyle{ \mathrm{sign}(f\circ g)=\mathrm{sign}(f)\cdot\mathrm{sign}(g) }[/math].
  • הוכחה:
  • [math]\displaystyle{ \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]\displaystyle{ i\neq j }[/math] שווה לאוסף הזוגות [math]\displaystyle{ g(i),g(j) }[/math], ולכן [math]\displaystyle{ \Pi_{i\neq j}\frac{x_{f(g(i))}-x_{f(g(j))}}{x_{g(i)}-x_{g(j)}}=\mathrm{sign}(f) }[/math].
  • סה"כ קיבלנו [math]\displaystyle{ \mathrm{sign}(f\circ g)=\mathrm{sign}(f)\cdot\mathrm{sign}(g) }[/math].

מחזורים

• מחזור [math]\displaystyle{ (a_1\ a_2\ \cdots \ a_k) }[/math] מייצג את התמורה f המקיימת [math]\displaystyle{ f(a_1)=a_2,...,f(a_{k-1})=a_k,f(a_k)=a_1 }[/math] ולכל איבר אחר [math]\displaystyle{ f(a)=a }[/math].
• לדוגמא: [math]\displaystyle{ \begin{pmatrix}1&2&3&4&5\\4&2&5&3&1\end{pmatrix}=(1\ 4\ 3\ 5)\in S_5 }[/math]

• כל תמורה ניתן להציג כהרכבה של מחזורים זרים, ואת תמורה הזהות ניתן להציג כ[math]\displaystyle{ (1) }[/math].

• חילוף הוא מחזור באורך 2.
• חילוף הוא תמורה אי זוגית.
  • נוכיח עבור [math]\displaystyle{ f=(1\ 2)\in S_n }[/math]. (זה מספיק כיוון שהשם של האיברים לא משנה.)
  • [math]\displaystyle{ \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]\displaystyle{ (a_1\ a_2\ \cdots \ a_k)=(a_1\ a_2)(a_2\ a_3)\cdot (a_{k-1}\ a_k) }[/math]
  • כל איבר שלא מוזכר במחזור נשלח לעצמו, ונציב בשני הצדדים את [math]\displaystyle{ a_1,...,a_{k-1} }[/math] ונראה כי הפונקציות שוות.
  • כיוון שמדובר בפונקציה הפיכה, אין צורך לבדוק את האיבר האחרון [math]\displaystyle{ a_k }[/math].

• מסקנה: כיוון שסימן כל חילוף הוא שלילי ולפי כפליות הסימן, הסימן של מחזור באורך k הוא [math]\displaystyle{ (-1)^{k-1} }[/math].
• דוגמא:
  • [math]\displaystyle{ 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]\displaystyle{ \mathrm{sign}(f)=(-1)\cdot(-1)=1 }[/math], כלומר מדובר בתמורה זוגית.

הרצאה 4 הומומורפיזמים, איזומורפיזמים, משפט קיילי, משפט לגראנג'; פרקים 9 ו6 מהספר

הומומורפיזם, איזומורפיזם

• הגדרה: תהיינה שתי חבורות G,H ותהי פונקציה [math]\displaystyle{ f:G\to H }[/math]. אזי f נקראת הומומורפיזם אם לכל [math]\displaystyle{ a,b\in G }[/math] מתקיים [math]\displaystyle{ f(a\cdot_G b)=f(a)\cdot_H f(b) }[/math].
• שימו לב ש [math]\displaystyle{ \cdot_G }[/math] היא הפעולה של G, ו[math]\displaystyle{ \cdot_H }[/math] היא הפעולה של H.
• הומומורפיזם שהוא פונקציה חח"ע ועל נקרא איזומורפיזם.
• הומומורפיזם שומר במובן מסויים על המבנה של החבורה, ואיזומורפיזם מראה שהחבורות הן 'אותה גברת בשינוי אדרת'.

• תכונות:
  • אם [math]\displaystyle{ f:G\to H }[/math] הומומורפיזם אזי [math]\displaystyle{ f(e_G)=e_H }[/math].
    • הוכחה:
    • [math]\displaystyle{ f(e_G)=f(e_G\cdot e_G)=f(e_G)\cdot f(e_G) }[/math].
    • לפי תכונת הצמצום [math]\displaystyle{ f(e_G)=e_H }[/math].
  • אם f הומומופיזם אזי [math]\displaystyle{ o(f(a))\leq o(a) }[/math].
    • אם [math]\displaystyle{ o(a)=n }[/math] אזי [math]\displaystyle{ a^n=e_G }[/math].
    • לכן [math]\displaystyle{ f(a^n)=\left(f(a)\right)^n=e_H }[/math].
    • לכן [math]\displaystyle{ o(f(a))\leq n=o(a) }[/math].
  • אם f איזומורפיזם אזי [math]\displaystyle{ o(f(a))= o(a) }[/math].
    • נניח כי [math]\displaystyle{ o(a)=n }[/math], הוכחנו ש[math]\displaystyle{ o(f(a))\leq n }[/math].
    • נסמן [math]\displaystyle{ o(f(a))=k }[/math].
    • לכן [math]\displaystyle{ \left(f(a)\right)^k=e_H }[/math], ולכן [math]\displaystyle{ f(a^k)=e_H }[/math].
    • כיוון שאיזומורפיזם הינו פונקציה חח"ע, נובע כי [math]\displaystyle{ a^k=e_G }[/math], כלומר [math]\displaystyle{ o(a)\leq k }[/math].
    • ביחד [math]\displaystyle{ k=n }[/math].
    • לבסוף, נובע [math]\displaystyle{ o(f(a)) }[/math] סופי אם"ם [math]\displaystyle{ o(a) }[/math] סופי, ולכן הם שווים גם אם אחד מהם הוא אינסוף.
  • אם f הומומורפיזם אזי [math]\displaystyle{ f(a^{-1})=\left(f(a)\right)^{-1} }[/math] (שימו לב שf לא צריכה להיות הפיכה, והסימון [math]\displaystyle{ f^{-1}(a) }[/math] לא בהכרח מוגדר ואינו קשור).
    • אכן [math]\displaystyle{ f(a)\cdot f(a^{-1})=f(e_G)=e_H }[/math].

• הגדרה: גרעין של הומומורפיזם הוא אוסף האיברים שנשלחים לאיבר היחידה.
• טענה: התמונה והגרעין של הומומורפיזם הינם תתי חבורות של הטוווח והתחום בהתאמה.
  • הוכחה לגבי התמונה:
  • יהי הומומורפיזם [math]\displaystyle{ f:G\to H }[/math].
  • ראשית, [math]\displaystyle{ f(e_G)=e_H }[/math] ולכן [math]\displaystyle{ e_H\in Im(f) }[/math].
  • שנית, יהיו [math]\displaystyle{ h_1,h_2\in Im(f) }[/math] לכן קיימים [math]\displaystyle{ g_1,g_2\in G }[/math] כך ש [math]\displaystyle{ f(g_i)=h_i }[/math].
  • [math]\displaystyle{ 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]\displaystyle{ Im(f) }[/math] הינה תת חבורה של [math]\displaystyle{ H }[/math].

משפט קיילי

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

• תכונות:
• שיכון קיילי הינו הומומורפיזם.
  • [math]\displaystyle{ \varphi(a)\circ\varphi(b)=f_a\circ f_b }[/math].
  • [math]\displaystyle{ 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]\displaystyle{ \varphi(a)\circ\varphi(b)=\varphi(a\cdot b) }[/math].
• שיכון קיילי הינו חח"ע (לכן הוא נקרא שיכון).
  • אם [math]\displaystyle{ a\neq b }[/math], אזי [math]\displaystyle{ f_a(e)=a\neq b=f_b(e) }[/math].
  • כלומר [math]\displaystyle{ f_a\neq f_b }[/math] ולכן [math]\displaystyle{ \varphi(a)\neq\varphi(b) }[/math].

• מסקנה: משפט קיילי כל חבורה איזומורפית לתת חבורה של חבורת תמורות.
  • הוכחה: החבורה איזומורפית לתמונה שלה בשיכון קיילי.

משפט לגראנג'

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

• הגדרה: האינדקס [math]\displaystyle{ [G:H] }[/math] מוגדר להיות מספר המחלקות השונות ש[math]\displaystyle{ H }[/math] מגדירה.
• כיוון שראינו שהמחלקות הן בעצם מחלקות שקילות שוות בגודלן המחלקות את G, נובע משפט לגראנג' :עבור חבורות סופיות, [math]\displaystyle{ |G|=|H|\cdot [G:H] }[/math].
• נובע כי הגודל (סדר) של כל תת חבורה, מחלק את הגודל (סדר) של החבורה כולה.
• יהי [math]\displaystyle{ a\in G }[/math] איבר מסדר [math]\displaystyle{ n }[/math]. ראינו כי [math]\displaystyle{ |\lt a\gt |=n }[/math], ולכן ביחד סדר האיבר מחלק את גודל החבורה.
• תהי חבורה סופית עם מספר ראשוני של איברים, אזי היא חבורה ציקלית.
  • אכן, ניקח איבר שונה מהנייטרלי, הסדר שלו חייב להיות המספר הראשוני (כי לראשוני אין מחלקים), ולכן החבורה הציקלית שלו שווה לכל החבורה.

• לפני הרצאה זו, חזרו בבקשה על הנושא של יחסי שקילות. ניתן לצפות בסרטון הבא:

הרצאה 5 חבורת אוילר, משפטי אוילר ופרמה; פרק 6 מהספר

חלוקה עם שארית

• זוג מספרים שלמים [math]\displaystyle{ a,b }[/math] נקראים שקולים מודולו n אם קיים שלם [math]\displaystyle{ q }[/math] כך ש [math]\displaystyle{ a=b+q\cdot n }[/math]
• חלוקה עם שארית: לכל מספר טבעי a ולכל מספר שלם b קיים זוג שלמים יחיד [math]\displaystyle{ q,r }[/math] כך ש [math]\displaystyle{ b=q\cdot a+r }[/math] וגם [math]\displaystyle{ 0\leq r \lt a }[/math].
  • קיום:
    • יהי [math]\displaystyle{ a\in\mathbb{N} }[/math]
    • אם [math]\displaystyle{ b=0 }[/math] אזי [math]\displaystyle{ b=0\cdot a + 0 }[/math].
    • יהי [math]\displaystyle{ b\geq 0 }[/math] עבורו הטענה נכונה, נוכיח עבור [math]\displaystyle{ b+1 }[/math].
    • [math]\displaystyle{ b+1=qa+r+1 }[/math].
    • אם [math]\displaystyle{ r+1\lt a }[/math] סיימנו, אחרת [math]\displaystyle{ r+1=a }[/math] ולכן [math]\displaystyle{ b=(q+1)a+0 }[/math].
    • אם [math]\displaystyle{ b\lt 0 }[/math] אזי [math]\displaystyle{ -b=qa+r }[/math].
    • אם [math]\displaystyle{ r=0 }[/math] אזי [math]\displaystyle{ b=(-q)a+0 }[/math] וסיימנו.
    • אם [math]\displaystyle{ 0\lt r\lt a }[/math] אזי [math]\displaystyle{ b=-qa-r=-qa-a+a-r=(-q-1)a+(a-r) }[/math] כאשר [math]\displaystyle{ 0\lt a-r\lt a }[/math].
  • יחידות:
    • נניח [math]\displaystyle{ b=q_1a+r_1=q_2a+r_2 }[/math].
    • לכן [math]\displaystyle{ (q_1-q_2)a=r_2-r_1 }[/math].
    • אבל [math]\displaystyle{ -(a-1)\leq r_2-r_2\leq a-1 }[/math], ולכן [math]\displaystyle{ r_2-r_1\neq ka }[/math].
    • לכן [math]\displaystyle{ q_1-q_2=0 }[/math] כלומר [math]\displaystyle{ q_1=q_2 }[/math] ולכן גם [math]\displaystyle{ r_1=r_2 }[/math].
• המספר q נקרא מנת החלוקה והמספר r נקרא שארית החלוקה.
• יהיו שני שלמים [math]\displaystyle{ a,b }[/math] ויהיו [math]\displaystyle{ r_a,r_b }[/math] השאריות שלהם בחלוקה בn. אזי [math]\displaystyle{ ab\equiv r_ar_b \mod n }[/math]
  • [math]\displaystyle{ 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]\displaystyle{ a^k\equiv r_a^k \mod n }[/math].

המחלק המשותף הגדול ביותר

• לכל שני מספרים טבעיים [math]\displaystyle{ k\lt n }[/math] מתקיים כי [math]\displaystyle{ gcd(n,k)=gcd(n-k,k) }[/math]
  • נוכיח שכל מספר שמחלק את [math]\displaystyle{ n,k }[/math] מחלק גם את [math]\displaystyle{ n-k,k }[/math] וההפך, ולכן הגדול ביותר הוא אותו האחד.
  • אם [math]\displaystyle{ a }[/math] מחלק את [math]\displaystyle{ n,k }[/math] אזי [math]\displaystyle{ n=qa,k=ta }[/math], לכן [math]\displaystyle{ n-k=(q-t)a }[/math].
  • אם [math]\displaystyle{ a }[/math] מחלק את [math]\displaystyle{ n-k,k }[/math] אזי [math]\displaystyle{ n-k=qa,k=ta }[/math] ולכן [math]\displaystyle{ n=(q+t)a }[/math].
• לכל שני מספריים טבעיים [math]\displaystyle{ n,k }[/math] קיימים מספרים שלמים [math]\displaystyle{ a,b }[/math] כך ש [math]\displaystyle{ an+bk=gcd(n,k) }[/math]
  • עבור [math]\displaystyle{ n=k=1 }[/math] מתקיים כי [math]\displaystyle{ 1\cdot 1 + 0\cdot 1 = 1 = gcd(1,1) }[/math].
  • נניח שהטענה נכונה לכל [math]\displaystyle{ n+k\lt m }[/math] נוכיח שהיא נכונה עבור [math]\displaystyle{ n+k=m }[/math].
  • אם [math]\displaystyle{ n=k }[/math] אזי [math]\displaystyle{ 1\cdot n + 0\cdot k = n =gcd(n,n)=gcd(n,k) }[/math].
  • אחרת, אם [math]\displaystyle{ n\gt k }[/math] מתקיים כי [math]\displaystyle{ gcd(n,k)=gcd(n-k,k)=a(n-k)+bk=an+(b-a)k }[/math].
  • שימו לב שהנחת האינדוקציה התקיימה עבור הזוג [math]\displaystyle{ n-k,k }[/math].

• שני מספרים טבעיים n,k נקראים זרים אם [math]\displaystyle{ gcd(n,k)=1 }[/math]
• ב[math]\displaystyle{ \mathbb{Z}_n }[/math] עם פעולת הכפל מודולו n האיברים ההפיכים הם בדיוק המספרים הזרים ל n.
  • נניח [math]\displaystyle{ k\in\mathbb{Z}_n }[/math] אינו זר לn, כלומר [math]\displaystyle{ gcd(n,k)=a\gt 1 }[/math].
    • לכן [math]\displaystyle{ n=qa,k=ta }[/math] לכן [math]\displaystyle{ qk=tn }[/math] ולכן [math]\displaystyle{ qk=0\in\mathbb{Z}_n }[/math] כלומר k מחלק אפס ואינו הפיך.
  • נניח [math]\displaystyle{ k\in\mathbb{Z}_n }[/math] זר לn כלומר [math]\displaystyle{ gcd(n,k)=1 }[/math].
    • לכן קיימים שלמים כך ש [math]\displaystyle{ an+bk=1 }[/math] לכן [math]\displaystyle{ b\cdot k \equiv 1 \mod n }[/math].
• עבור מספר טבעי [math]\displaystyle{ 1\lt n }[/math] קבוצת המספרים הטבעיים הזרים לn וקטנים ממנו מהווה חבורה ביחס לכפל מודולו n, היא נקראית חבורת אוילר ומסומנת [math]\displaystyle{ U_n }[/math].
  • הוכחה ש[math]\displaystyle{ U_n }[/math] חבורה:
  • סגירות: מכפלת הפיכים היא הפיכה.
  • אסוציאטיביות: נובע מהאסוציאטיביות של הכפל.
  • איבר נייטרלי: 1.
  • הפיכים: ברור מההגדרה.
• [math]\displaystyle{ \mathbb{Z}_n }[/math] עם פעולות חיבור וכפל מודולו n הוא שדה אם ורק אם n הינו מספר ראשוני.
  • אכן, כל המספרים החיוביים הקטנים מn הפיכים אם"ם כולם זרים לו אם"ם הוא ראשוני.

פונקצית אוילר, משפט אוילר והמשפט הקטן של פרמה

• פונקצית אוילר [math]\displaystyle{ \phi(n) }[/math] היא מספר המספרים הטבעיים שקטנים או שווים לn וזרים לו.
• משפט אוילר - יהיו שני מספרים טבעיים זרים [math]\displaystyle{ a\lt n }[/math]. אזי [math]\displaystyle{ a^{\phi(n)}\equiv 1 }[/math] מודולו n.
  • עבור [math]\displaystyle{ n\gt 1 }[/math], מתקיים כי [math]\displaystyle{ a\in U_n }[/math] וגם [math]\displaystyle{ |U_n|=\phi(n) }[/math].
  • הסדר של איבר בחבורה סופית חייב לחלק את סדר החבורה, נסמן [math]\displaystyle{ o(a)=k }[/math] ולכן [math]\displaystyle{ \phi(n)=t\cdot k }[/math].
  • לכן [math]\displaystyle{ a^{\phi(n)} = (a^k)^t=1 }[/math] כאשר הכפל נעשה ב[math]\displaystyle{ U_n }[/math].
• המשפט הקטן של פרמה - יהי p ראשוני ומספר טבעי [math]\displaystyle{ a\lt p }[/math] אזי [math]\displaystyle{ a^{p-1}\equiv 1 }[/math] מודולו p.
  • זו מסקנה ישירה ממשפט אוילר (אמנם למעשה אוילר הוא הכללה של פרמה), כיוון ש [math]\displaystyle{ \phi(p)=p-1 }[/math].
• בפרט, בתנאי המשפט, [math]\displaystyle{ a^p\equiv a }[/math] מודולו p.
  • למעשה [math]\displaystyle{ a^p\equiv a }[/math] מודולו p נכון לכל ראשוני p ולכל טבעי a.
  • כיוון שאם a זר לp מתקיים כי גם השארית [math]\displaystyle{ r_a }[/math] זרה ל [math]\displaystyle{ p }[/math] ולכן [math]\displaystyle{ a^{p-1}\equiv r_a^{p-1}\equiv 1 }[/math] מודולו p.
  • אם a אינו זר לp אזי הוא חייב להתחלק בראשוני p, ולכן [math]\displaystyle{ a^p\equiv a \equiv 0 }[/math] מודולו p.

הרצאה 6 הצפנה סימטרית (מפתח פרטי), הצפנה אסימטרית (מפתח ציבורי), RSA; פרק 7 מהספר

• הצפנה; העברת מידע בערוץ פומבי כך שרק המשתתפים בהצפנה יוכלו להבין אותו, הוכחה לזהות כותב המידע (בין היתר כותב המידע לא יוכל להתנער ממנו), הוכחה לאמינות ושלימות המידע (המידע אינו חלקי ואף אחד לא שינה אותו).
• הצפנה סימטרית - הצפנה בה לשני הצדדים יש סוד משותף שהעבירו מראש בערוץ שאינו פומבי (משאית ברינקס, לנסוע לחנות לאסוף כרטיס sim).
• הצפנה פומבית - הצפנה ללא סוד מתואם מראש, באמצעות מפתחות פומביים (שכולם רואים).
• פרקטית הצדדים מעבירים מפתח סודי באמצעות הצפנה פומבית, ואז עוברים להצפנה סימטרית.

• ההצפנה "המושלמת" - רצף בינארי אקראי באורך המידע המוסכם על שני הצדדים. ללא תלות במידע ובחוקיותו, חיבור בכל ביט (xor) של המידע עם הרצף ייצר תוכן שבו לכל ביט יש סיכוי שווה להיות 0 או 1.
• אם הרצף קצר מהמידע וחוזר על עצמו, חיבור שתי חתיכות שנשלחו יאפס את הרצף הסודי וישאיר לנו שתי חתיכות מידע גלוי המחוברות (זה כמעט מידע חשוף).

• קוד חילוף אותיות - נשבר ע"י חקר סטטיסטיקת שכיחות האותיות. אם המידע עובר תהליך שגורם לו להראות אקראי - עדיף
• מטא דטא - מידע על המידע שעשוי לעניין אותנו:
  • אם רצף נשלח פעמיים, גם אם אין אנו יודעים מהו, ייתכן שנסיק מההקשר.
  • הזמן שבו נשלח מסר (אמצע הלילה למשל).
  • הזמן שלקח למכונה להצפין את המידע.
  • עצם העובדה ששני צדדים מסוימים מדברים (רוסיה ונציגי קמפיין לנשיאות ארה"ב).
  • אורך המידע (בהנחה שהוא אינו מרופד באפסים).

RSA

מומלץ לקרוא ישירות את המאמר פורץ הדרך בו הוצגה השיטה:

Rivest, Ronald L., Adi Shamir, and Leonard Adleman. "A method for obtaining digital signatures and public-key cryptosystems."

• אליס בוחרת שני ראשוניים גדולים [math]\displaystyle{ \{p,q\} }[/math] זה הסוד שלה.
• אליס מחשבת את המכפלה [math]\displaystyle{ n=p\cdot q }[/math]
• אליס מחשבת את פונקצית אוילר [math]\displaystyle{ m=\phi(n)=(p-1)(q-1) }[/math]
• (הסבר - המספרים שאינם זרים לn מחלקים את אחד הראשוניים. [math]\displaystyle{ p,2p,3p,...,q\cdot p }[/math] וגם [math]\displaystyle{ q,2q,3q,...,p\cdot q }[/math]. סה"כ [math]\displaystyle{ p+q-1 }[/math] כי [math]\displaystyle{ n=p\cdot q }[/math] נספר פעמיים.)
• אליס בוחרת מספר כלשהו e כך שהוא זר לm.
• אליס מחשבת את ההופכי של e מודולו m, נקרא לו d. היא יודעת לעשות את זה כיוון שהיא הקשיבה בהרצאה קודמת על gcd ומציאת הופכי.
• אליס מפרסמת לכל העולם ואחותו את זוג המספרים [math]\displaystyle{ n,e }[/math]

• כעת בוב מעוניין לשלוח לאליס מידע שרק היא תוכל לפענח.
• בוב בעצם הולך "לנעול" את המידע באמצעות המנעול [math]\displaystyle{ e,n }[/math] של אליס. כל אחד יכול לנעול אותו, ורק אליס יודעת לפתוח אותו.
• המידע שבוב מעוניין לשלוח הוא מספר [math]\displaystyle{ x\lt n }[/math], בוב שולח את המידע המוצפן [math]\displaystyle{ x^e\mod n }[/math]
• אם בוב רוצה לשלוח יותר מידע, הוא יצטרך לפרק אותו לחתיכות. שימו לב שאם המנעול של אליס ישאר קבוע לחלוטין זה יהווה חולשה.

• אליס מקבלת את המידע המוצפן ומפענחת אותו באופן הבא: [math]\displaystyle{ x=\left(x^e\right)^d \mod n }[/math]
• הוכחה - נחלק לשני מקרים.
• אם [math]\displaystyle{ gcd(x,n)=1 }[/math]:
  • נתון כי [math]\displaystyle{ de=km+1=k\phi(n)+1 }[/math].
  • [math]\displaystyle{ \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]\displaystyle{ x^{\phi(n)}\equiv 1 \mod n }[/math]
• אם [math]\displaystyle{ gcd(x,n)\neq 1 }[/math]:
  • כיוון ש[math]\displaystyle{ n=p\cdot q }[/math] אז x הוא כפולה של p או q. נוכיח במקרה שx מתחלק בp.
  • קיים [math]\displaystyle{ h\lt q }[/math] עבורו [math]\displaystyle{ x=hp }[/math] וכמו כן x זר לq (אחרת בשני המקרים יוצא ש [math]\displaystyle{ x\geq n }[/math]).
  • לכן לפי פרמה הקטן יוצא ש [math]\displaystyle{ x^{q-1}\equiv 1 \mod q }[/math]
  • לכן [math]\displaystyle{ x^{km}=x^{k(p-1)(q-1)}=\left(x^{q-1}\right)^{k(p-1)}\equiv 1 \mod q }[/math]
  • לכן [math]\displaystyle{ x^{de}=x^{km+1}=x^{km}x=(1+tq)x=x+tqhp=x+th\cdot n\equiv x \mod n }[/math]

• שימו לב: אמנם [math]\displaystyle{ 4\equiv 1 \mod 3 }[/math] אך [math]\displaystyle{ 2^4 \not\equiv 2 \mod 3 }[/math] כלומר לחשב את ההופכי של e מוד n זה אמנם קל, אך לא יעיל לשום דבר...

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

שיטת מילר-רבין לבדיקת ראשוניות

• חלק מהותי בשיטות שאנו לומדים הוא מציאת ראשוניים גדולים. כיצד הדבר נעשה? האם יש רשימה גדולה של כל הראשוניים בעולם?
• ידוע שכמות הראשוניים עד המספר [math]\displaystyle{ n }[/math] היא בערך [math]\displaystyle{ \frac{n}{\ln(n)} }[/math].
• לכן הסיכוי בבחירת מספר אקראי עד [math]\displaystyle{ n }[/math] שהוא יהיה ראשוני הוא בערך [math]\displaystyle{ \frac{1}{\ln(n)} }[/math].
• אנו זקוקים למבחן ראשוניות - נגריל מספרים אקראיים ונבדוק האם הם ראשוניים, ומהר מאד נמצא אחד כזה בהתחשב בסיכוי הנ"ל.
• זכרו שפירוק לגורמים ראשוניים היא בעייה קשה (אחרת RSA מיותר ממילא).

• לפי משפט פרמה הקטן, אם [math]\displaystyle{ p }[/math] ראשוני, אזי לכל [math]\displaystyle{ a\lt p }[/math] מתקיים [math]\displaystyle{ a^{p-1}\equiv 1 \mod p }[/math].
• האם ההפך נכון? כלומר, האם [math]\displaystyle{ a^{p-1}\equiv 1 \mod p }[/math] רומז ש[math]\displaystyle{ p }[/math] ראשוני?
• מספרי קרמייקל מקיימים את התכונה הזו כמעט לכל [math]\displaystyle{ a }[/math] למרות שאינם ראשוניים.

• טענה: אם [math]\displaystyle{ p }[/math] ראשוני, ו[math]\displaystyle{ x\in U_p }[/math] איבר כך ש [math]\displaystyle{ x^2=1 }[/math] אזי [math]\displaystyle{ x=\pm 1 }[/math]
• הוכחה:
  • נזכור ש[math]\displaystyle{ \mathbb{Z}_p }[/math] הוא שדה כיוון שמדובר במספר ראשוני, ולכן אין ב[math]\displaystyle{ U_p=\mathbb{Z}/\{0\} }[/math] מחלקי אפס.
  • [math]\displaystyle{ x^2=1 }[/math] אם"ם [math]\displaystyle{ (x-1)(x+1)=0 }[/math] אם"ם [math]\displaystyle{ x=\pm 1 }[/math]

• הגדרה:
  • בהנתן מספר n, ונסמן [math]\displaystyle{ n-1=2^s\cdot r }[/math] עבור r אי זוגי. אומרים שהמספר [math]\displaystyle{ 1\leq a \lt n }[/math] הוא עד חזק לראשוניות של n אם אחד מהתנאים הבאים מתקיים:
    • [math]\displaystyle{ a^r\equiv 1 \mod n }[/math]
    • [math]\displaystyle{ a^{2^kr}\equiv n-1 \mod n }[/math] עבור [math]\displaystyle{ 1\leq k \leq s-1 }[/math].

• שימו לב: [math]\displaystyle{ n-1\equiv -1 \mod n }[/math]

• אם [math]\displaystyle{ p }[/math] ראשוני אזי כל המספרים [math]\displaystyle{ 1\lt a\lt p }[/math] הם עדים חזקים לכך.
  • הוכחה:
    • לפי אוילר [math]\displaystyle{ a^{p-1}\equiv 1 \mod p }[/math] .
    • אם נעלה את [math]\displaystyle{ a^r }[/math] בריבוע s פעמים נקבל [math]\displaystyle{ a^{2^s\cdot r}=a^{p-1}\equiv 1 \mod p }[/math].
    • לכן אם [math]\displaystyle{ a^r\not \equiv 1 \mod p }[/math], בשלב כלשהו נעלה מספר שאינו 1 בריבוע ונקבל 1, לכן מספר זה חייב להיות [math]\displaystyle{ -1 }[/math].
• אם [math]\displaystyle{ p }[/math] אינו ראשוני, ידוע שלכל היותר רבע מבין המספרים [math]\displaystyle{ a }[/math] יכולים להיות עדים חזקים.
• לכן הסיכוי שמצאנו עד חזק למרות שהמספר שאנו בודקים אינו ראשוני הוא רבע.
• אם נבחן k מספרים אקראיים שונים, הסיכוי שכולם יהיו עדים חזקים אך המספר אינו ראשוני הוא [math]\displaystyle{ \frac{1}{4^k} }[/math] (נמוך מאד).

דיפי-הלמן

מומלץ לקרוא ישירות את המאמר פורץ הדרך בו הוצגה השיטה:

Diffie, Whitfield, and Martin E. Hellman. "New directions in cryptography."

• למדנו שבעזרת RSA ניתן להעביר פיסת מידע באופן בטוח בערוץ פומבי, ולרוב נרצה להעביר מפתח סודי לצורך הצפנה סימטרית.
• אלגוריתם דיפי-הלמן הוא שיטה לתיאום מפתח סודי בלבד ולא להעברת מידע.

• אליס ובוב מתאמים מספר ראשוני גדול [math]\displaystyle{ p }[/math] שאינו סודי כמובן.
• כמו כן הם מתאמים יוצר [math]\displaystyle{ g }[/math] של [math]\displaystyle{ U_p }[/math] (כלומר [math]\displaystyle{ U_p=\lt g\gt }[/math]), או לפחות איבר מסדר מאד גדול (בהמשך יש הסבר כיצד אפשר לעשות זאת).
• כעת אליס בוחרת מספר אקראי סודי [math]\displaystyle{ a\leq p-1 }[/math] ושולחת לבוב את [math]\displaystyle{ g^a \mod p }[/math].
• בוב בוחר מספר אקראי סודי [math]\displaystyle{ b\leq p-1 }[/math] ושולח לאליס את [math]\displaystyle{ g^b \mod p }[/math].

• כעת אליס ובוב שניהם יכולים לחשב בקלות את הסוד המשותף [math]\displaystyle{ g^{ab} }[/math].

• על מנת לשבור את ההצפנה צריך לחשב את [math]\displaystyle{ a }[/math] בהנתן [math]\displaystyle{ g^a \mod p }[/math], זו בעיית הלוגריתם הדיסקרטי שנחשבת לקשה.
• אם [math]\displaystyle{ g }[/math] מסדר נמוך חישוב כל החזקות האפשריות שלו הוא קל.

• גישה פרקטית למשל:
  • נבחר את p להיות מספר ראשוני "בטוח", כלומר [math]\displaystyle{ p=2q+1 }[/math] כאשר [math]\displaystyle{ q }[/math] ראשוני.
  • כעת ב[math]\displaystyle{ |U_p|=2q }[/math] ולכן הסדר של כל איבר ב[math]\displaystyle{ U_p }[/math] הוא אחד מבין [math]\displaystyle{ 1,2,q,2q }[/math].
  • נגריל איבר [math]\displaystyle{ g\neq \pm 1 }[/math] (לכן [math]\displaystyle{ g^2\not\equiv 1 \mod p }[/math]) וגם [math]\displaystyle{ g^q\not\equiv 1 \mod p }[/math].
  • האיבר שבחרנו הוא יוצר.

חתימה

• פונקציות גיבוב (hash) - מעבירות קלט בגודל אקראי לקלט באורך קבוע.
• התנגשות היא מצב בו שני קלטים מובילים לאותו ערך מגובב. לפי שובך היונים התנגשויות קיימות, אך בפונקציות גיבוב "טובות" הסיכוי לכך נמוך מאד.

• סיפרנו על אליס שייצרה מפתח פומבי [math]\displaystyle{ (n,e) }[/math], ושמרה לעצמה את הערכים הסודיים [math]\displaystyle{ m,d }[/math]
• כעת אליס רוצה להבטיח את זהותה ואת אמינות המידע, היא מעבירה את המידע שלה דרך פונקצית גיבוב ומקבלת את הערך המגובב [math]\displaystyle{ a }[/math].
• אליס מחשבת את [math]\displaystyle{ y=a^{d} \mod n }[/math] ושולחת אותו בנוסף למידע.
• אפילו בהנתן [math]\displaystyle{ a }[/math] לא ניתן לחשב את [math]\displaystyle{ d }[/math] (זו בעיית הלוגריתם הדיסקרטי).
• אף אחד אחר לא יכול לחשב את y כיוון ש [math]\displaystyle{ d }[/math] סודי.

• כעת בוב שרוצה לוודא את אמינות המידע מחשב את [math]\displaystyle{ a=y^{e} \mod n }[/math] ומוודא כי המידע שהוא קיבל הוא המידע שאליס התכוונה לשלוח עד כדי המקרה הבלתי סביר של התנגשות.
• אף אחד אחר לא יכל ליצור את הוכחת אמינות המידע הזו פרט לאליס.

• שימו לב שעל מנת למנוע תקיפת 'אדם באמצע' באמצעות חתימה המפתחות הפומביים צריכים להיות מאומתים על פני ערוץ מאובטח (מקודדים בתוך הדפדפן למשל).

חישוב חזקה

• שיטת הריבועים החוזרים לחישוב חזקה.
• לדוגמא, אנו מעוניינים לחשב את [math]\displaystyle{ x^{41} \mod n }[/math] במעט פעולות
  • [math]\displaystyle{ 41=2^5+2^3+1 }[/math]
  • [math]\displaystyle{ x^{41}=x^{2^5}\cdot x^{2^3}\cdot x }[/math]
  • [math]\displaystyle{ 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 מהספר

• תהי חבורה G ותהי תת חבורה N. תת החבורה N נקראת נורמלית אם לכל [math]\displaystyle{ a\in G }[/math] מתקיים כי [math]\displaystyle{ aN=Na }[/math].
• ברור שבחבורה אבלית כל חבורה היא תת חבורה נורמלית.
• דוגמא:
  • נביט בחבורה הסימטרית [math]\displaystyle{ G=S_3 }[/math] ובתת החבורה [math]\displaystyle{ H=\lt (1\ 2)\gt =\{(1),(1\ 2)\} }[/math].
  • אזי [math]\displaystyle{ (1\ 3)H=\{(1\ 3), (3\ 1\ 2)\} }[/math] אך [math]\displaystyle{ H(1\ 3)=\{(1\ 3),(2\ 1\ 3)\} }[/math] וקל לראות כי [math]\displaystyle{ (1\ 3)H\neq H(1\ 3) }[/math].
  • אזי N תת חבורה לא נורמלית!
• דוגמא נוספת:
  • נביט בחבורה הסימטרית [math]\displaystyle{ G=S_3 }[/math] ובתת החבורה [math]\displaystyle{ N=\lt (1\ 2\ 3)\gt }[/math] שהיא תת החבורה של כל התמורות הזוגיות במקרה זה.
  • קל לוודא שלכל תמורה זוגית מתקיים [math]\displaystyle{ fN=Nf=N }[/math] ולכל תמורה אי-זוגית מתקיים [math]\displaystyle{ fN=Nf }[/math] שווה לקבוצת כל התמורות האי-זוגיות.

• טענה תהי N תת חבורה נורמלית אזי [math]\displaystyle{ (aN)(bN)=abN }[/math]
• הוכחה - הכלה דו כיוונית:
  • יהי [math]\displaystyle{ anbk\in (aN)(bN) }[/math] כיוון ש [math]\displaystyle{ bN=Nb }[/math] אזי [math]\displaystyle{ anbk=abmk\in abN }[/math].
  • יהי [math]\displaystyle{ abn\in abN }[/math] אזי [math]\displaystyle{ aebn\in (aN)(bN) }[/math].

• תהיינה G חבורה וN תת חבורה נורמלית, אזי [math]\displaystyle{ G/N=\{aN|a\in G\} }[/math] היא חבורה.

• יהי הומומורפיזם בין חבורות [math]\displaystyle{ f:G\to H }[/math]. נגדיר את הגרעין [math]\displaystyle{ \ker(f)=\{a\in G|f(a)=e_H\} }[/math].
• נסמן [math]\displaystyle{ K=\ker(f) }[/math]
• טענה:
  • לכל [math]\displaystyle{ a\in G }[/math] מתקיים כי [math]\displaystyle{ aK=\left\{b\in G|f(a)=f(b)\right\} }[/math]
• הוכחה:
  • בכיוון ראשון, יהי [math]\displaystyle{ ak\in aK }[/math] אזי [math]\displaystyle{ f(ak)=f(a)f(k)=f(a)e_H=f(a) }[/math]
  • בכיוון שני, יהי [math]\displaystyle{ b\in G }[/math] כך ש [math]\displaystyle{ f(a)=f(b) }[/math] אזי [math]\displaystyle{ f(a^{-1}b)=e_H }[/math] ולכן [math]\displaystyle{ a^{-1}b=k\in K }[/math] ולכן [math]\displaystyle{ b=ak\in aK }[/math]

• כיוון שהוכחה דומה עובדת מהצד השני, נובע כי [math]\displaystyle{ aK=Ka }[/math] ולכן הגרעין הינו תת חבורה נורמלית.

הרצאה 9 משפט האיזומורפיזם, מבוא לקידוד; פרק 11 מהספר

• משפט האיזומורפיזם הראשון. יהי [math]\displaystyle{ \varphi:G\to H }[/math] הומומורפיזם בין חבורות. אזי [math]\displaystyle{ G/\ker(\varphi)\cong im(\varphi) }[/math]
• הוכחה:
  • לצורך הנוחות נסמן [math]\displaystyle{ K=\ker(\varphi) }[/math] ו[math]\displaystyle{ M=im(\varphi) }[/math].
  • עלינו להראות שקיים איזומורפיזם (כלומר הומומורפיזם חח"ע ועל) [math]\displaystyle{ f:G/K\to M }[/math].
  • לכל [math]\displaystyle{ aK\in G/K }[/math] נגדיר [math]\displaystyle{ f(aK)=\varphi(a) }[/math].
  • ראשית, עלינו להוכיח כי מדובר בפונקציה מוגדרת היטב. כלומר, בהנתן [math]\displaystyle{ a,b\in G }[/math], אם [math]\displaystyle{ aK=bK }[/math] עלינו להוכיח כי [math]\displaystyle{ f(aK)=f(bK) }[/math].
    • [math]\displaystyle{ a=ae\in aK }[/math] ולכן [math]\displaystyle{ a\in bK }[/math]. כלומר קיים [math]\displaystyle{ k\in K }[/math] כך ש [math]\displaystyle{ a=bk }[/math].
    • [math]\displaystyle{ \varphi(a)=\varphi(bk)=\varphi(b)\varphi(k)=\varphi(b) }[/math].
    • [math]\displaystyle{ f(aK)=\varphi(a)=\varphi(b)=f(bK) }[/math].
  • כעת, עלינו להוכיח ש[math]\displaystyle{ f }[/math] הינו הומומורפיזם.
    • [math]\displaystyle{ f\left((aK)(bK)\right)=f(abK)=\varphi(ab)=\varphi(a)\varphi(b)=f(aK)f(bK) }[/math]
  • עכשיו נוכיח ש[math]\displaystyle{ f }[/math] על.
    • לכל איבר בתמונה [math]\displaystyle{ h\in M }[/math] קיים מקור [math]\displaystyle{ g\in G }[/math]. לכן [math]\displaystyle{ f(gK)=\varphi(g)=h }[/math].
  • ולבסוף, נוכיח ש[math]\displaystyle{ f }[/math] חח"ע.
    • יהיו [math]\displaystyle{ aK,bK\in G/K }[/math] כך ש [math]\displaystyle{ f(aK)=f(bK) }[/math] עלינו להוכיח כי [math]\displaystyle{ aK=bK }[/math].
    • נתון [math]\displaystyle{ \varphi(a)=\varphi(b) }[/math] צ"ל [math]\displaystyle{ aK=bK }[/math]. שימו לב שלא צריך להוכיח כי [math]\displaystyle{ a=b }[/math]; אכן [math]\displaystyle{ \varphi }[/math] לא חייב להיות חח"ע.
    • נראה הכלה בכיוון אחד, הכיוון השני דומה.
    • יהי [math]\displaystyle{ ak\in aK }[/math] צ"ל [math]\displaystyle{ ak\in bK }[/math].
    • קל לראות ש [math]\displaystyle{ ak=bb^{-1}ak }[/math], עלינו להוכיח כי [math]\displaystyle{ b^{-1}ak\in K }[/math].
    • אכן [math]\displaystyle{ \varphi(b^{-1}ak)=\left(\varphi(b)\right)^{-1}\varphi(a)\varphi(k)=\left(\varphi(a)\right)^{-1}\varphi(a)=e_H }[/math]

• דוגמא.
• נגדיר את הפונקציה [math]\displaystyle{ \varphi:\mathbb{Z}\to \mathbb{Z}_n }[/math] על ידי [math]\displaystyle{ \varphi(a)=a\mod n }[/math] (השארית של החלוקה של a בn).
• נוכיח שמדובר בהומומורפיזם.
  • יהיו [math]\displaystyle{ a,b\in\mathbb{Z} }[/math] לפי ההגדרה [math]\displaystyle{ \varphi(a+b)= a+b \mod n }[/math].
  • נשים לב כי [math]\displaystyle{ a=\varphi(a)+kn, b=\varphi(b)+mn }[/math].
  • לכן [math]\displaystyle{ a+b\equiv \varphi(a)+\varphi(b) \mod n }[/math].
  • סה"כ [math]\displaystyle{ \varphi(a+b)=\varphi(a)+\varphi(b) }[/math] כיוון שהם שקולים מודולו n, ואנו עוסקים בחבורה [math]\displaystyle{ \mathbb{Z}_n }[/math].
• כעת מתקיים כי [math]\displaystyle{ \ker\varphi=n\mathbb{Z}=\{na|a\in\mathbb{Z}\} }[/math].
• לכן [math]\displaystyle{ \mathbb{Z}/n\mathbb{Z}\cong \mathbb{Z}_n }[/math]

• שאלה - האם בחיבור [math]\displaystyle{ 1+7+5+8 }[/math] ב[math]\displaystyle{ \mathbb{Z}_9 }[/math] חשוב לבצע את פעולת המודולו בכל חיבור, או שמותר בסוף?
• [math]\displaystyle{ \mathbb{Z}_9 }[/math] איזומורפית לחבורה [math]\displaystyle{ \{0+9\mathbb{Z},...,8+9\mathbb{Z}\} }[/math]
• נביט ב [math]\displaystyle{ (1+9\mathbb{Z})+(7+9\mathbb{Z})+(5+9\mathbb{Z})+(8+9\mathbb{Z}) }[/math]
• הוכחנו כי [math]\displaystyle{ (aN)(bN)=abN }[/math]. לכן [math]\displaystyle{ (1+9\mathbb{Z})+(7+9\mathbb{Z})+(5+9\mathbb{Z})+(8+9\mathbb{Z})=21+9\mathbb{Z} }[/math].
• כיוון ש [math]\displaystyle{ \varphi(21)=\varphi(3) }[/math], נובע לפי הוכחת משפט האיזומורפיזם הראשון כי [math]\displaystyle{ 21+9\mathbb{Z}=3+9\mathbb{Z} }[/math], כלומר אכן מותר לעשות את המודולו בסוף.

מבוא לקידוד

• קוד ISBN בעל 10 ספרות, כאשר הספרה האחרונה היא ספרת ביקורת.
• הספרות שייכות לחבורה [math]\displaystyle{ \mathbb{Z}_{11} }[/math], כאשר 9 הספרות הראשונות הן 0-9 והאחרונה יכולה להיות גם X.
• קוד תקין מקיים את הנוסחא [math]\displaystyle{ 10x_1+9x_2+...+x_{10}=0 }[/math] (שימו לב שמדובר בפעולות מודולו 11).
• לכן חישוב ספרת הביקורת הוא [math]\displaystyle{ x_{10}=-\left(10x_1+...+2x_9\right) }[/math].
• אם ספרה אחת בלבד מהקוד תשתנה בטעות, הקוד בוודאות לא יהיה תקין.
  • אם נחליף את [math]\displaystyle{ x_i }[/math] בספרה [math]\displaystyle{ y_i }[/math] על מנת שהקוד החדש יהיה תקין צריך ש [math]\displaystyle{ a_i(y_i-x_i)=0 }[/math], אבל [math]\displaystyle{ a_i\neq 0 }[/math] ו[math]\displaystyle{ \mathbb{Z}_{11} }[/math] הוא שדה.
• אם נחליף במיקום של זוג ספרות כלשהן נקבל קוד בלתי תקין.
  • [math]\displaystyle{ 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 מהספר

• תעודת זהות בישראל.
• עבור ספרת הביקורת של תעודת הזהות אנו לא מרשים שימוש בספרה X ולכן עובדים ב[math]\displaystyle{ \mathbb{Z}_{10} }[/math].
• הבעייה - זה אינו שדה ויש מחלקי אפס. למשל [math]\displaystyle{ 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]\displaystyle{ \{0,1,2,3,4\} }[/math] נשלחות לספרות [math]\displaystyle{ \{0,2,4,6,8\} }[/math] בהתאמה.
  • הספרות [math]\displaystyle{ \{5,6,7,8,9\} }[/math] נשלחות לספרות [math]\displaystyle{ \{1,3,5,7,9\} }[/math] בהתאמה.
  • הספרות [math]\displaystyle{ \{5,6,7,8,9\} }[/math] כפול 2 שוות ל [math]\displaystyle{ 10+x }[/math] ונשלחות ל[math]\displaystyle{ 1+x }[/math].
  • נשים לב כי פעמיים הספרה שקול ל [math]\displaystyle{ x }[/math] מודולו 10.
  • סה"כ הגדרנו את הפונקציה הבאה על הספרות [math]\displaystyle{ f(a)=\begin{cases}2a & a\leq 4 \\ 2a+1 & a\geq 5\end{cases} }[/math].
• שימו לב שכפל רגיל ב2 לא היה עובד, כיוון ש[math]\displaystyle{ 2\cdot 5 = 2\cdot 0 }[/math].

• מדוע אם כך בחרנו דווקא במשקל 2 שאינו זר ל 10 (ולכן אינו הפיך)?
  • ההפיכים מודולו 10 הם אי זוגיים.
  • ההפרש בין כל שניים מהם הוא זוגי, ולכן כל חילוף של שתי ספרות בהפרש 5 לא היה מתגלה.
  • לדוגמא נניח כי המשקלים הם 1 ו3.
  • [math]\displaystyle{ 1\cdot a+3\cdot (a+5)=a+3a+15=1\cdot(a+5)+3\cdot a }[/math].

• נניח שספרות תעודת הזהות הן [math]\displaystyle{ x_9,...,x_1 }[/math] כאשר [math]\displaystyle{ x_1 }[/math] היא ספרת הביקורת והימנית ביותר.
• לפי החישוב לעיל ספרת הביקורת נבחרה כך ש [math]\displaystyle{ x_9+f(x_8)+x_7+...+f(x_2)+x_1=0 }[/math].
• נעביר אגף ונקבל נוסחא לספרת הביקורת.

• קל לראות שתעודת זהות שנפלה בה טעות בספרה אחת אינה תקינה יותר.
  • אם הספרה השונה היא במקום אי זוגי אז [math]\displaystyle{ 1\cdot x_i\neq 1\cdot yi }[/math].
  • אם הספרה השונה היא במקום אי זוגי אז [math]\displaystyle{ f(x_i)\neq f(y_i) }[/math] כיוון ש[math]\displaystyle{ f }[/math] חח"ע.
• אם החלפנו את הספרות 0,9 במקומות סמוכים לא נזהה את השגיאה.
  • אכן, [math]\displaystyle{ 1\cdot 0 + f(9) = 9 = 1\cdot 9 + f(0) }[/math].
• אם החלפנו שתי ספרות שונות במקומות סמוכים שאינן הזוג 0,9 אז נזהה את השגיאה.
  • אם שתי הספרות קטנות או שוות ל4, נקבל [math]\displaystyle{ x_i+2x_j-x_j-2x_i=x_j-x_i\neq 0 }[/math].
  • אם שתי הספרות גדולות או שוות ל5 נקבל [math]\displaystyle{ x_i+2x_j+1-x_j-2x_i-1=x_j-x_i\neq 0 }[/math].
  • אם [math]\displaystyle{ 0\leq x_i\leq 4 }[/math] אבל [math]\displaystyle{ 5\leq x_j\leq 9 }[/math] נקבל [math]\displaystyle{ x_i+2x_j+1-x_j-2x_i=x_j-x_i+1 }[/math].
  • הדרך היחידה ש[math]\displaystyle{ x_j-x_i+1=0 }[/math]היא אם [math]\displaystyle{ x_j-x_i=9 }[/math] וזה בדיוק הזוג 0,9.

קוד לינארי

• המידע שאנו מעוניים לשלוח הוא וקטור של ביטים [math]\displaystyle{ \mathbb{Z}_2^k }[/math].
• נכפיל את המידע במטריצה הבינארית [math]\displaystyle{ G=\begin{pmatrix} I_k \\ A\end{pmatrix} }[/math] ונקבל קוד ב[math]\displaystyle{ \mathbb{Z}_2^n }[/math].
• דוגמא
  • נביט במטריצה [math]\displaystyle{ G=\begin{pmatrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1\\ 1 & 1 & 1\end{pmatrix} }[/math].
  • כפל במטריצה זו מוסיף למידע באורך 3 ביט יתירות הבודק זוגיות (parity bit).

• עבור [math]\displaystyle{ G=\begin{pmatrix} I_k \\ A\end{pmatrix} }[/math] נגדיר את המטריצה [math]\displaystyle{ H=\begin{pmatrix}A & I_{n-k}\end{pmatrix} }[/math].
• טענה:
• לכל וקטור [math]\displaystyle{ Hv=0 }[/math] אם ורק אם [math]\displaystyle{ v }[/math] הוא מהצורה [math]\displaystyle{ v=Gx }[/math].
  • הוכחה:
  • כיוון ראשון:
    • נוכיח ראשית ש[math]\displaystyle{ HG=0 }[/math], ולכן ברור שאם [math]\displaystyle{ v=Gx }[/math] אזי [math]\displaystyle{ Hv=0 }[/math].
    • [math]\displaystyle{ HG=\begin{pmatrix}A & I_{n-k}\end{pmatrix}\begin{pmatrix}I_k \\ A\end{pmatrix}=A+A=0 }[/math] (זכרו שאנו מעל השדה [math]\displaystyle{ \mathbb{Z}_2 }[/math]).
  • בכיוון ההפוך:
    • נניח כי [math]\displaystyle{ Hv=0 }[/math] ונסמן [math]\displaystyle{ v=\begin{pmatrix}x\\u\end{pmatrix} }[/math] כאשר [math]\displaystyle{ x\in\mathbb{Z}_2^k }[/math].
    • נוכיח כי [math]\displaystyle{ Gx=v }[/math].
    • נסמן [math]\displaystyle{ Gx=\begin{pmatrix}x\\u'\end{pmatrix} }[/math], צריך להוכיח כי [math]\displaystyle{ u=u' }[/math].
    • נתון כי [math]\displaystyle{ Hv=0 }[/math], ומכיוון קודם ידוע כי [math]\displaystyle{ HGx=0 }[/math] ולכן ביחד [math]\displaystyle{ H(Gx-v)=0 }[/math].
    • לכן [math]\displaystyle{ 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]\displaystyle{ v }[/math] הינו תקין אם ורק אם [math]\displaystyle{ Hv=0 }[/math].

• שימו לב כי נובע מההוכחה לעיל שעבור וקטור מידע [math]\displaystyle{ x }[/math] יש בדיוק וקטור יתירות יחיד [math]\displaystyle{ u }[/math] עבורו [math]\displaystyle{ \begin{pmatrix}x\\u\end{pmatrix} }[/math] תקין.
• כלומר, ניתן לזהות כל כמות טעויות המשנה אך ורק את וקטור היתירות.

הרצאה 11 המשך קידוד; פרק 8 מהספר

• עד כה הראנו שיש לנו דרך לקודד מידע ולוודא שהמידע שהגיע הוא קוד תקין.
• השאלה: כיצד שגיאות עשויות להשפיע על הקוד? כמה שגיאות יכולות להעביר אותנו ממילה חוקית אחת לאחרת?
• מרחק המינג- המרחק בין שני וקטורים ב[math]\displaystyle{ \mathbb{Z}_2^n }[/math] הוא כמות העמודות בהן הם נבדלים.
  • דוגמא: [math]\displaystyle{ d((1,0,1,0),(0,1,1,0))=2 }[/math].

• נסמן ב[math]\displaystyle{ d_{min} }[/math] את המרחק הקטן ביותר בין שתי מילים חוקיות כלשהן [math]\displaystyle{ Gx_1,Gx_2 }[/math].
• טענה: אם [math]\displaystyle{ d_{min}\geq 2n+1 }[/math] אז הקוד מסוגל לזהות עד [math]\displaystyle{ 2n }[/math] שגיאות ולתקן עד [math]\displaystyle{ n }[/math] שגיאות.
• הוכחה:
  • אם כמות השגיאות קטנה או שווה ל[math]\displaystyle{ 2n }[/math] המילה שהתקבלה בוודאות אינה חוקית, כיוון שהמרחק המינימלי בין שתי מילים חוקיות גדול או שווה ל[math]\displaystyle{ 2n+1 }[/math].
  • אם כמות השגיאות קטנה או שווה ל[math]\displaystyle{ n }[/math] יש בדיוק מילה חוקית אחת שיכולה להיות המקור.
  • אחרת, ניתן להגיע ע"י n שגיאות משתי מילים חוקיות למילה שקיבלנו, כלומר המרחק בין שתי המילים החוקיות קטן או שווה ל[math]\displaystyle{ 2n }[/math], בסתירה.

• דוגמא: בקוד ביט parity מתקיים כי [math]\displaystyle{ d_{min}=2 }[/math] והקוד יכול לזהות שגיאה אחת ולא לתקן בכלל.

• טענה:
• הקוד מסוגל לזהות לפחות שגיאה אחת אם ורק אם ב[math]\displaystyle{ H }[/math] אין עמודת אפסים.
  • הוכחה:
  • תהי מילה חוקית [math]\displaystyle{ v }[/math] ונוסיף לה שגיאה אחת בדיוק [math]\displaystyle{ v+e_i }[/math].
  • אזי [math]\displaystyle{ H(v+e_i)=Hv+He_i=0+C_i(H) }[/math].

• טענה:
• [math]\displaystyle{ d_{min}\geq 3 }[/math] אם ורק אם ב[math]\displaystyle{ H }[/math] אין עמודת אפסים וגם אין שתי עמודות זהות.
• במקרה זה ניתן לזהות לפחות שתי שגיאות, ולתקן לפחות שגיאה אחת.
  • הוכחה:
  • תהי מילה חוקית [math]\displaystyle{ v }[/math] ונוסיף לה שתי שגיאות [math]\displaystyle{ v+e_i+e_j }[/math].
  • אזי [math]\displaystyle{ H(v+e_i+e_j)=C_i(H)+C_j(H) }[/math].
  • זה שווה אפס (כלומר המילה החדשה חוקית) אם ורק אם [math]\displaystyle{ C_i(H)=C_j(H) }[/math].

• הערה:
• נניח שהוספנו [math]\displaystyle{ n-k }[/math] ביטים למידע, זה משאיר ל[math]\displaystyle{ A }[/math] כמות של [math]\displaystyle{ 2^{n-k}-(n-k)-1 }[/math] עמודות שיכולות להיות שונות מאפס, ושונות מהעמודות של [math]\displaystyle{ I_{n-k} }[/math].
• כלומר על מנת לתקן שגיאה אחת, כמות הביטים שעלינו להוסיף לוגריתמית ביחס לכמות המידע.

• דוגמא (קוד המינג)
• [math]\displaystyle{ 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]\displaystyle{ d_{min}\leq 3 }[/math].
• מצד שני, כיוון שאין ב[math]\displaystyle{ H }[/math] שתי עמודות זהות [math]\displaystyle{ d_{min}\geq 3 }[/math].
• ביחד [math]\displaystyle{ d_{min}= 3 }[/math].

• מציאת שגיאה, בהנתן שהתרחשה בדיוק שגיאה אחת:
• נניח שהמילה שנשלחה היא [math]\displaystyle{ v }[/math] והמילה שהתקבלה היא [math]\displaystyle{ v+e_i }[/math].
• לכן [math]\displaystyle{ H(v+e_i)=C_i(H) }[/math].
• כלומר מיקום העמודה במטריצה [math]\displaystyle{ H }[/math] הוא מיקום הטעות.

• דוגמא:
• [math]\displaystyle{ 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]\displaystyle{ u=\begin{pmatrix}1\\0\\0\\1\\0\\0\\1\end{pmatrix} }[/math].
• נחשב [math]\displaystyle{ Hu=\begin{pmatrix}1\\0\\1\end{pmatrix} }[/math].
• כך אנו יודעים שהטעות הייתה בביט השני.

checksum בפרוטוקולי IP, TCP, UDP.

הרצאה 12 חוג הפולינומים; פרקים 16,17 מהספר

• תזכורת: חוג הוא קבוצה [math]\displaystyle{ R }[/math] עם פעולות חיבור וכפל, כך שהוא חבורה חילופית ביחד לחיבור, מקיים אסוציאטיביות בכפל, מכיל איבר יחידה ואת חוק הפילוג.

חוג הפולינומים

• יהי [math]\displaystyle{ \mathbb{F} }[/math] שדה, אזי [math]\displaystyle{ \mathbb{F}[x] }[/math] הוא חוג הפולינומים עם פעולות כפל וחיבור רגילות.
  • כלומר [math]\displaystyle{ \mathbb{F}[x]=\{a_nx^n+...+a_1x+a_0|n\in\mathbb{N},a_i\in\mathbb{F}\} }[/math].
• עבור פולינום [math]\displaystyle{ a_nx^n+...+a_1x+a_0 }[/math] כאשר [math]\displaystyle{ a_n\neq 0 }[/math] אומרים שהדרגה שלו היא [math]\displaystyle{ n }[/math].
• עבור פולינום האפס אפשר להגיד שדרגתו היא [math]\displaystyle{ -1 }[/math].

• טענה (חלוקה עם שארית): יהיו שני פולינומים [math]\displaystyle{ f(x),g(x)\in\mathbb{F}[x] }[/math] כך ש[math]\displaystyle{ g(x) }[/math] אינו פולינום האפס, אזי קיימים פולינומים יחידים [math]\displaystyle{ q(x),r(x) }[/math] כך ש:
  • [math]\displaystyle{ f(x)=q(x)g(x)+r(x) }[/math].
  • [math]\displaystyle{ \deg(r(x))\lt \deg(g(x)) }[/math].
• הוכחה:
• קיום:
  • יהי [math]\displaystyle{ g(x) }[/math] כזה.
  • אם [math]\displaystyle{ \deg(f)\lt \deg(g) }[/math] אזי [math]\displaystyle{ f=0\cdot g + f }[/math].
  • אם [math]\displaystyle{ \deg(f)\geq\deg(g) }[/math] נוכיח באינדוקציה על הדרגה של [math]\displaystyle{ f }[/math].
  • נסמן [math]\displaystyle{ f(x)=a_nx^n+...+a_0 }[/math], [math]\displaystyle{ g(x)=b_mx^m+...+b_0 }[/math] כאשר נתון [math]\displaystyle{ n\geq m }[/math].
  • הפולינום [math]\displaystyle{ f(x)-\frac{a_n}{b_m}x^{n-m}g(x) }[/math] הוא מדרגה קטנה ממש מ[math]\displaystyle{ n }[/math] ולכן מקיים את הטענה לפי הנחת האינדוקציה.
  • לכן [math]\displaystyle{ f(x)-\frac{a_n}{b_m}x^{n-m}g(x)=q(x)g(x)+r(x) }[/math].
  • לכן [math]\displaystyle{ f(x)=(\frac{a_n}{b_m}x^{n-m}+q(x))g(x)+r(x) }[/math].
• יחידות:
  • נניח [math]\displaystyle{ f(x)=q_1(x)g(x)+r_1(x)=q_2(x)g(x)+r_2(x) }[/math].
  • לכן [math]\displaystyle{ (q_1(x)-q_2(x))g(x)=r_1(x)-r_2(x) }[/math].
  • אבל [math]\displaystyle{ \deg(r_1(x)-r_2(x))\lt \deg(g(x)) }[/math] ולכן [math]\displaystyle{ q_1(x)-q_2(x)=0 }[/math] ולכן גם [math]\displaystyle{ r_1(x)-r_2(x)=0 }[/math].

• מסקנה: עבור פולינום [math]\displaystyle{ f(x) }[/math] ועבור נקודה [math]\displaystyle{ a\in\mathbb{F} }[/math] מתקיים כי [math]\displaystyle{ f(a)=0 }[/math] אם"ם קיים פולינום [math]\displaystyle{ q(x) }[/math] כך ש [math]\displaystyle{ f(x)=q(x)(x-a) }[/math].
• במילים: a הינו שורש של הפולינום f אם"ם הפולינום f מתחלק בפולינום x-a.
• הוכחה:
  • לפי משפט החלוקה עם שארית קיימים פולינומים [math]\displaystyle{ q(x),r(x) }[/math] כך ש:
    • [math]\displaystyle{ f(x)=q(x)(x-a)+r(x) }[/math].
    • [math]\displaystyle{ \deg(r(x))\lt \deg(x-a)=1 }[/math], כלומר [math]\displaystyle{ r(x)=r\in\mathbb{F} }[/math] הוא קבוע.
  • נציב [math]\displaystyle{ a }[/math] ונקבל [math]\displaystyle{ f(a)=r }[/math].
  • לכן [math]\displaystyle{ f(x)=q(x)(x-a) }[/math] אם ורק אם [math]\displaystyle{ f(a)=0 }[/math].

קודים פולינומיים

• כעת נביט בפולינומים מעל השדה הבינארי [math]\displaystyle{ \mathbb{Z}_2[x] }[/math].
• כל פולינום מדרגה n מתאים לוקטור המקדמים ב[math]\displaystyle{ \mathbb{Z}_2^{n+1} }[/math].
• למשל, וקטור המידע [math]\displaystyle{ 10110 }[/math] מתאים לפולינום [math]\displaystyle{ x^4+x^2+x }[/math].

• נקבע פולינום [math]\displaystyle{ g(x)\in\mathbb{Z}_2[x] }[/math] כלשהו מדרגה m.
• עבור מידע [math]\displaystyle{ f(x) }[/math] נבצע חלוקה עם שארית של [math]\displaystyle{ x^m\cdot f(x) }[/math] ב[math]\displaystyle{ g(x) }[/math]
• [math]\displaystyle{ x^m\cdot f(x) =q(x)g(x)+r(x) }[/math].
• המילה שנשלח היא [math]\displaystyle{ x^m\cdot f(x) + r(x) }[/math] (שימו לב כי [math]\displaystyle{ r(x)=-r(x) }[/math]).
• המילה תקינה אם ורק אם היא מתחלקת ב[math]\displaystyle{ g(x) }[/math].
• זהו קוד לינארי:
  • אם [math]\displaystyle{ f(x),h(x) }[/math] מתאימים לוקטורי מידע, [math]\displaystyle{ f(x)=q_1(x)g(x)+r_1(x) }[/math] ו[math]\displaystyle{ h(x)=q_2(x)g(x)+r_2(x) }[/math] אז השארית של [math]\displaystyle{ f(x)+h(x) }[/math] היא [math]\displaystyle{ r_1(x)+r_2(x) }[/math].
• קוד זה מוסיף m ביטים של יתירות למידע.

• דוגמא:
• נבחר את הפולינום [math]\displaystyle{ g(x)=x^3+x+1 }[/math] (מוסיף 3 ביטי יתירות).
  • נקודד מידע:
    • נניח כי המידע שלנו הוא [math]\displaystyle{ 1010 }[/math] כלומר הפולינום [math]\displaystyle{ f(x)=x^3+x }[/math].
    • לכן עלינו לחלק את הפולינום [math]\displaystyle{ x^3\cdot f(x) =x^6+x^4 }[/math] בפולינום [math]\displaystyle{ g(x)=x^3+x+1 }[/math].
    • לאחר אלגוריתם חלוקה עם שארית נקבל [math]\displaystyle{ x^6+x^4=(x^3+1)(x^3+x+1)+x+1 }[/math].
    • לכן סה"כ המידע שנשלח הוא [math]\displaystyle{ x^3\cdot f(x) + r(x)=x^6+x^4+x+1 }[/math] שזה בעצם [math]\displaystyle{ 1010011 }[/math].
  • נבדוק תקינות מידע:
    • האם המידע [math]\displaystyle{ 1101101 }[/math] תקין?
    • זה בעצם הפולינום [math]\displaystyle{ x^6+x^5+x^3+x^2+1 }[/math], זה קוד תקין אם"ם הוא מתחלק ב[math]\displaystyle{ g(x) }[/math].
    • נבצע חלוקה עם שארית ונקבל שארית [math]\displaystyle{ x^2 }[/math], לכן הקוד אינו תקין.

הרצאה 13 קודים ציקליים; פרק 22 מהספר

קידוד פולינומי ציקלי

• עבור הקידוד הציקלי נקבע את הפרמטרים הבאים:
  • יהי k אורך המידע, כלומר נקודד פולינומים עד דרגה [math]\displaystyle{ k-1 }[/math] בלבד.
  • יהי g פולינום מדרגה m, לפי נקודד קידוד פולינומי.
  • נסמן את אורך המילה המקודדת ב[math]\displaystyle{ n=k+m }[/math].
  • מילה היא חוקית אם ורק אם היא מהצורה [math]\displaystyle{ h(x)g(x) }[/math] כאשר [math]\displaystyle{ deg(h(x))\lt k }[/math]

• קוד נקרא ציקלי אם לכל מילה חוקית [math]\displaystyle{ (a_{n-1}\ a_{n-2}\ \cdots\ a_1\ a_0) }[/math] גם ההזזה הציקלית [math]\displaystyle{ (a_{n-2}\ a_{n-3}\ \cdots\ a_0\ a_{n-1}) }[/math] היא מילה חוקית.

• נתאר את ההזה הציקלית באמצעות פעולה אלגברית.
  • יהי [math]\displaystyle{ f(x)=a_{n-1}x^{n-1}+...+a_0 }[/math]
  • אזי [math]\displaystyle{ x\cdot f(x) \equiv a_{n-2}x^{n-1}+...+a_0x+a_{n-1} \mod x^n-1 }[/math]
  • כלומר ההזזה הציקלית של [math]\displaystyle{ f(x) }[/math] היא השארית של [math]\displaystyle{ x\cdot f(x) }[/math] בחלוקה ב[math]\displaystyle{ x^n-1 }[/math].
  • הוכחה:
    • אכן [math]\displaystyle{ 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]\displaystyle{ f(x)=a_{n-1}x^{n-1}+...+a_0 }[/math]
  • אם [math]\displaystyle{ a_n=0 }[/math] אזי ההזזה הציקלית היא [math]\displaystyle{ x\cdot f(x) }[/math]
  • אם [math]\displaystyle{ a_n=1 }[/math] אזי ההזה הציקלית היא [math]\displaystyle{ x\cdot f(x) +x^n +1 }[/math]
    • (מכבים את הביט האחרון, ומוסיפים ביט ראשון)

• משפט: הפולינום [math]\displaystyle{ g(x) }[/math] מחלק את [math]\displaystyle{ x^n+1 }[/math] אם ורק אם הקוד הפולינומי הינו ציקלי.
• שימו לב: n הוא אורך המילה המקודדת, שכולל הן את המידע והן את היתירות.
  • הוכחה:
  • בכיוון ראשון, נניח כי הקוד הוא ציקלי:
    • [math]\displaystyle{ x^{k-1}g(x) }[/math] היא מילה חוקית
    • כיוון שהקוד ציקלי, גם ההזזה הציקלית [math]\displaystyle{ x\cdot x^{k-1}g(x)+x^n+1 }[/math] חוקית
    • כלומר [math]\displaystyle{ x^k g(x)+x^n+1=h(x)g(x) }[/math]
    • לכן [math]\displaystyle{ x^n+1=(h(x)+x^k) g(x) }[/math], כפי שרצינו.
  • בכיוון שני, נניח כי [math]\displaystyle{ x^n+1=t(x)g(x) }[/math]
    • נשים לב כי [math]\displaystyle{ deg(t(x))=k }[/math]
    • תהי מילה חוקית [math]\displaystyle{ h(x)g(x) }[/math]
    • אם [math]\displaystyle{ deg(h\cdot g)\lt n }[/math] אז ההזזה הציקלית היא [math]\displaystyle{ xh(x)g(x) }[/math] והיא מילה חוקית כי [math]\displaystyle{ deg(xh(x))\lt k }[/math]
    • אחרת, נניח כי [math]\displaystyle{ deg(h\cdot g)=n }[/math] ולכן ההזזה הציקלית היא [math]\displaystyle{ xh(x)g(x)+x^n+1 }[/math]
    • כלומר ההזזה הציקלית היא [math]\displaystyle{ xh(x)g(x)+t(x)g(x)=(xh(x)+t(x))\cdot g(x) }[/math]
    • כיוון ש [math]\displaystyle{ deg(xh(x))=deg(t(x))=k }[/math] נובע כי [math]\displaystyle{ deg(xh(x)+t(x))\lt k }[/math]
    • לכן [math]\displaystyle{ (xh(x)+t(x))\cdot g(x) }[/math] מילה חוקית, כפי שרצינו.

• משפט: קוד פולינומי ציקלי עם פולינום [math]\displaystyle{ g(x) }[/math] מדרגה [math]\displaystyle{ m }[/math] מסוגל לזהות כל כמות של שגיאות, בתנאי שכולן נמצאות בתוך טווח של [math]\displaystyle{ m }[/math] ביטים.
• הוכחה:
  • נניח שקרו טעויות בתוך טווח של [math]\displaystyle{ m }[/math] ביטים.
  • אם המילה החדשה חוקית, גם כל הזזה ציקלית שלה היא חוקית.
  • נזיז את [math]\displaystyle{ m }[/math] הביטים כך שיהיו בקצה הימני במקום של היתירות.
  • כיוון שהיתירות היא יחידה, בוודאות המילה אינה חוקית, סתירה.

• דוגמא:
• [math]\displaystyle{ x^7-1=(1+x)(1+x+x^3)(1+x^2+x^3) }[/math]
• לכן הקוד הנוצר על ידי הפולינום [math]\displaystyle{ g(x)=1+x+x^3 }[/math] עבור וקטורי מידע באורך 4 הוא ציקלי.

• פרוטוקול Ethernet משתמש בתיקון שגיאות ציקלי הנקרא CRC32, ובפרט בפולינום:
• [math]\displaystyle{ 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]\displaystyle{ g(x) }[/math] מחלק את [math]\displaystyle{ x^{2^{32}-1}-1 }[/math], כלומר הוא מתאים לקידוד של עד למעלה מ4 מיליארד ביטים של מידע.