U matematici, modularna aritmetika je računski sistem za cijele brojeve, uz pomoć kojih se oni "okreću" kada dostignu određenu vrijednost - modul (ili množinu njih). Savremeni pristup ovoj vrsti nauke razvio je Carl Friedrich Gauss u svojoj Disquisitiones Arithmeticae objavljenoj 1801. Informatičari veoma vole da koriste ovu metodu, jer je veoma zanimljiva i otvara određene nove mogućnosti u operacijama sa brojevima.
Essence
Pošto broj sati počinje ponovo nakon što dostigne 12, to je aritmetički modul 12. Prema definiciji ispod, 12 odgovara ne samo 12, već i 0, tako da se može imenovati i vrijeme koje se zove " 12:00". "0:00". Na kraju krajeva, 12 je isto što i 0 po modulu 12.
Modularna aritmetika se može obraditi matematički uvođenjem kongruentne relacije na cijele brojeve koja je kompatibilna s operacijama na cijelim brojevimabrojevi: sabiranje, 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 utiče na skoro sve aspekte njenog proučavanja, a takođe se široko koristi u teoriji grupa, prstenova, čvorova i apstraktne algebre. U oblasti primenjene matematike koristi se u kompjuterskoj algebri, kriptografiji, informatici, hemiji, vizuelnoj umetnosti i muzici.
Vježba
Veoma praktična primena je izračunavanje kontrolnih suma u identifikatorima serijskih brojeva. Na primjer, neki uobičajeni standardi za knjige koriste aritmetički modul 11 (ako je objavljen prije 1. januara 2007.) ili modul 10 (ako je objavljen prije ili poslije 1. januara 2007.). Slično, na primjer, u međunarodnim brojevima bankovnih računa (IBAN). Ovo koristi modulo 97 aritmetiku za otkrivanje korisničkih grešaka u unosu u brojevima bankovnih računa.
U hemiji, zadnja cifra CAS registracijskog broja (jedinstveni identifikacioni broj za svako hemijsko jedinjenje) je kontrolna cifra. Izračunava se tako što se posljednja znamenka prva dva dijela CAS registarskog broja pomnoži sa 1, prethodna cifra 2 puta, prethodna cifra 3 puta, itd., sabere se sve i izračuna zbir po modulu 10.
Šta je kriptografija? Činjenica je daima vrlo jaku vezu sa temom o kojoj se raspravlja. U kriptografiji, zakoni modularne aritmetike direktno su u osnovi sistema javnih ključeva kao što su RSA i Diffie-Hellman. Ovdje daje konačna polja koja leže u osnovi eliptičkih krivulja. Koristi se u različitim 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 i svi ga koriste, a posebno informatičari. Ovo je dobro dokumentovano u knjigama poput Modularne aritmetike za lutke. Međutim, brojni stručnjaci preporučuju da se ovakva literatura ne shvaća ozbiljno.
U informatici, modularna aritmetika se često koristi u bitovima 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. Modulo poređenje, deljenje sa ostatkom i drugi trikovi se takođe koriste u programiranju.
U muzici, aritmetički modulo 12 se koristi kada se razmatra sistem 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 muzici i drugim humanističkim naukama aritmetika igra prilično značajnu ulogu, ali u udžbenicimainformatičari obično ne pišu o tome.
Metoda smanjivanja devetki
Metoda konverzije 9s nudi brzu provjeru ručnih decimalnih aritmetičkih izračunavanja. Zasnovan je na modularnoj aritmetici po modulu 9, a posebno na odlučujućem svojstvu 10 10 1.
ima i drugih primjera. Aritmetika po modulu 7 se koristi u algoritmima koji određuju dan u sedmici za određeni datum. Posebno, Zellerova kongruencija i algoritam Sudnjeg dana u velikoj mjeri koriste aritmetiku po modulu 7.
Ostale aplikacije
Već je rečeno o modularnoj aritmetici u kriptografiji. U ovoj oblasti jednostavno je nezamjenjiva. Općenito, modularna aritmetika također nalazi primjenu u disciplinama kao što su pravo, ekonomija (kao što je teorija igara) i druge oblasti društvenih nauka. Drugim riječima, gdje proporcionalna podjela i raspodjela resursa igra glavnu ulogu.
Budući da modularna aritmetika ima tako širok spektar primjena, važno je znati koliko je teško riješiti sistem poređenja. Linearni sistem podudarnosti može se riješiti u polinomskom vremenu u obliku Gausove eliminacije. Ovo je detaljnije opisano teoremom linearne kongruencije. Algoritmi kao što je Montgomeryjeva redukcija također postoje kako bi omogućili efikasno izvođenje jednostavnih aritmetičkih operacija. Na primjer, množenje i stepenovanje po modulu n, za velike brojeve. Ovo je veoma važno znati da biste razumeli štakriptografija. Uostalom, radi samo sa sličnim operacijama.
kongruencija
Neke operacije, kao što je pronalaženje diskretnog logaritma ili kvadratne kongruencije, izgledaju kao složene kao i faktorizacija cijelih brojeva i stoga su polazna tačka za kriptografske algoritme i šifriranje. 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čigledno da su podijeljeni u dvije grupe:
- Par: djeljivo sa 2 (0, 2, 4, 6..).
- Neparno: nije djeljivo sa 2 (1, 3, 5, 7…).
Zašto je ova razlika važna? Ovo je početak apstrakcije. Primećujemo svojstva broja (npr. paran ili neparan), a ne samo sam broj ("37").
Ovo nam omogućava da istražujemo matematiku na dubljem nivou i pronađemo odnose između tipova brojeva, a ne specifičnih.
Svojstva broja
Biti "tri" je samo još jedno svojstvo broja. Možda nije tako odmah korisno kao parno/neparno, ali postoji. Možemo kreirati 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 kadadivizije. Na primjer, "5 mod 3=2", što znači da je 2 ostatak kada podijelite 5 sa 3.
Kada konvertujete svakodnevne termine u matematiku, "parni broj" je tamo gde je "0 mod 2", što znači da je ostatak 0 kada se podeli sa 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 da li je paran broj pomnožen bilo gdje, gdje će cijeli rezultat biti nula.
Trik s modularnom matematikom je u tome što 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 sa 12. Jednačina 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 konvertovali 25 u 1 i dodali ovo do 8.
Koristeći sat kao analogiju, možemo shvatiti da li jepravila modularne aritmetike, i ona rade.
Sabiranje/Oduzimanje
Recimo da dva puta izgledaju isto na našem satu ("2:00" i "14:00"). Ako na oba dodamo isto x sati, šta će se dogoditi? Pa, mijenjaju se za isti iznos na satu! 2:00 + 5 sati ≡ 14:00 + 5 sati - oba će pokazati 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), sabiranje i oduzimanje imaju isti rezultat.
Teže je znati da li množenje ostaje isto. Ako je 14 ≡ 2 (mod 12), možemo li pomnožiti oba broja i dobiti isti rezultat? Hajde da vidimo šta se dešava kada pomnožimo sa 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) se može zanemariti! Prelijevanje od 12 sati koje nosi 14 jednostavno se ponavlja nekoliko puta. Ali koga briga? Svejedno ignoriramo prelijevanje.
Množenje
Prilikom množenja bitan je samo ostatak, odnosno ista 2 sata za 14:00 i 2:00. Intuitivno, ovako vidim da 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 koje vrijeme će sletjeti?
14 ≡ 2 mod 12. Dakle, zamislite to kao 2 sata, tako da će avion sletjeti u 5 sati ujutro. Rješenje je jednostavno: 3 + 2=5 ujutro. Ovo je malo komplikovanije od jednostavne modulo operacije, ali princip je isti.
