U matematici je modularna aritmetika računski sustav za cijele brojeve, uz pomoć kojih oni "preokreću" kada dostignu određenu vrijednost - modul (ili množinu njih). Suvremeni pristup ovoj vrsti znanosti razvio je Carl Friedrich Gauss u svojoj Disquisitiones Arithmeticae objavljenoj 1801. godine. Računalni znanstvenici jako vole koristiti ovu metodu, jer je vrlo zanimljiva i otvara određene nove mogućnosti u operacijama s brojevima.
Essence
Budući da broj sati počinje ponovno nakon što dosegne 12, to je aritmetički modul 12. Prema donjoj definiciji, 12 odgovara ne samo 12, već i 0, tako da se također može imenovati vrijeme koje se zove " 12:00". "0:00". Uostalom, 12 je isto kao 0 po modulu 12.
Modularna aritmetika se može obraditi matematički uvođenjem kongruentnog odnosa na cijele brojeve koji je kompatibilan s operacijama na cijelim brojevimabrojevi: zbrajanje, oduzimanje i množenje. Za pozitivan cijeli broj n, kaže se da su dva broja a i b podudarna po modulu n ako je njihova razlika a - b višekratnik n (tj. ako postoji cijeli broj k takav da je a - b=kn).
Odbici
U teorijskoj matematici, modularna aritmetika je jedan od temelja teorije brojeva, koja utječe na gotovo sve aspekte njenog proučavanja, a također se široko koristi u teoriji grupa, prstenova, čvorova i apstraktne algebre. U području primijenjene matematike koristi se u računalnoj algebri, kriptografiji, informatici, kemiji, vizualnoj umjetnosti i glazbi.
Vježba
Vrlo praktična primjena je izračun kontrolnih zbroja u identifikatorima serijskih brojeva. Na primjer, neki uobičajeni knjižni standardi koriste aritmetički modul 11 (ako je objavljen prije 1. siječnja 2007.) ili modul 10 (ako je objavljen prije ili nakon 1. siječnja 2007.). Slično, na primjer, u međunarodnim brojevima bankovnih računa (IBAN). Ovo koristi aritmetiku modulo 97 za otkrivanje korisničkih pogrešaka u unosu brojeva bankovnih računa.
U kemiji, zadnja znamenka CAS registracijskog broja (jedinstveni identifikacijski broj za svaki kemijski spoj) je provjera. Izračunava se tako da se posljednja znamenka prva dva dijela registracijskog broja CAS-a pomnoži s 1, prethodna znamenka 2 puta, prethodna znamenka 3 puta, itd., sve se zbroji i izračuna zbroj po modulu 10.
Što je kriptografija? Činjenica je daima vrlo jaku povezanost s temom o kojoj se raspravlja. U kriptografiji, zakoni modularne aritmetike izravno leže u temelju sustava javnih ključeva kao što su RSA i Diffie-Hellman. Ovdje daje konačna polja koja leže u pozadini eliptičkih krivulja. Koristi se u raznim algoritmima simetričnog ključa, uključujući napredni standard šifriranja (AES), međunarodni algoritam šifriranja podataka i RC4.
Prijava
Ova metoda se koristi u područjima gdje trebate čitati brojeve. Razvili su ga matematičari, a koriste ga svi, a posebno informatičari. To je dobro dokumentirano u knjigama poput Modularne aritmetike za lutke. Međutim, brojni stručnjaci preporučuju da se takva literatura ne shvaća ozbiljno.
U informatici, modularna aritmetika se često koristi u bitskim i drugim operacijama koje uključuju kružne strukture podataka fiksne širine. Analitičari ga vole koristiti. Modul operacija je implementirana u mnogim programskim jezicima i kalkulatorima. U ovom slučaju, to je jedan primjer takve aplikacije. Usporedba modula, dijeljenje s ostatkom i drugi trikovi također se koriste u programiranju.
U glazbi, aritmetički modulo 12 se koristi kada se razmatra sustav jednakog temperamenta od dvanaest tonova, u kojem su oktava i enharmonik ekvivalentni. Drugim riječima, ključevi u omjeru 1-2 ili 2-1 su ekvivalentni. U glazbi i drugim humanističkim znanostima aritmetika igra prilično značajnu ulogu, ali u udžbenicimainformatičari obično ne pišu o tome.
Metoda smanjivanja devetki
Metoda pretvorbe 9s nudi brzu provjeru ručnih decimalnih aritmetičkih izračuna. Temelji se na modularnoj aritmetici po modulu 9, a posebno na odlučujućem svojstvu 10 10 1.
ima i drugih primjera. Aritmetika po modulu 7 koristi se u algoritmima koji određuju dan u tjednu za određeni datum. Posebno, Zellerova kongruencija i algoritam Sudnjeg dana intenzivno koriste aritmetiku po modulu 7.
Ostale aplikacije
Već je rečeno o modularnoj aritmetici u kriptografiji. Na ovom području ona je jednostavno nezamjenjiva. Općenito, modularna aritmetika također nalazi primjenu u disciplinama kao što su pravo, ekonomija (kao što je teorija igara) i druga područja društvenih znanosti. Drugim riječima, gdje proporcionalna podjela i raspodjela resursa igra glavnu ulogu.
Budući da modularna aritmetika ima tako širok raspon primjena, važno je znati koliko je teško riješiti sustav usporedbi. Linearni sustav podudarnosti može se riješiti u polinomskom vremenu u obliku Gaussove eliminacije. To je detaljnije opisano linearnim teoremom kongruencije. Algoritmi kao što je Montgomeryjeva redukcija također postoje kako bi se omogućilo učinkovito izvođenje jednostavnih aritmetičkih operacija. Na primjer, množenje i stepenovanje po modulu n, za velike brojeve. Ovo je vrlo važno znati kako biste razumjeli štokriptografija. Uostalom, radi samo sa sličnim operacijama.
kongruencija
Neke operacije, kao što je pronalaženje diskretnog logaritma ili kvadratne podudarnosti, čini se složenim kao cjelobrojna faktorizacija i stoga su početna točka za kriptografske algoritme i enkripciju. Ovi problemi mogu biti NP-srednji.
Primjeri
Slijede tri prilično brze C funkcije - dvije za izvođenje modularnog množenja i jedna za podizanje na modularne brojeve za nepredznačene cijele brojeve do 63 bita, bez prolaznog prekoračenja.
Ubrzo nakon otkrića cijelih brojeva (1, 2, 3, 4, 5…) postaje očito da su podijeljeni u dvije grupe:
- Par: djeljivo s 2 (0, 2, 4, 6..).
- Neparno: nije djeljivo s 2 (1, 3, 5, 7…).
Zašto je ova razlika važna? Ovo je početak apstrakcije. Primjećujemo svojstva broja (npr. paran ili nepar), a ne samo sam broj ("37").
Ovo nam omogućuje da istražimo matematiku na dubljoj razini i pronađemo odnose između vrsta brojeva, a ne specifičnih.
Svojstva broja
Biti "tri" samo je još jedno svojstvo broja. Možda nije tako odmah korisno kao parno/neparno, ali postoji. Možemo stvoriti pravila poput "trinaest x tri vena=trinaest" i tako dalje. Ali to je ludo. Ne možemo stalno stvarati nove riječi.
Modulo operacija (skraćeno mod ili "%" u mnogim programskim jezicima) je ostatak kadapodjela. Na primjer, "5 mod 3=2", što znači da je 2 ostatak kada podijelite 5 s 3.
Prilikom pretvaranja svakodnevnih pojmova u matematiku, "parni broj" je mjesto gdje je "0 mod 2", što znači da je ostatak 0 kada se podijeli s 2. Neparni broj je "1 mod 2" (ima ostatak od 1).
Parni i neparni brojevi
Koliko je parno x parno x neparno x neparno? Pa, to je 0 x 0 x 1 x 1=0. Zapravo, možete vidjeti je li paran broj bilo gdje pomnožen, pri čemu će cijeli rezultat biti nula.
Trik s modularnom matematikom je da smo je već koristili za pohranjivanje vremena - ponekad se naziva "aritmetika sata".
Na primjer: 7:00 ujutro (am/pm - nije važno). Gdje će kazaljka biti za 7 sati?
Modulacije
(7 + 7) mod 12=(14) mod 12=2 mod 12 [2 je ostatak kada se 14 podijeli s 12. Jednadžba 14 mod 12=2 mod 12 znači 14 sati i 2 sata, pogledajte isto na 12-satnom satu. Kongruentni su, označeni trostrukim znakom jednakosti: 14 ≡ 2 mod 12.
Još jedan primjer: 8:00 je ujutro. Gdje će biti velika ruka za 25 sati?
Umjesto dodavanja 25 na 8, možete razumjeti da je 25 sati samo "1 dan + 1 sat". Odgovor je jednostavan. Dakle, sat će završiti 1 sat unaprijed - u 9:00.
(8 + 25) mod 12 ≡ (8) mod 12 + (25) mod 12 ≡ (8) mod 12 + (1) mod 12 ≡ 9 mod 12. Intuitivno ste pretvorili 25 u 1 i dodali ovo do 8.
Koristeći sat kao analogiju, možemo shvatiti je lipravila modularne aritmetike i funkcioniraju.
Zbrajanje/Oduzimanje
Recimo da dva puta izgledaju isto na našem satu ("2:00" i "14:00"). Ako objema dodamo isto x sati, što se događa? Pa mijenjaju se za isti iznos na satu! 2:00 + 5 sati ≡ 14:00 + 5 sati - oba će prikazati 7:00.
Zašto? Možemo jednostavno dodati 5 na 2 ostatka koja oba imaju i oni napreduju na isti način. Za sve podudarne brojeve (2 i 14), zbrajanje i oduzimanje imaju isti rezultat.
Teže je znati ostaje li množenje isti. Ako je 14 ≡ 2 (mod 12), možemo li pomnožiti oba broja i dobiti isti rezultat? Pogledajmo što će se dogoditi kada pomnožimo s 3.
Pa, 2:003 × 6:00. Ali koliko je 14:003?
Zapamti, 14=12 + 2. Tako da možemo reći
143=(12 + 2)3=(123) + (23)
Prvi dio (123) može se zanemariti! Prelijevanje od 12 sati koji nosi 14 jednostavno se ponavlja nekoliko puta. Ali koga briga? Svejedno ignoriramo preljev.
Množenje
Prilikom množenja bitan je samo ostatak, odnosno ista 2 sata za 14:00 i 2:00. Intuitivno, ovako vidim kako množenje ne mijenja odnos s modularnom matematikom (možete pomnožiti obje strane modularnog odnosa i dobiti isti rezultat).
Radimo to intuitivno, ali lijepo je dati mu ime. Imate let koji stiže u 15 sati. Onkasni 14 sati. U koliko će sati sletjeti?
14 ≡ 2 mod 12. Dakle, zamislite to kao 2 sata, tako da će zrakoplov sletjeti u 5 sati ujutro. Rješenje je jednostavno: 3 + 2=5 ujutro. Ovo je malo kompliciranije od jednostavne modulo operacije, ali princip je isti.
