הבדלים בין גרסאות בדף "מבנים אלגבריים למדעי המחשב - ארז שיינר"

גרסה מ־09:17, 24 בנובמבר 2017

תוכן עניינים

1 ספר הקורס
2 נושאי ההרצאות

ספר הקורס

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

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

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

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

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

תזכורת לגבי חבורות, תכונת הצמצום.
$\mathbb{Z},\mathbb{Z}_n,{GL}_n,{SL}_n,S_n$ .
תת חבורות; קווטרניונים, מעגל היחידה ושורשי יחידה, המרוכבים ללא אפס כתת חבורה של מטריצות ממשיות בגודל 2 על 2.
תנאי מקוצר לבדיקת תת חבורה.
כתיב אקספוננט $g^n=g\cdots g$ או כפל $ng=g+\cdots+g$ בהתאם לסימון פעולת החבורה.
סדר של איבר, תת חבורה ציקלית, סדר האיבר הוא גודל החבורה הציקלית.

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

הגדרת סימן של תמורה לפי חלוקת פולינומים, הוכחת כפליות הסימן.
הצגת תמורה כמחזורים זרים, הצגת מחזורים כהרכבה של חילופים, סימן חילוף הוא שלילי.

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

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

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

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

זוג מספרים שלמים $a,b$ נקראים שקולים מודולו n אם קיים שלם $q$ כך ש $a=b+q\cdot n$
חלוקה עם שארית: לכל מספר טבעי a ולכל מספר שלם b קיים זוג שלמים יחיד $q,r$ כך ש $b=q\cdot a+r$ וגם $0\leq r < a$ .
המספר q נקרא מנת החלוקה והמספר r נקרא שארית החלוקה.
$ab$ שקול מודולו n למכפלת השאריות של $a,b$ בחלוקה בn.

לכל שני מספרים טבעיים $k<n$ מתקיים כי $gcd(n,k)=gcd(n-k,k)$
לכל שני מספריים טבעיים $n,k$ קיימים מספרים שלמים $a,b$ כך ש $an+bk=gcd(n,k)$
(הוכחה באינדוקציה על הגודל של n+k. אם n=k סיימנו, אחרת אם $k<n$ אזי $gcd(n,k)=gcd(n-k,k)=a(n-k)+bk=an+(b-a)k$ )

שני מספרים טבעיים n,k נקראים זרים אם $gcd(n,k)=1$
ב $\mathbb{Z}_n$ עם פעולת הכפל מודולו n האיברים ההפיכים הם בדיוק המספרים הזרים ל n.
עבור מספר טבעי $1<n$ קבוצת המספרים הטבעיים הזרים לn וקטנים ממנו מהווה חבורה ביחס לכפל מודולו n, היא נקראית חבורת אוילר ומסומנת $U_n$ .
$\mathbb{Z}_n$ עם פעולות חיבור וכפל מודולו n הוא שדה אם ורק אם n הינו מספר ראשוני.

פונקצית אוילר $\phi(n)$ היא מספר המספרים הטבעיים שקטנים או שווים לn וזרים לו.
משפט אוילר - יהיו שני מספרים טבעיים זרים $a<n$ . אזי $a^{\phi(n)}\equiv 1$ מודולו n.
המשפט הקטן של פרמה - יהי p ראשוני ומספר טבעי $a<p$ אזי $a^{p-1}\equiv 1$ מודולו p.
בפרט, בתנאי המשפט, $a^p\equiv a$ מודולו p.
למעשה התוצאה תקיפה לכל מספר טבעי $a$ , כיוון ש $a^{\phi(n)}=\left(qn+r\right)^{\phi(n)}\equiv r^{\phi(n)}$ , וגם $r$ זר ל $n$ .

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

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

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

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

הצפנות סימטריות וחוזקן, RSA, דיפי-הלמן.

הרצאות 8-9 משפט האיזומורפיזם; פרקים 10,11 מהספר

תת חבורות נורמליות, חבורות מנה, משפט האיזומורפיזם הראשון.

הדגמה על ידי חבורת המודולו, מותר להפעיל את המודולו בכל שלב שנרצה.

הרצאה 10 קידוד; פרק 8 מהספר

קידוד, ספרת ביקורת של תעודת זהות, קוד לינארי, קוד המינג.

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

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

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

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

השדה הבינארי, קודים פולינומיים.

CRC בשימוש פרוטוקול Ethernet.

@@ שורה 73: / שורה 73: @@
+*ההצפנה "המושלמת" - רצף בינארי אקראי באורך המידע המוסכם על שני הצדדים. ללא תלות במידע ובחוקיותו, חיבור בכל ביט (xor) של המידע עם הרצף ייצר תוכן שבו לכל ביט יש סיכוי שווה להיות 0 או אחד.
+*אם הרצף קצר מהמידע וחוזר על עצמו, חיבור שתי חתיכות שנשלחו יאפס את הרצף הסודי וישאיר לנו שתי חתיכות מידע גלוי המחוברות (זה כמעט מידע חשוף).
+*קוד חילוף אותיות - נשבר ע"י חקר סטטיסטיקת שכיחות האותיות. אם המידע עובר תהליך שגורם לו להראות אקראי - עדיף
+*מטא דטא -
+**אם רצף נשלח פעמיים, גם אם אין אנו יודעים מהו, ייתכן שנסיק מההקשר.
+**הזמן שבו נשלח מסר (אמצע הלילה) עלול לעניין אותנו.
+**הזמן שלקח למכונה להצפין את המידע עלול להעיד עליו.
+**עצם העובדה ששני צדדים מסוימים מדברים (רוסיה, ארה"ב) עלול להיות מפליל.
 הצפנות סימטריות וחוזקן, RSA, דיפי-הלמן.

הבדלים בין גרסאות בדף "מבנים אלגבריים למדעי המחשב - ארז שיינר"

גרסה מ־09:17, 24 בנובמבר 2017

תוכן עניינים

ספר הקורס

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

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

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

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

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

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

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

הרצאות 8-9 משפט האיזומורפיזם; פרקים 10,11 מהספר

הרצאה 10 קידוד; פרק 8 מהספר

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

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

תפריט הניווט

כלים אישיים

גרסאות שפה

מרחבי שם

חיפוש

עוד

צפיות

ניווט

כלים