ברוכים הבאים לשיעור המבוא לתורת המספרים הבדידה! יחידה זו מהווה אבן יסוד קריטית בקורס "מתמטיקה דיסקרטית ח", ומספקת את הכלים המתמטיים הדרושים להבנת עקרונות רבים במדעי המחשב, ובפרט בקריפטוגרפיה. נתמקד בתכונות של מספרים שלמים וביישומיהם המעשיים, תוך שימת דגש על נושאים המופיעים תדיר במבחני הטכניון: הבנה מעמיקה של אלגוריתמים, יכולת הוכחה, ויישום מושגים תיאורטיים לפתרון בעיות.
יסודות תורת המספרים השלמים
תורת המספרים מתחילה בהבנת היחסים הבסיסיים בין מספרים שלמים.
אלגוריתם אוקלידס
האלגוריתם האוקלידי הוא שיטה יעילה למציאת המ.מ.מ. של שני מספרים שלמים. הוא מבוסס על העיקרון ש-gcd(a,b) = gcd(b, a mod b). האלגוריתם מסתיים כאשר שארית החלוקה היא 0, ואז המ.מ.מ. הוא המחלק האחרון שאינו אפס.
חשבון מודולרי
חשבון מודולרי עוסק בשאריות של חלוקה ומאפשר לנו לעבוד עם "שעון" סופי של מספרים.
תכונות בסיסיות
- חיבור/חיסור: אם a ≡ b (mod n) ו-c ≡ d (mod n), אז a+c ≡ b+d (mod n) ו-a-c ≡ b-d (mod n).
- כפל: אם a ≡ b (mod n) ו-c ≡ d (mod n), אז ac ≡ bd (mod n).
הופכי מודולרי
הופכי מודולרי של a מודולו n הוא מספר x המקיים ax ≡ 1 (mod n). הופכי כזה קיים אם ורק אם gcd(a,n) = 1. את ההופכי המודולרי מוצאים באמצעות האלגוריתם האוקלידי המורחב.
מספרים ראשוניים ותיאוריות מפתח
מספרים ראשוניים הם אבני הבניין של המספרים השלמים, וחיוניים לקריפטוגרפיה.
משפט פרמה הקטן ומשפט אוילר
משפט פרמה הקטן
אם p הוא מספר ראשוני ו-a הוא מספר שלם שאינו מתחלק ב-p, אז ap-1 ≡ 1 (mod p). כמו כן, לכל a, מתקיים ap ≡ a (mod p).
משפט אוילר
אם n הוא מספר שלם חיובי ו-a הוא מספר שלם זר ל-n (כלומר gcd(a,n)=1), אז aφ(n) ≡ 1 (mod n).
פונקציית אוילר (φ)
φ(n) סופרת את מספר המספרים השלמים החיוביים הקטנים מ-n וזרים ל-n. אם n=pq כאשר p ו-q ראשוניים שונים, אז φ(n)=(p-1)(q-1). פונקציה זו מרחיבה את משפט פרמה למודולוס שאינו ראשוני.
שני המשפטים הללו חיוניים לפישוט חישובי חזקות מודולריות גדולות, שהם ליבת אלגוריתמים קריפטוגרפיים.
יישומים בקריפטוגרפיה: הצפנת RSA
אלגוריתם RSA הוא דוגמה קלאסית לאופן שבו תורת המספרים הבדידה משמשת ליצירת מערכות אבטחה חזקות.
עקרונות מפתח ב-RSA
- בחירת מפתחות: בוחרים שני מספרים ראשוניים גדולים p ו-q. מחשבים n = pq ו-φ(n) = (p-1)(q-1).
- מפתח הצפנה ציבורי (e): בוחרים e כך ש-1 ו-gcd(e, φ(n)) = 1.
- מפתח פענוח פרטי (d): מחשבים את d כהופכי המודולרי של e מודולו φ(n), כלומר ed ≡ 1 (mod φ(n)). זה נעשה באמצעות האלגוריתם האוקלידי המורחב.
- הצפנה: הודעה M מוצפנת ל-C באמצעות הנוסחה C = Me mod n.
- פענוח: הודעה מוצפנת C מפוענחת ל-M באמצעות הנוסחה M = Cd mod n.
האבטחה של RSA נשענת על הקושי בפירוק לגורמים של מספרים גדולים (n), מה שמונע ממתקיף לחשב את φ(n) וממנו את d.
שאלות לדיון
- כיצד האלגוריתם האוקלידי המורחב משמש למציאת הופכי מודולרי? תן דוגמה מספרית עבור 7-1 mod 26.
- הסבר את הקשר בין משפט פרמה הקטן למשפט אוילר. מתי נשתמש בכל אחד מהם בחישובי חזקות מודולריות?
- מדוע חיוני שמפתח הפענוח d יהיה הופכי מודולרי של מפתח ההצפנה e מודולו φ(n) באלגוריתם RSA? פרט את ההוכחה המתמטית.
- כיצד ידע על פירוק לגורמים של n (המודולוס הציבורי ב-RSA) משפיע על אבטחת האלגוריתם?
נקודות לתשובת מודל
- אלגוריתם אוקלידי מורחב והופכי מודולרי: הצג את שלבי האלגוריתם הסטנדרטי, ולאחר מכן את שלבי המעקב לאחור כדי לבטא את המ.מ.מ. כצירוף ליניארי ax+by. הראה כיצד כאשר gcd(a,n)=1, אחד המקדמים (x או y) הוא ההופכי המודולרי. הדוגמה המספרית צריכה להדגים את כל השלבים בבירור.
- פרמה ואוילר: משפט פרמה הקטן הוא מקרה פרטי של משפט אוילר כאשר המודולוס n הוא מספר ראשוני p (אז φ(p) = p-1). משפט אוילר כללי יותר וחל על כל מודולוס n חיובי, בתנאי שהבסיס זר ל-n. שניהם משמשים להקטנת המעריך בחזקות מודולריות: ak ≡ ak mod φ(n) (mod n).
- חשיבות d ב-RSA: מפתח הפענוח d מוגדר כך ש-ed ≡ 1 (mod φ(n)). המשמעות היא ש-ed = 1 + kφ(n) עבור שלם כלשהו k. לכן, Cd ≡ (Me)d ≡ Med ≡ M1+kφ(n) ≡ M1 * (Mφ(n))k (mod n). לפי משפט אוילר, Mφ(n) ≡ 1 (mod n) (בהנחה ש-gcd(M,n)=1), ולכן M * 1k ≡ M (mod n). זה מבטיח שהפענוח מחזיר את ההודעה המקורית.
- אבטחת RSA ופירוק לגורמים: אם תוקף יכול לפרק את n לגורמים p ו-q, הוא יכול לחשב בקלות את φ(n)=(p-1)(q-1). מרגע שיש לו את φ(n) ואת מפתח ההצפנה הציבורי e, הוא יכול למצוא את מפתח הפענוח d באמצעות האלגוריתם האוקלידי המורחב. לכן, הקושי החישובי בפירוק לגורמים של מספרים גדולים הוא הבסיס לאבטחת RSA.