Matematikoje modulinė aritmetika yra sveikųjų skaičių skaičiavimo sistema, kurios pagalba jie „apverčia“pasiekę tam tikrą reikšmę – modulį (arba jų daugiskaitą). Šiuolaikinį požiūrį į tokio pobūdžio mokslą sukūrė Carlas Friedrichas Gaussas savo knygoje „Disquisitiones Arithmeticae“, išleistoje 1801 m. Informatikai labai mėgsta naudoti šį metodą, nes jis labai įdomus ir atveria tam tikras naujas galimybes atliekant operacijas su skaičiais.
Essence
Kadangi valandų skaičius vėl prasideda pasiekus 12, tai yra aritmetinis modulis 12. Pagal toliau pateiktą apibrėžimą 12 atitinka ne tik 12, bet ir 0, todėl galima pavadinti ir laiką, vadinamą " 12:00". "0:00". Juk 12 yra tas pats, kas 0 modulo 12.
Modulinė aritmetika gali būti apdorojama matematiškai įvedant kongruentinį ryšį su sveikaisiais skaičiais, suderinamą su operacijomis su sveikaisiais skaičiaisskaičiai: sudėtis, atimtis ir daugyba. Teigiamajam sveikajam skaičiui n sakoma, kad du skaičiai a ir b yra vienodi modulio n, jei jų skirtumas a - b yra n kartotinis (tai yra, jei yra sveikasis skaičius k, kad a - b=kn).
Išskaitymai
Teorinėje matematikoje modulinė aritmetika yra vienas iš skaičių teorijos pagrindų, turintis įtakos beveik visiems jos tyrimo aspektams, taip pat plačiai naudojama grupių, žiedų, mazgų ir abstrakčios algebros teorijoje. Taikomosios matematikos srityje jis naudojamas kompiuterinėje algebroje, kriptografijoje, informatikoje, chemijoje, vaizduojamuosiuose menuose ir muzikoje.
Praktika
Labai praktiškas pritaikymas yra kontrolinių sumų skaičiavimas serijos numerių identifikatoriuose. Pavyzdžiui, kai kuriuose bendruose knygų standartuose naudojamas aritmetikos modulis 11 (jei išleistas iki 2007 m. sausio 1 d.) arba modulo 10 (jei išleistas iki 2007 m. sausio 1 d. arba vėliau). Panašiai, pavyzdžiui, tarptautiniuose banko sąskaitų numeriuose (IBAN). Tam naudojama modulo 97 aritmetika, kad aptiktų vartotojo įvesties klaidas banko sąskaitų numeriuose.
Chemijoje paskutinis CAS registracijos numerio (kiekvieno cheminio junginio unikalaus identifikavimo numerio) skaitmuo yra kontrolinis skaitmuo. Jis apskaičiuojamas paskutinis pirmųjų dviejų CAS registracijos numerio dalių skaitmuo padauginamas iš 1, ankstesnis skaitmuo 2 kartus, ankstesnis skaitmuo 3 kartus ir tt, visa tai sudedama ir apskaičiuojama suma modulo 10.
Kas yra kriptografija? Faktas yra tasjis turi labai stiprų ryšį su aptariama tema. Kriptografijoje modulinės aritmetikos dėsniai yra tiesiogiai grindžiami viešojo rakto sistemomis, tokiomis kaip RSA ir Diffie-Hellman. Čia pateikiami baigtiniai laukai, kuriais grindžiamos elipsinės kreivės. Naudojamas įvairiuose simetriniuose raktų algoritmuose, įskaitant išplėstinį šifravimo standartą (AES), tarptautinį duomenų šifravimo algoritmą ir RC4.
Programa
Šis metodas naudojamas tose srityse, kuriose reikia skaityti skaičius. Jį sukūrė matematikai, juo naudojasi visi, ypač informatikai. Tai gerai aprašyta tokiose knygose kaip „Modulinė aritmetika manekenams“. Tačiau nemažai ekspertų rekomenduoja į tokią literatūrą žiūrėti rimtai.
Kompiuterių moksle modulinė aritmetika dažnai naudojama bitų ir kitose operacijose, susijusiose su fiksuoto pločio apskrito duomenų struktūromis. Analitikai mėgsta ja naudotis. Modulo operacija įgyvendinama daugelyje programavimo kalbų ir skaičiuotuvų. Šiuo atveju tai yra vienas tokios programos pavyzdžių. Programuojant taip pat naudojamas modulių palyginimas, padalijimas su liekana ir kitos gudrybės.
Muzikoje 12 aritmetikos modulis naudojamas, kai kalbama apie vienodo temperamento dvylikos tonų sistemą, kurioje oktava ir enharmonija yra lygiaverčiai. Kitaip tariant, klavišai santykiu 1-2 arba 2-1 yra lygiaverčiai. Muzikoje ir kituose humanitariniuose moksluose aritmetika vaidina gana reikšmingą vaidmenį, tačiau vadovėliuoseinformatikai paprastai apie tai nerašo.
Devynerių mažinimo metodas
Naudojant 9s konvertavimo metodą galima greitai patikrinti neautomatinius dešimtainius aritmetinius skaičiavimus. Jis pagrįstas moduline aritmetine modulio 9 ir ypač lemiama savybe 10 10 1.
yra ir kitų pavyzdžių. Aritmetikos modulis 7 naudojamas algoritmuose, kurie nustato savaitės dieną tam tikrai datai. Visų pirma, Zellerio kongruence ir Doomsday algoritmas naudoja daug aritmetikos modulio 7.
Kitos programos
Tai jau buvo pasakyta apie modulinę aritmetiką kriptografijoje. Šioje srityje ji tiesiog nepakeičiama. Apskritai modulinė aritmetika taip pat pritaikoma tokiose disciplinose kaip teisė, ekonomika (pvz., žaidimų teorija) ir kitose socialinių mokslų srityse. Kitaip tariant, kai proporcingas išteklių padalijimas ir paskirstymas vaidina pagrindinį vaidmenį.
Kadangi modulinė aritmetika yra plačiai naudojama, svarbu žinoti, kaip sunku išspręsti palyginimų sistemą. Tiesinę kongruencijų sistemą galima išspręsti daugianario laiku Gauso eliminacijos forma. Tai išsamiau apibūdina tiesinės kongruencijos teorema. Taip pat egzistuoja tokie algoritmai kaip Montgomery redukcija, leidžiantys efektyviai atlikti paprastas aritmetines operacijas. Pavyzdžiui, daugybos ir eksponencijos modulio n, dideliems skaičiams. Tai labai svarbu žinoti, norint suprasti, kąkriptografija. Galų gale, jis veikia tik atliekant panašias operacijas.
Congruence
Kai kurios operacijos, pvz., diskretinio logaritmo ar kvadratinės kongruencijos radimas, atrodo tokios pat sudėtingos kaip sveikųjų skaičių faktorizavimas, todėl yra kriptografinių algoritmų ir šifravimo pradžios taškas. Šios problemos gali būti NP tarpinės.
Pavyzdžiai
Toliau pateikiamos trys gana greitos C funkcijos – dvi, skirtos moduliniam daugybai atlikti, ir viena, skirta didinti iki modulinių skaičių neženkliems sveikiesiems skaičiams iki 63 bitų be trumpalaikio perpildymo.
Netrukus po sveikųjų skaičių (1, 2, 3, 4, 5…) atradimo tampa aišku, kad jie skirstomi į dvi grupes:
- Lyginis: dalijasi iš 2 (0, 2, 4, 6..).
- Nelyginis: nesidalija iš 2 (1, 3, 5, 7…).
Kodėl šis skirtumas svarbus? Tai yra abstrakcijos pradžia. Pastebime skaičiaus ypatybes (pvz., lyginį arba nelyginį), o ne tik patį skaičių ("37").
Tai leidžia mums giliau tyrinėti matematiką ir rasti ryšį tarp skaičių tipų, o ne konkrečių.
Skaičiaus savybės
Būti „trejetu“yra tik dar viena skaičiaus savybė. Galbūt ne taip iš karto naudinga kaip lyginis / nelyginis, bet jis yra. Galime sukurti tokias taisykles kaip „trylika x trys venos=trylika“ir pan. Bet tai beprotiška. Negalime nuolat kurti naujų žodžių.
Modulo operacija (sutrumpintai mod arba "%" daugelyje programavimo kalbų) yra likusi dalis, kaipadalinys. Pavyzdžiui, "5 mod 3=2", o tai reiškia, kad 2 yra likusi dalis, kai 5 dalijate iš 3.
Konvertuojant kasdienius terminus į matematiką, "lyginis skaičius" yra ten, kur jis yra "0 mod 2", o tai reiškia, kad likusioji dalis yra 0, padalyta iš 2. Nelyginis skaičius yra "1 mod 2" (turi likutį iš 1).
Lenginiai ir nelyginiai skaičiai
Kas yra lyginis x lyginis x nelyginis x nelyginis? Na, tai yra 0 x 0 x 1 x 1=0. Tiesą sakant, jūs galite pamatyti, ar lyginis skaičius yra padaugintas kur nors, kur visas rezultatas bus lygus nuliui.
Modulinės matematikos gudrybė ta, kad mes ją jau panaudojome laiko saugojimui – kartais vadinama „laikrodžio aritmetika“.
Pavyzdžiui: 7:00 (am/pm – nesvarbu). Kur bus valandų rodyklė po 7 valandų?
Moduliacijos
(7 + 7) mod 12=(14) mod 12=2 mod 12 [2 yra liekana, kai 14 yra padalintas iš 12. Lygtis 14 mod 12=2 mod 12 reiškia 14 valandų ir 2 valandas atrodo tas pats 12 valandų laikrodyje. Jie yra suderinti, pažymėti trigubu lygybės ženklu: 14 ≡ 2 mod 12.
Kitas pavyzdys: 8:00 val. Kur bus didžiausia ranka po 25 valandų?
Užuot pridėję 25 prie 8, galite suprasti, kad 25 valandos yra tik „1 diena + 1 valanda“. Atsakymas paprastas. Taigi, laikrodis baigsis 1 valanda į priekį – 9:00.
(8 + 25) mod 12 ≡ (8) mod 12 + (25) mod 12 ≡ (8) mod 12 + (1) mod 12 ≡ 9 mod 12. Jūs intuityviai konvertavote 25 į 1 ir pridėjote tai iki 8.
Naudodami laikrodį kaip analogiją, galime išsiaiškinti, armodulinės aritmetikos taisyklės, ir jos veikia.
Sudėjimas/Atimtis
Tarkime, mūsų laikrodyje du kartus atrodo taip pat („2:00“ir „14:00“). Jei prie abiejų pridėsime tas pačias x valandas, kas atsitiks? Na, jie keičiasi už tą pačią sumą laikrodyje! 2:00 + 5 valandos ≡ 14:00 + 5 valandos – abu bus rodomi 7:00.
Kodėl? Galime tiesiog pridėti 5 prie 2 likusių, kurias abu turi, ir jie eina į priekį tokiu pačiu būdu. Visų lygiaverčių skaičių (2 ir 14) sudėties ir atimties rezultatas yra toks pat.
Sunkiau žinoti, ar daugyba išlieka tokia pati. Jei 14 ≡ 2 (mod 12), ar galime padauginti abu skaičius ir gauti tą patį rezultatą? Pažiūrėkime, kas atsitiks, kai padauginsime iš 3.
Na, 2:003 × 6:00. Bet kas yra 14:003?
Atminkite, 14=12 + 2. Taigi galime pasakyti
143=(12 + 2)3=(123) + (23)
Pirmoji dalis (123) gali būti ignoruojama! 12 valandų perpildymas, pernešantis 14, tiesiog kartojasi kelis kartus. Bet kam tai rūpi? Vis tiek nepaisome perpildymo.
Daugyba
Dauginant svarbu tik likusi dalis, tai yra tos pačios 2 valandos 14:00 ir 2:00. Intuityviai matau, kaip daugyba nekeičia ryšio su moduline matematika (galite padauginti abi modulinio ryšio puses ir gauti tą patį rezultatą).
Mes tai darome intuityviai, bet malonu suteikti jam pavadinimą. Jūsų skrydis atvyksta 15 val. Jisatidėtas 14 valandų. Kada nusileis?
14 ≡ 2 mod 12. Taigi įsivaizduokite, kad tai 2 val., taigi lėktuvas nusileis 5 valandą ryto. Sprendimas paprastas: 3 + 2=5 val. Tai šiek tiek sudėtingiau nei paprastas modulinis veiksmas, tačiau principas yra tas pats.
