V matematiki je modularna aritmetika računski sistem za cela števila, s pomočjo katerega se "obrnejo", ko dosežejo določeno vrednost - modul (ali množino le-teh). Sodoben pristop k tovrstni znanosti je razvil Carl Friedrich Gauss v svoji Disquisitiones Arithmeticae, objavljeni leta 1801. Računalniki to metodo zelo radi uporabljajo, saj je zelo zanimiva in odpira določene nove možnosti pri operacijah s številkami.
Essence
Ker se število ur začne znova, potem ko doseže 12, je aritmetično po modulu 12. V skladu s spodnjo definicijo 12 ne ustreza le 12, ampak tudi 0, tako da lahko poimenujemo tudi čas, imenovan " 12:00". "0:00". Konec koncev je 12 enako kot 0 po modulu 12.
Modularno aritmetiko je mogoče obdelati matematično z uvedbo kongruentne relacije do celih števil, ki je združljiva z operacijami nad celimi številištevila: seštevanje, odštevanje in množenje. Za pozitivno celo število n se reče, da sta dve števili a in b skladni po modulu n, če je njuna razlika a - b večkratnik n (to je, če obstaja celo število k, tako da je a - b=kn).
Odbitki
V teoretični matematiki je modularna aritmetika eden od temeljev teorije števil, ki vpliva na skoraj vse vidike njenega preučevanja, pogosto pa se uporablja tudi v teoriji skupin, obročev, vozlov in abstraktne algebre. Na področju uporabne matematike se uporablja v računalniški algebri, kriptografiji, informatiki, kemiji, vizualni umetnosti in glasbi.
vaja
Zelo praktična uporaba je izračun kontrolnih vsot v identifikatorjih serijskih številk. Nekateri običajni knjižni standardi na primer uporabljajo aritmetični modul 11 (če je bil objavljen pred 1. januarjem 2007) ali modul 10 (če je bil izdan pred ali po 1. januarju 2007). Podobno, na primer, v mednarodnih številkah bančnih računov (IBAN). To uporablja aritmetiko modulo 97 za odkrivanje napak pri uporabniškem vnosu v številkah bančnih računov.
V kemiji je zadnja številka registrske številke CAS (enotna identifikacijska številka za vsako kemično spojino) kontrolna številka. Izračuna se tako, da se zadnja številka prvih dveh delov registrske številke CAS pomnoži z 1, prejšnja številka 2-krat, prejšnja številka 3-krat itd., se sešteje in izračuna vsota po modulu 10.
Kaj je kriptografija? Dejstvo je, daima zelo močno povezavo z obravnavano temo. V kriptografiji zakoni modularne aritmetike neposredno temeljijo na sistemih z javnim ključem, kot sta RSA in Diffie-Hellman. Tukaj zagotavlja končna polja, ki so podlaga za eliptične krivulje. Uporablja se v različnih algoritmih simetričnih ključev, vključno z naprednim standardom šifriranja (AES), mednarodnim algoritmom za šifriranje podatkov in RC4.
Prijava
Ta metoda se uporablja na področjih, kjer morate brati številke. Razvili so ga matematiki in vsi ga uporabljajo, še posebej računalničarji. To je dobro dokumentirano v knjigah, kot je Modularna aritmetika za telebane. Vendar pa številni strokovnjaki priporočajo, da takšne literature ne jemljete resno.
V računalništvu se modularna aritmetika pogosto uporablja v bitnih in drugih operacijah, ki vključujejo krožne podatkovne strukture fiksne širine. Analitiki ga radi uporabljajo. Operacija modulo se izvaja v številnih programskih jezikih in kalkulatorjih. V tem primeru je to en primer takšne aplikacije. Pri programiranju se uporabljajo tudi primerjava po modulih, deljenje z ostankom in drugi triki.
V glasbi se aritmetika po modulu 12 uporablja, ko upoštevamo sistem enakega temperamenta dvanajstih tonov, v katerem sta oktava in enharmonik enakovredni. Z drugimi besedami, ključi v razmerju 1-2 ali 2-1 so enakovredni. V glasbi in drugih humanističnih vedah ima aritmetika precej pomembno vlogo, vendar v učbenikihračunalničarji o tem običajno ne pišejo.
Metoda zmanjševanja devetic
Metoda pretvorbe 9s ponuja hitro preverjanje ročnih decimalnih aritmetičnih izračunov. Temelji na modularni aritmetiki po modulu 9 in zlasti na odločilni lastnosti 10 10 1.
so še drugi primeri. Aritmetika po modulu 7 se uporablja v algoritmih, ki določajo dan v tednu za določen datum. Zlasti Zellerjeva skladnost in algoritem Doomsday močno uporabljata aritmetiko po modulu 7.
Druge aplikacije
O modularni aritmetiki v kriptografiji je bilo že rečeno. Na tem področju je preprosto nenadomestljiva. Na splošno se modularna aritmetika uporablja tudi v disciplinah, kot so pravo, ekonomija (kot je teorija iger) in druga področja družbenih ved. Z drugimi besedami, kjer imata sorazmerna delitev in porazdelitev virov glavno vlogo.
Ker ima modularna aritmetika tako širok spekter uporabe, je pomembno vedeti, kako težko je rešiti sistem primerjav. Linearni sistem kongruenc je mogoče rešiti v polinomskem času v obliki Gaussove eliminacije. To podrobneje opisuje linearni kongruenčni izrek. Obstajajo tudi algoritmi, kot je Montgomeryjeva redukcija, ki omogočajo učinkovito izvajanje preprostih aritmetičnih operacij. Na primer, množenje in stopnjevanje po modulu n za velika števila. To je zelo pomembno vedeti, da bi razumeli, kajkriptografija. Navsezadnje deluje samo s podobnimi operacijami.
Skladnost
Nekatere operacije, kot je iskanje diskretnega logaritma ali kvadratne kongruence, se zdijo tako zapletene kot celoštevilska faktorizacija in so zato izhodišče za kriptografske algoritme in šifriranje. Te težave so lahko NP-vmesne.
Primeri
Naslednje so tri dokaj hitre funkcije C - dve za izvajanje modularnega množenja in ena za dvigovanje na modularna števila za nepredznačena cela števila do 63 bitov, brez prehodnega prelivanja.
Kmalu po odkritju celih števil (1, 2, 3, 4, 5…) postane očitno, da so razdeljena v dve skupini:
- Edo: deljivo z 2 (0, 2, 4, 6..).
- Liho: ni deljivo z 2 (1, 3, 5, 7…).
Zakaj je to razlikovanje pomembno? To je začetek abstrakcije. Opazimo lastnosti števila (npr. sodo ali liho) in ne samo števila samo ("37").
To nam omogoča, da matematiko raziščemo na globlji ravni in najdemo razmerja med vrstami številk in ne specifičnimi.
Lastnosti številke
Biti "tri" je le še ena lastnost števila. Morda ni tako takoj uporaben kot sodo/neparno, vendar je tam. Ustvarimo lahko pravila, kot so "trinajst x tri vene=trinajst" in tako naprej. Ampak to je noro. Ne moremo ustvarjati novih besed ves čas.
Modulo operacija (skrajšano mod ali "%" v mnogih programskih jezikih) je preostanek, kodivizije. Na primer, "5 mod 3=2", kar pomeni, da je 2 ostanek, ko 5 delite s 3.
Pri pretvarjanju vsakdanjih izrazov v matematiko je "sodo število" tam, kjer je "0 mod 2", kar pomeni, da je ostanek 0, če ga delimo z 2. Liho število je "1 mod 2" (ima preostanek od 1).
Sodo in liho število
Kaj je sodo x sodo x liho x liho? No, to je 0 x 0 x 1 x 1=0. Pravzaprav lahko vidite, ali je sodo število kjerkoli pomnoženo, kjer bo celoten rezultat nič.
Trik z modularno matematiko je, da smo jo že uporabljali za shranjevanje časa - včasih imenovano "aritmetika ur".
Na primer: 7:00 (am/pm - ni pomembno). Kje bo urni kazalec čez 7 ur?
Modulacije
(7 + 7) mod 12=(14) mod 12=2 mod 12 [2 je ostanek, ko je 14 deljeno z 12. Enačba 14 mod 12=2 mod 12 pomeni 14 ur in 2 uri poglej enako na 12-urni uri. So skladni, označeni s trojnim znakom enakosti: 14 ≡ 2 mod 12.
Še en primer: ura je 8:00. Kje bo velika kombinacija čez 25 ur?
Namesto, da bi dodali 25 k 8, lahko razumete, da je 25 ur samo "1 dan + 1 ura". Odgovor je preprost. Torej, ura se bo končala 1 uro naprej - ob 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 v 1 in dodali to do 8.
Z uro kot analogijo lahko ugotovimo, ali jepravila modularne aritmetike in delujejo.
Seštevanje/odštevanje
Recimo, da sta dvakrat enaka na naši uri ("2:00" in "14:00"). Če obema dodamo enakih x ur, kaj se zgodi? No, menjajo se za isti znesek na uri! 2:00 + 5 ur ≡ 14:00 + 5 ur - obe bosta pokazali 7:00.
Zakaj? 2 ostankoma, ki ju imata oba, lahko preprosto dodamo 5 in napredujeta na enak način. Za vsa skladna števila (2 in 14) imata seštevanje in odštevanje enak rezultat.
Težje je vedeti, ali množenje ostane enako. Če je 14 ≡ 2 (mod 12), ali lahko pomnožimo obe številki in dobimo enak rezultat? Poglejmo, kaj se zgodi, ko pomnožimo s 3.
No, 2:003 × 6:00. Toda kaj je 14:003?
Zapomni si, 14=12 + 2. Tako lahko rečemo
143=(12 + 2)3=(123) + (23)
Prvi del (123) je mogoče prezreti! Prelivanje 12 ur, ki nosi 14, se preprosto ponovi večkrat. Ampak koga briga? Prelivanje vseeno prezremo.
Množenje
Pri množenju je pomemben samo preostanek, torej enaki 2 uri za 14.00 in 2.00. Intuitivno tako vidim, da množenje ne spremeni razmerja z modularno matematiko (lahko pomnožite obe strani modularnega odnosa in dobite enak rezultat).
To delamo intuitivno, vendar je lepo, če mu damo ime. Let imate ob 15. uri. onzamuja za 14 ur. Kdaj bo pristal?
14 ≡ 2 mod 12. Torej, pomislite na to kot na 2. uri, torej bo letalo pristalo ob 5. uri zjutraj. Rešitev je preprosta: 3 + 2=5 zjutraj. To je nekoliko bolj zapleteno kot preprosta modulo operacija, vendar je princip enak.
