במתמטיקה, אריתמטיקה מודולרית היא מערכת חישוב של מספרים שלמים, בעזרתה הם "מתהפכים" כשהם מגיעים לערך מסוים - המודול (או רבים מהם). הגישה המודרנית לסוג זה של מדע פותחה על ידי קרל פרידריך גאוס ב-Disquisitiones Arithmeticae שלו שפורסם ב-1801. מדעני מחשבים מאוד אוהבים להשתמש בשיטה זו, מכיוון שהיא מאוד מעניינת ופותחת אפשרויות חדשות מסוימות בפעולות עם מספרים.
Essence
מכיוון שמספר השעות מתחיל שוב אחרי שהוא מגיע ל-12, זה מודולו אריתמטי 12. לפי ההגדרה למטה, 12 מתאים לא רק ל-12, אלא גם ל-0, אז אפשר גם למנות את הזמן שנקרא " 12:00". "0:00". אחרי הכל, 12 זהה ל-0 modulo 12.
ניתן לעבד חשבון מודולרי באופן מתמטי על ידי הכנסת יחס תואם למספרים שלמים התואם לפעולות על מספרים שלמיםמספרים: חיבור, חיסור וכפל. עבור מספר שלם חיובי n, שני מספרים a ו-b אמורים להיות תואמים modulo n אם ההפרש שלהם a - b הוא כפולה של n (כלומר, אם קיים מספר שלם k כך ש- a - b=kn).
Deductions
במתמטיקה תיאורטית, אריתמטיקה מודולרית היא אחד היסודות של תורת המספרים, המשפיעה כמעט על כל ההיבטים של המחקר שלה, והיא נמצאת בשימוש נרחב גם בתורת הקבוצות, הטבעות, הקשרים והאלגברה המופשטת. בתחום המתמטיקה השימושית, הוא משמש באלגברה ממוחשבת, קריפטוגרפיה, מדעי המחשב, כימיה, אמנות חזותית ומוזיקה.
תרגול
יישום מעשי מאוד הוא חישוב סכומי ביקורת במזהי מספרים סידוריים. לדוגמה, כמה תקני ספרים נפוצים משתמשים במודולו 11 האריתמטי (אם יצא לפני 1 בינואר 2007) או מודולו 10 (אם יצא לפני או אחרי 1 בינואר 2007). באופן דומה, למשל, במספרי חשבונות בנק בינלאומיים (IBAN). זה משתמש בחשבון modulo 97 כדי לזהות שגיאות קלט משתמש במספרי חשבונות בנק.
בכימיה, הספרה האחרונה במספר הרישום של CAS (מספר הזיהוי הייחודי של כל תרכובת כימית) היא ספרת הביקורת. זה מחושב על ידי לקיחת הספרה האחרונה של שני החלקים הראשונים של מספר הרישום CAS כפול 1, הספרה הקודמת פי 2, הספרה הקודמת פי 3 וכו', חיבור הכל וחישוב הסכום modulo 10.
מהי קריפטוגרפיה? העובדה היאיש לו קשר חזק מאוד עם הנושא הנדון. בקריפטוגרפיה, חוקי האריתמטיקה המודולרית עומדים ישירות בבסיס מערכות מפתח ציבורי כגון RSA ודיפי-הלמן. כאן הוא מספק את השדות הסופיים העומדים בבסיס העקומות האליפטיות. משמש באלגוריתמי מפתח סימטריים שונים, כולל Advanced Encryption Standard (AES), International Data Encryption Algorithm ו-RC4.
Application
שיטה זו משמשת באזורים שבהם אתה צריך לקרוא מספרים. הוא פותח על ידי מתמטיקאים, וכולם משתמשים בו, במיוחד מדעני מחשב. זה מתועד היטב בספרים כמו Modular Arithmetic for Dummies. עם זאת, מספר מומחים ממליצים לא להתייחס לספרות כזו ברצינות.
במדעי המחשב, אריתמטיקה מודולרית משמשת לעתים קרובות בפעולות סיביות ואחרות המערבות מבני נתונים מעגליים ברוחב קבוע. אנליסטים אוהבים להשתמש בו. פעולת המודולו מיושמת בשפות תכנות רבות ובמחשבונים. במקרה זה, זוהי דוגמה אחת ליישום כזה. השוואת מודולו, חלוקה עם שארית וטריקים אחרים משמשים גם בתכנות.
במוזיקה, נעשה שימוש במודולו אריתמטי 12 כאשר בוחנים מערכת של טמפרמנט שווה של שנים עשר צלילים, שבה האוקטבה והאנהרמונית שוות ערך. במילים אחרות, המקשים ביחס 1-2 או 2-1 שווים. במוזיקה ובמדעי הרוח אחרים, החשבון משחק תפקיד משמעותי למדי, אבל בספרי לימודמדעני מחשבים בדרך כלל לא כותבים על זה.
שיטה לצמצום תשע
שיטת ההמרה של 9s מציעה בדיקה מהירה של חישובים אריתמטיים עשרוניים ידניים. הוא מבוסס על אריתמטיקה מודולרית מודולו 9 ובפרט על התכונה הקובעת 10 10 1.
יש דוגמאות אחרות. אריתמטי מודולו 7 משמש באלגוריתמים הקובעים את היום בשבוע עבור תאריך מסוים. במיוחד, ההתאמה של זלר ואלגוריתם יום הדין עושים שימוש רב במודולו אריתמטי 7.
יישומים אחרים
כבר נאמר על אריתמטיקה מודולרית בהצפנה. בתחום הזה, היא פשוט שאין לה תחליף. באופן כללי יותר, אריתמטיקה מודולרית מוצאת גם יישומים בדיסציפלינות כמו משפטים, כלכלה (כגון תורת המשחקים) ותחומים אחרים של מדעי החברה. במילים אחרות, כאשר החלוקה היחסית וחלוקת המשאבים משחקת תפקיד מרכזי.
מכיוון שלחשבון מודולרי יש מגוון רחב כל כך של שימושים, חשוב לדעת כמה קשה לפתור מערכת השוואות. מערכת ליניארית של קונגרואנסים יכולה להיפתר בזמן פולינום בצורה של חיסול גאוסי. זה מתואר ביתר פירוט על ידי משפט הקונגרואנס הליניארי. אלגוריתמים כגון הפחתה של מונטגומרי קיימים גם כדי לאפשר ביצוע פעולות אריתמטיות פשוטות ביעילות. לדוגמה, כפל ואקספונציה מודולו n, עבור מספרים גדולים. זה מאוד חשוב לדעת כדי להבין מהקריפטוגרפיה. אחרי הכל, זה פשוט עובד עם פעולות דומות.
קונגרואנס
חלק מהפעולות, כמו מציאת הלוגריתם הבדיד או ההלימה הריבועית, נראות מורכבות כמו פירוק מספרים שלמים, ולכן הן נקודת המוצא לאלגוריתם הצפנה והצפנה. בעיות אלו עשויות להיות NP-בינוני.
דוגמאות
להלן שלוש פונקציות C מהירות למדי - שתיים לביצוע כפל מודולרי ואחת להעלאה למספרים מודולריים עבור מספרים שלמים ללא סימן עד 63 סיביות, ללא גלישה חולפת.
זמן קצר לאחר גילוי המספרים השלמים (1, 2, 3, 4, 5…) מתברר שהם מחולקים לשתי קבוצות:
- אווי: מתחלק ב-2 (0, 2, 4, 6..).
- אי זוגי: לא ניתן לחלוקה ב-2 (1, 3, 5, 7…).
למה ההבחנה הזו חשובה? זוהי תחילתה של הפשטה. אנו מבחינים במאפיינים של המספר (למשל, זוגי או אי-זוגי) ולא רק המספר עצמו ("37").
זה מאפשר לנו לחקור את המתמטיקה ברמה עמוקה יותר ולמצוא קשרים בין סוגי מספרים ולא ספציפיים.
מאפיינים של מספר
להיות "שלושה" הוא רק עוד תכונה של מספר. אולי לא שימושי באופן מיידי כמו זוגי/אי זוגי, אבל זה שם. אנחנו יכולים ליצור כללים כמו "שלוש עשרה x שלוש וריד=שלוש עשרה" וכן הלאה. אבל זה מטורף. אנחנו לא יכולים ליצור מילים חדשות כל הזמן.
פעולת המודולו (בקיצור mod או "%" בשפות תכנות רבות) היא היתרה כאשרחֲלוּקָה. לדוגמה, "5 mod 3=2", כלומר 2 הוא היתרה כאשר אתה מחלק 5 ב-3.
כאשר ממירים מונחים יומיומיים למתמטיקה, "מספר זוגי" הוא המקום שבו הוא "0 mod 2", כלומר השאר הוא 0 כאשר מחלקים ב-2. מספר אי זוגי הוא "1 mod 2" (יש לו שארית מתוך 1).
מספרים זוגיים ואי-זוגיים
מהו זוגי x זוגי x אי זוגי x אי זוגי? ובכן, זה 0 x 0 x 1 x 1=0. למעשה, אתה יכול לראות אם מספר זוגי מוכפל בכל מקום, שבו התוצאה כולה תהיה אפס.
הטריק עם מתמטיקה מודולרית הוא שכבר השתמשנו בה כדי לאחסן זמן - לפעמים נקרא "חשבון שעון".
לדוגמה: 7:00 בבוקר (בוקר/צהריים - לא משנה). איפה מחוג השעות יהיה בעוד 7 שעות?
מודולציות
(7 + 7) mod 12=(14) mod 12=2 mod 12 [2 הוא השאר כאשר 14 מחולק ב-12. משוואה 14 mod 12=2 mod 12 פירושה 14 שעות ו-2 שעות אותו דבר בשעון של 12 שעות. הם חופפים, מסומנים בסימן שוויון משולש: 14 ≡ 2 mod 12.
דוגמה נוספת: השעה 8:00 בבוקר. איפה היד הגדולה תהיה בעוד 25 שעות?
במקום להוסיף 25 ל-8, אתה יכול להבין ש-25 שעות זה רק "יום אחד + שעה". התשובה פשוטה. אז, השעון יסתיים שעה אחת קדימה - בשעה 9:00.
(8 + 25) mod 12 ≡ (8) mod 12 + (25) mod 12 ≡ (8) mod 12 + (1) mod 12 ≡ 9 mod 12. המרת באופן אינטואיטיבי 25 ל-1 והוספת את זה עד 8.
בשימוש בשעון כאנלוגיה, נוכל להבין אםכללי החשבון המודולרי, והם עובדים.
הוספה/חיסור
נניח ששתי פעמים נראות אותו הדבר בשעון שלנו ("2:00" ו-"14:00"). אם נוסיף את אותן X שעות לשניהם, מה יקרה? ובכן, הם מתחלפים באותה כמות על השעון! 2:00 + 5 שעות ≡ 14:00 + 5 שעות - שניהם יופיעו ב-7:00.
למה? אנחנו יכולים פשוט להוסיף 5 ל-2 השאריות שיש לשניהם והם מתקדמים באותו אופן. עבור כל המספרים התואמים (2 ו-14), חיבור וחיסור מקבלים אותה תוצאה.
קשה יותר לדעת אם הכפל נשאר זהה. אם 14 ≡ 2 (מוד 12), האם נוכל להכפיל את שני המספרים ולקבל את אותה תוצאה? בוא נראה מה קורה כשנכפיל ב-3.
ובכן, 2:003 × 6:00. אבל מה זה 14:003?
זכור, 14=12 + 2. אז אנחנו יכולים לומר
143=(12 + 2)3=(123) + (23)
ניתן להתעלם מהחלק הראשון (123)! ההצפה של 12 שעות הנושאת 14 פשוט חוזרת על עצמה מספר פעמים. אבל למי אכפת? אנחנו מתעלמים מהצף בכל מקרה.
כפל
בעת הכפל, רק השאר חשוב, כלומר, אותן שעתיים עבור 14:00 ו-2:00. באופן אינטואיטיבי, כך אני רואה שכפל לא משנה את הקשר עם מתמטיקה מודולרית (אפשר להכפיל את שני הצדדים של קשר מודולרי ולקבל את אותה תוצאה).
אנחנו עושים את זה באופן אינטואיטיבי, אבל זה נחמד לתת לזה שם. יש לך טיסה שתגיע בשעה 15:00. הואמתעכב ב-14 שעות. באיזו שעה הוא ינחת?
14 ≡ 2 mod 12. אז, תחשוב על השעה 2, אז המטוס ינחת ב-5 בבוקר. הפתרון פשוט: 3 + 2=5 בבוקר. זה קצת יותר מסובך מפעולת המודולו הפשוטה, אבל העיקרון זהה.
