În matematică, aritmetica modulară este un sistem de calcul al numerelor întregi, cu ajutorul căruia se „întoarce” atunci când ating o anumită valoare – modulul (sau pluralul acestora). Abordarea modernă a acestui tip de știință a fost dezvoltată de Carl Friedrich Gauss în Disquisitiones Arithmeticae publicată în 1801. Informaticii sunt foarte pasionați să folosească această metodă, deoarece este foarte interesantă și deschide anumite posibilități noi în operațiunile cu numere.
Esență
Deoarece numărul de ore începe din nou după ce ajunge la 12, este aritmetic modulo 12. Conform definiției de mai jos, 12 corespunde nu numai cu 12, ci și cu 0, deci se poate numi și timpul numit „ 12:00 . „0:00”. La urma urmei, 12 este același cu 0 modulo 12.
Aritmetica modulară poate fi procesată matematic prin introducerea unei relații congruente cu numerele întregi care este compatibilă cu operațiile pe numere întreginumere: adunare, scădere și înmulțire. Pentru un număr întreg pozitiv n, se spune că două numere a și b sunt congruente modulo n dacă diferența lor a - b este un multiplu al lui n (adică dacă există un număr întreg k astfel încât a - b=kn).
Deduceri
În matematica teoretică, aritmetica modulară este unul dintre fundamentele teoriei numerelor, afectând aproape toate aspectele studiului acesteia și este, de asemenea, utilizată pe scară largă în teoria grupurilor, inelelor, nodurilor și algebrei abstracte. În domeniul matematicii aplicate, este folosit în algebră computerizată, criptografie, informatică, chimie, arte vizuale și muzică.
Practică
O aplicație foarte practică este calcularea sumelor de control în identificatorii numerelor de serie. De exemplu, unele standarde comune de cărți folosesc aritmetica modulo 11 (dacă este lansat înainte de 1 ianuarie 2007) sau modulo 10 (dacă este lansat înainte sau după 1 ianuarie 2007). În mod similar, de exemplu, în numerele internaționale de cont bancar (IBAN). Aceasta utilizează aritmetica modulo 97 pentru a detecta erorile de introducere a utilizatorului în numerele de cont bancar.
În chimie, ultima cifră a numărului de înregistrare CAS (numărul unic de identificare pentru fiecare compus chimic) este cifra de control. Se calculează luând ultima cifră din primele două părți ale numărului de înregistrare CAS înmulțită cu 1, cifra anterioară de 2 ori, cifra anterioară de 3 ori etc., adunând totul și calculând suma modulo 10.
Ce este criptografia? Adevărul este căare o legătură foarte strânsă cu subiectul în discuție. În criptografie, legile aritmeticii modulare stau direct la baza sistemelor cu cheie publică, cum ar fi RSA și Diffie-Hellman. Aici furnizează câmpurile finite care stau la baza curbelor eliptice. Folosit în diverși algoritmi de cheie simetrică, inclusiv Advanced Encryption Standard (AES), International Data Encryption Algorithm și RC4.
Aplicație
Această metodă este folosită în zonele în care trebuie să citiți numere. A fost dezvoltat de matematicieni și toată lumea îl folosește, în special informaticieni. Acest lucru este bine documentat în cărți precum Modular Arithmetic for Dummies. Cu toate acestea, un număr de experți recomandă să nu luați în serios o astfel de literatură.
În informatică, aritmetica modulară este adesea folosită în operațiuni pe biți și alte operațiuni care implică structuri de date circulare cu lățime fixă. Analiştilor le place să-l folosească. Operația modulo este implementată în multe limbaje de programare și calculatoare. În acest caz, este un exemplu de astfel de aplicație. Compararea modulelor, împărțirea cu un rest și alte trucuri sunt, de asemenea, folosite în programare.
În muzică, aritmetica modulo 12 este folosită atunci când se consideră un sistem de temperament egal de douăsprezece tonuri, în care octava și enarmonica sunt echivalente. Cu alte cuvinte, cheile din raportul 1-2 sau 2-1 sunt echivalente. În muzică și alte științe umaniste, aritmetica joacă un rol destul de important, dar în manualede obicei, informaticienii nu scriu despre asta.
Metoda de reducere a nouă
Metoda de conversie 9s oferă o verificare rapidă a calculelor aritmetice zecimale manuale. Se bazează pe aritmetica modulară modulo 9 și în special pe proprietatea decisivă 10 10 1.
există alte exemple. Aritmetica modulo 7 este utilizată în algoritmii care determină ziua săptămânii pentru o anumită dată. În special, congruența lui Zeller și algoritmul Doomsday folosesc intens aritmetica modulo 7.
Alte aplicații
S-a spus deja despre aritmetica modulară în criptografie. În acest domeniu, ea este pur și simplu de neînlocuit. Mai general, aritmetica modulară își găsește aplicații și în discipline precum dreptul, economia (cum ar fi teoria jocurilor) și alte domenii ale științelor sociale. Cu alte cuvinte, unde diviziunea și distribuția proporțională a resurselor joacă un rol major.
Deoarece aritmetica modulară are o gamă atât de largă de utilizări, este important să știm cât de dificil este să rezolvi un sistem de comparații. Un sistem liniar de congruențe poate fi rezolvat în timp polinomial sub forma eliminării gaussiene. Acest lucru este descris mai detaliat de teorema congruenței liniare. Algoritmi precum reducerea Montgomery există și pentru a permite efectuarea eficientă a operațiilor aritmetice simple. De exemplu, înmulțirea și exponentiația modulo n, pentru numere mari. Acest lucru este foarte important de știut pentru a înțelege cecriptografie. La urma urmei, funcționează doar cu operațiuni similare.
Congruență
Unele operații, cum ar fi găsirea logaritmului discret sau a congruenței pătratice, par a fi la fel de complexe ca factorizarea întregului și, prin urmare, sunt punctul de plecare pentru algoritmii criptografici și criptare. Aceste probleme pot fi NP-intermediare.
Exemple
Următoarele sunt trei funcții C destul de rapide - două pentru efectuarea înmulțirii modulare și una pentru creșterea la numere modulare pentru numere întregi fără semn de până la 63 de biți, fără depășire tranzitorie.
La scurt timp după descoperirea numerelor întregi (1, 2, 3, 4, 5…) devine evident că acestea sunt împărțite în două grupuri:
- Par: divizibil cu 2 (0, 2, 4, 6..).
- Impar: nu este divizibil cu 2 (1, 3, 5, 7…).
De ce este importantă această distincție? Acesta este începutul abstracției. Observăm proprietățile numărului (de exemplu, par sau impar) și nu doar numărul în sine ("37").
Acest lucru ne permite să explorăm matematica la un nivel mai profund și să găsim relații între tipurile de numere, mai degrabă decât unele specifice.
Proprietăți ale unui număr
A fi un „trei” este doar o altă proprietate a unui număr. Poate nu la fel de util imediat ca par/impar, dar există. Putem crea reguli precum „treisprezece x trei venă=treisprezece” și așa mai departe. Dar e o nebunie. Nu putem face cuvinte noi tot timpul.
Operația modulo (mod prescurtat sau „%” în multe limbaje de programare) este restul cândDivizia. De exemplu, „5 mod 3=2”, ceea ce înseamnă că 2 este restul când împărțiți 5 la 3.
Când convertiți termenii de zi cu zi în matematică, un „număr par” este „0 mod 2”, adică restul este 0 atunci când este împărțit la 2. Un număr impar este „1 mod 2” (are un rest din 1).
Numere pare și impare
Ce este par x par x impar x impar? Ei bine, este 0 x 0 x 1 x 1=0. De fapt, puteți vedea dacă un număr par este înmulțit oriunde, unde întregul rezultat va fi zero.
Trucul cu matematica modulară este că deja am folosit-o pentru a stoca timpul - uneori numită „aritmetica ceasului”.
De exemplu: 7:00 am (am/pm - nu contează). Unde va fi acul orelor peste 7 ore?
Modulații
(7 + 7) mod 12=(14) mod 12=2 mod 12 [2 este restul când 14 este împărțit la 12. Ecuația 14 mod 12=2 mod 12 înseamnă 14 ore și 2 ore arată același lucru pe un ceas de 12 ore. Sunt congruente, indicate printr-un triplu semn egal: 14 ≡ 2 mod 12.
Un alt exemplu: este ora 8:00. Unde va fi mâna mare în 25 de ore?
În loc să adăugați 25 la 8, puteți înțelege că 25 de ore înseamnă doar „1 zi + 1 oră”. Răspunsul este simplu. Deci, ceasul se va încheia cu 1 oră înainte - la 9:00.
(8 + 25) mod 12 ≡ (8) mod 12 + (25) mod 12 ≡ (8) mod 12 + (1) mod 12 ≡ 9 mod 12. Ai convertit intuitiv 25 la 1 și ai adăugat asta la 8.
Folosind ceasul ca analogie, ne putem da seama dacăregulile aritmeticii modulare și funcționează.
Adunare/Scădere
Să presupunem că două ori arată la fel pe ceasul nostru ("2:00" și "14:00"). Dacă adăugăm aceleași x ore la ambele, ce se întâmplă? Ei bine, se schimbă pentru aceeași sumă pe ceas! 2:00 + 5 ore ≡ 14:00 + 5 ore - ambele vor fi afișate la 7:00.
De ce? Putem adăuga pur și simplu 5 la cele 2 resturi pe care ambele le au și avansează în același mod. Pentru toate numerele congruente (2 și 14), adunarea și scăderea au același rezultat.
Este mai greu de știut dacă înmulțirea rămâne aceeași. Dacă 14 ≡ 2 (mod 12), putem înmulți ambele numere și obținem același rezultat? Să vedem ce se întâmplă când înmulțim cu 3.
Ei bine, 2:003 × 6:00. Dar ce înseamnă 14:003?
Nu uitați, 14=12 + 2. Deci putem spune
143=(12 + 2)3=(123) + (23)
Prima parte (123) poate fi ignorată! Debordarea de 12 ore care poartă 14 pur și simplu se repetă de mai multe ori. Dar cui ii pasa? Ignorăm oricum debordarea.
Multiplicare
La înmulțire, contează doar restul, adică aceleași 2 ore pentru 14:00 și 2:00. Intuitiv, așa văd că multiplicarea nu schimbă relația cu matematica modulară (puteți înmulți ambele părți ale unei relații modulare și obțineți același rezultat).
O facem intuitiv, dar este frumos să îi dăm un nume. Aveți un zbor care sosește la 15:00. Elîntârziat cu 14 ore. La ce oră va ateriza?
14 ≡ 2 mod 12. Deci, gândiți-vă la ora 2, așa că avionul va ateriza la ora 5 dimineața. Soluția este simplă: 3 + 2=5 am. Aceasta este puțin mai complicată decât operația modulo simplă, dar principiul este același.
