Matemaatikas on moodularitmeetika täisarvude arvutussüsteem, mille abil need teatud väärtuse – mooduli (või nende mitmuse) – saavutamisel "pööravad ümber". Kaasaegse lähenemise sedalaadi teadusele töötas välja Carl Friedrich Gauss oma 1801. aastal avaldatud teoses Disquisitiones Arithmeticae. Arvutiteadlastele meeldib seda meetodit väga kasutada, kuna see on väga huvitav ja avab arvudega tehtes teatud uusi võimalusi.
Essence
Kuna tundide arv algab uuesti pärast seda, kui see jõuab 12-ni, on see aritmeetiline moodul 12. Alloleva definitsiooni kohaselt ei vasta 12 mitte ainult 12-le, vaid ka 0-le, seega võib nimetada ka kellaaega nimega " 12:00". "0:00". Lõppude lõpuks on 12 sama mis 0 moodul 12.
Modulaarset aritmeetikat saab töödelda matemaatiliselt, juurutades täisarvude kongruentse seose, mis ühildub täisarvudega tehtavate toimingutegaarvud: liitmine, lahutamine ja korrutamine. Positiivse täisarvu n korral öeldakse, et kaks arvu a ja b on mooduli n kongruentsed, kui nende erinevus a - b on arvu n kordne (st kui on olemas täisarv k, mille korral a - b=kn).
Mahaarvamised
Teoreetilises matemaatikas on moodularitmeetika üks arvuteooria aluseid, mis mõjutab peaaegu kõiki selle uurimise aspekte ning seda kasutatakse laialdaselt ka rühmade, rõngaste, sõlmede ja abstraktse algebra teoorias. Rakendusmatemaatika valdkonnas kasutatakse seda arvutialgebras, krüptograafias, arvutiteaduses, keemias, kujutavas kunstis ja muusikas.
Harjutamine
Väga praktiline rakendus on seerianumbrite identifikaatorites olevate kontrollsummade arvutamine. Näiteks kasutavad mõned levinud raamatustandardid aritmeetikamoodulit 11 (kui see on välja antud enne 1. jaanuari 2007) või moodulit 10 (kui see on välja antud enne või pärast 1. jaanuari 2007). Samamoodi näiteks rahvusvahelistes pangakontonumbrites (IBAN). See kasutab mooduli 97 aritmeetikat, et tuvastada pangakonto numbrites kasutaja sisestusvigu.
Keemias on CAS-i registreerimisnumbri (iga keemilise ühendi kordumatu identifitseerimisnumber) viimane number kontrollnumber. See arvutatakse nii, et CAS-i registreerimisnumbri kahe esimese osa viimane number korrutatakse 1-ga, eelmine number 2 korda, eelmine number 3 korda jne, liidetakse kõik kokku ja arvutatakse summa moodul 10.
Mis on krüptograafia? Fakt on see, etsellel on väga tugev seos käsitletava teemaga. Krüptograafias on modulaarse aritmeetika seadused otseselt aluseks avaliku võtmega süsteemidele, nagu RSA ja Diffie-Hellman. Siin annab see elliptiliste kõverate aluseks olevad lõplikud väljad. Kasutatakse erinevates sümmeetrilise võtmega algoritmides, sealhulgas täiustatud krüpteerimisstandardis (AES), rahvusvahelises andmete krüptimise algoritmis ja RC4-s.
Rakendus
Seda meetodit kasutatakse piirkondades, kus on vaja numbreid lugeda. Selle töötasid välja matemaatikud ja kõik kasutavad seda, eriti arvutiteadlased. See on hästi dokumenteeritud sellistes raamatutes nagu Modular Aithmetic for Dummies. Mitmed eksperdid soovitavad aga sellist kirjandust mitte tõsiselt võtta.
Arvutiteaduses kasutatakse modulaarset aritmeetikat sageli bittide kaupa ja muudes operatsioonides, mis hõlmavad fikseeritud laiusega ümmargusi andmestruktuure. Analüütikutele meeldib seda kasutada. Modulooperatsiooni rakendatakse paljudes programmeerimiskeeltes ja kalkulaatorites. Antud juhul on see üks näide sellisest rakendusest. Programmeerimisel kasutatakse ka moodulite võrdlemist, jäägiga jagamist ja muid nippe.
Muusikas kasutatakse aritmeetilist moodulit 12, kui vaadeldakse kaheteistkümne tooniga võrdse temperamendi süsteemi, milles oktav ja enharmoonia on samaväärsed. Teisisõnu, klahvid vahekorras 1-2 või 2-1 on samaväärsed. Muusikas ja muudes humanitaarteadustes on aritmeetikal üsna märkimisväärne roll, aga õpikutesarvutiteadlased tavaliselt sellest ei kirjuta.
Üheksade vähendamise meetod
9s teisendusmeetod võimaldab kiiresti kontrollida käsitsi kümnendarvu aritmeetilisi arvutusi. See põhineb moodularitmeetilisel moodulil 9 ja eelkõige otsustaval omadusel 10 10 1.
näiteid on teisigi. Aritmeetikamoodulit 7 kasutatakse algoritmides, mis määravad konkreetse kuupäeva nädalapäeva. Eelkõige kasutavad Zelleri kongruents ja Doomsday algoritm palju aritmeetilist moodulit 7.
Muud rakendused
Seda on juba öeldud modulaararitmeetika kohta krüptograafias. Selles vallas on ta lihts alt asendamatu. Üldisem alt leiab moodularitmeetika rakendusi ka sellistes distsipliinides nagu õigus, majandus (näiteks mänguteooria) ja teistes sotsia alteaduste valdkondades. Teisisõnu, kus ressursside proportsionaalne jaotus ja jaotus mängib suurt rolli.
Kuna moodularitmeetikal on nii lai kasutusala, on oluline teada, kui keeruline on võrdlussüsteemi lahendada. Lineaarset kongruentside süsteemi saab lahendada polünoomilises ajas Gaussi eliminatsiooni vormis. Seda kirjeldab täpsem alt lineaarkongruentsusteoreem. Samuti on olemas sellised algoritmid nagu Montgomery reduktsioon, mis võimaldavad lihtsaid aritmeetilisi toiminguid tõhus alt sooritada. Näiteks korrutamise ja astendamise modulo n, suurte arvude puhul. Seda on väga oluline teada, et mõista, midakrüptograafia. Lõppude lõpuks töötab see lihts alt sarnaste toimingutega.
Congruence
Mõned toimingud, nagu diskreetse logaritmi või ruutkongruentsi leidmine, tunduvad olevat sama keerulised kui täisarvude faktoriseerimine ja seega on need krüptoalgoritmide ja krüptimise lähtepunktiks. Need probleemid võivad olla NP-kesksed.
Näited
Järgnevad kolm üsna kiiret C-funktsiooni – kaks modulaarseks korrutamiseks ja üks moodularvudeks tõstmiseks kuni 63-bitiste märgita täisarvude jaoks ilma mööduva ülevooluta.
Varsti pärast täisarvude (1, 2, 3, 4, 5…) avastamist selgub, et need jagunevad kahte rühma:
- Paaris: jagub 2-ga (0, 2, 4, 6..).
- Paaritu: ei jagu 2-ga (1, 3, 5, 7…).
Miks see eristamine oluline on? See on abstraktsiooni algus. Märkame arvu omadusi (nt paaris või paaritu), mitte ainult arvu ennast ("37").
See võimaldab meil uurida matemaatikat sügavamal tasemel ja leida seoseid numbritüüpide, mitte konkreetsete arvutüüpide vahel.
Arvu omadused
Olla "kolm" on vaid üks numbri omadus. Võib-olla pole see kohe nii kasulik kui paaris/paaritu, kuid see on olemas. Saame luua reegleid nagu "kolmteist x kolm veeni=kolmteist" ja nii edasi. Aga see on hull. Me ei saa kogu aeg uusi sõnu luua.
Modulooperatsioon (paljudes programmeerimiskeeltes lühendatult mod või "%") on ülejäänud osa, kuijaotus. Näiteks "5 mod 3=2", mis tähendab, et 2 on jääk, kui jagate 5 3-ga.
Igapäevaste terminite teisendamisel matemaatikaks on "paarisarv", kus see on "0 mod 2", mis tähendab, et jääk on 0, kui jagatakse 2-ga. Paaritu arv on "1 mod 2" (sisaldab jääki 1-st).
Paaris ja paaritud numbrid
Mis on paaris x paaris x paaritu x paaritu? Noh, see on 0 x 0 x 1 x 1=0. Tegelikult näete, kas paarisarv on kuskil korrutatud, kus kogu tulemus on null.
Modulaarse matemaatika nipp seisneb selles, et oleme seda juba aja salvestamiseks kasutanud – mõnikord nimetatakse seda ka kella aritmeetikaks.
Näiteks: 7:00 (am/pm – vahet pole). Kus on tunniosuti 7 tunni pärast?
Modulatsioonid
(7 + 7) mod 12=(14) mod 12=2 mod 12 [2 on jääk, kui 14 jagatakse 12-ga. Võrrand 14 mod 12=2 mod 12 tähendab 14 tundi ja 2 tundi sama 12-tunnisel kellal. Need on kongruentsed, tähistatud kolmekordse võrdusmärgiga: 14 ≡ 2 mod 12.
Veel üks näide: kell on 8.00. Kus on suur jaotus 25 tunni pärast?
Selle asemel, et lisada 25 kuni 8, saate aru, et 25 tundi on lihts alt "1 päev + 1 tund". Vastus on lihtne. Seega lõpeb kell 1 tund ette – kell 9:00.
(8 + 25) mod 12 ≡ (8) mod 12 + (25) mod 12 ≡ (8) mod 12 + (1) mod 12 ≡ 9 mod 12. Teisendasite intuitiivselt 25 1-ks ja lisasite selle kuni 8.
Kasutades kella analoogina, saame aru saada, kasmoodularitmeetika reeglid ja need töötavad.
Liitmine/lahutamine
Oletame, et kaks korda näevad meie kella järgi ühesugused ("2:00" ja "14:00"). Kui lisame mõlemale samad x tundi, mis juhtub? No need vahetuvad kella peal sama summa eest! 2:00 + 5 tundi ≡ 14:00 + 5 tundi – mõlemad näitavad 7:00.
Miks? Võime lihts alt lisada 5 kahele jäägile, mis mõlemal on, ja need liiguvad edasi samal viisil. Kõigi kongruentssete arvude (2 ja 14) korral on liitmisel ja lahutamisel sama tulemus.
On raskem teada, kas korrutamine jääb samaks. Kui 14 ≡ 2 (mod 12), kas saame mõlemad arvud korrutada ja saada sama tulemuse? Vaatame, mis juhtub, kui korrutame 3-ga.
Noh, 2:003 × 6:00. Aga mis on 14:003?
Pidage meeles, 14=12 + 2. Seega võime öelda
143=(12 + 2)3=(123) + (23)
Esimese osa (123) võib ignoreerida! 12-tunnine ülevool, mis kannab 14, kordub lihts alt mitu korda. Aga keda huvitab? Me ignoreerime ületäitumist niikuinii.
Korrutamine
Korrutamisel loeb ainult jääk, st sama 2 tundi kella 14:00 ja 2:00 jaoks. Intuitiivselt näen ma nii, et korrutamine ei muuda seost modulaarse matemaatikaga (saate korrutada moodulseose mõlemad pooled ja saada sama tulemuse).
Teeme seda intuitiivselt, kuid hea on sellele nimi anda. Teie lend saabub kell 15.00. Tahilineb 14 tundi. Mis kell see maandub?
14 ≡ 2 mod 12. Niisiis, mõelge sellele kui kella kahele, nii et lennuk maandub kell 5 hommikul. Lahendus on lihtne: 3 + 2=5 hommikul. See on veidi keerulisem kui lihtne mooduloperatsioon, kuid põhimõte on sama.
