V matematike je modulárna aritmetika výpočtový systém pre celé čísla, pomocou ktorého sa "otočia", keď dosiahnu určitú hodnotu - modul (alebo ich množné číslo). Moderný prístup k tomuto druhu vedy vyvinul Carl Friedrich Gauss vo svojej práci Disquisitiones Arithmeticae publikovanej v roku 1801. Počítačoví vedci túto metódu veľmi radi používajú, pretože je veľmi zaujímavá a otvára určité nové možnosti v operáciách s číslami.
Essence
Keďže počet hodín začína znova po dosiahnutí 12, ide o aritmetický modulo 12. Podľa nižšie uvedenej definície 12 zodpovedá nielen 12, ale aj 0, takže čas možno pomenovať aj ako „ 12:00". "0:00". Koniec koncov, 12 je to isté ako 0 modulo 12.
Modulárna aritmetika môže byť spracovaná matematicky zavedením kongruentného vzťahu k celým číslam, ktorý je kompatibilný s operáciami na celých číslachčísla: sčítanie, odčítanie a násobenie. Pre kladné celé číslo n sa hovorí, že dve čísla a a b sú zhodné modulo n, ak ich rozdiel a - b je násobkom n (to znamená, ak existuje celé číslo k také, že a - b=kn).
Zrážky
V teoretickej matematike je modulárna aritmetika jedným zo základov teórie čísel, ktorá ovplyvňuje takmer všetky aspekty jej štúdia, a je tiež široko používaná v teórii grúp, kruhov, uzlov a abstraktnej algebry. V oblasti aplikovanej matematiky sa používa v počítačovej algebre, kryptografii, informatike, chémii, výtvarnom umení a hudbe.
Cvičenie
Veľmi praktickou aplikáciou je výpočet kontrolných súčtov v identifikátoroch sériového čísla. Napríklad niektoré bežné knižné štandardy používajú aritmetický modulo 11 (ak bol vydaný pred 1. januárom 2007) alebo modulo 10 (ak bol vydaný pred alebo po 1. januári 2007). Podobne napríklad v medzinárodných číslach bankových účtov (IBAN). Toto používa aritmetiku modulo 97 na zisťovanie chýb zadávania používateľov v číslach bankových účtov.
V chémii je kontrolnou číslicou posledná číslica registračného čísla CAS (jedinečné identifikačné číslo pre každú chemickú zlúčeninu). Vypočíta sa tak, že sa posledná číslica z prvých dvoch častí registračného čísla CAS vynásobí 1, predchádzajúca číslica 2 krát, predchádzajúca číslica 3 krát atď., všetko sa sčíta a vypočíta sa súčet modulo 10.
Čo je kryptografia? Faktom je, žemá veľmi silné spojenie s diskutovanou témou. V kryptografii sú zákony modulárnej aritmetiky priamo základom systémov verejného kľúča, ako sú RSA a Diffie-Hellman. Tu poskytuje konečné polia, ktoré sú základom eliptických kriviek. Používa sa v rôznych algoritmoch symetrických kľúčov vrátane Advanced Encryption Standard (AES), International Data Encryption Algorithm a RC4.
Aplikácia
Táto metóda sa používa v oblastiach, kde potrebujete čítať čísla. Vyvinuli ho matematici a používajú ho všetci, najmä informatici. Toto je dobre zdokumentované v knihách ako Modular Arithmetic for Dummies. Viacerí odborníci však odporúčajú nebrať takúto literatúru vážne.
V informatike sa modulárna aritmetika často používa v bitových a iných operáciách zahŕňajúcich kruhové dátové štruktúry s pevnou šírkou. Analytici to radi používajú. Operácia modulo je implementovaná v mnohých programovacích jazykoch a kalkulačkách. V tomto prípade je to jeden z príkladov takejto aplikácie. Pri programovaní sa používa aj porovnávanie modulov, delenie so zvyškom a iné triky.
V hudbe sa aritmetický modulo 12 používa pri uvažovaní o systéme rovnakého temperamentu dvanástich tónov, v ktorom sú oktáva a enharmonika ekvivalentné. Inými slovami, kľúče v pomere 1-2 alebo 2-1 sú ekvivalentné. V hudbe a iných humanitných vedách hrá aritmetika dosť významnú úlohu, ale v učebniciachinformatici o tom zvyčajne nepíšu.
Metóda redukcie deviatok
Metóda 9s prevodu ponúka rýchlu kontrolu manuálnych desiatkových aritmetických výpočtov. Je založený na modulárnej aritmetike modulo 9 a najmä na rozhodujúcej vlastnosti 10 10 1.
sú aj iné príklady. Aritmetický modulo 7 sa používa v algoritmoch, ktoré určujú deň v týždni pre konkrétny dátum. Najmä Zellerova kongruencia a algoritmus Doomsday vo veľkej miere využívajú aritmetický modulo 7.
Iné aplikácie
O modulárnej aritmetike v kryptografii už bolo povedané. V tejto oblasti je jednoducho nenahraditeľná. Všeobecnejšie povedané, modulárna aritmetika nachádza uplatnenie aj v disciplínach ako právo, ekonómia (ako je teória hier) a iných oblastiach spoločenských vied. Inými slovami, kde proporcionálne rozdelenie a rozdelenie zdrojov zohráva hlavnú úlohu.
Keďže modulárna aritmetika má tak široké využitie, je dôležité vedieť, aké ťažké je vyriešiť systém porovnávania. Lineárny systém kongruencií je možné riešiť v polynomiálnom čase formou Gaussovej eliminácie. Podrobnejšie to popisuje veta o lineárnej kongruencii. Existujú aj algoritmy, ako napríklad Montgomeryho redukcia, ktoré umožňujú efektívne vykonávanie jednoduchých aritmetických operácií. Napríklad násobenie a umocňovanie modulo n pre veľké čísla. Toto je veľmi dôležité vedieť, aby ste pochopili čokryptografia. Predsa len to funguje s podobnými operáciami.
Kongruencia
Niektoré operácie, ako je nájdenie diskrétneho logaritmu alebo kvadratickej kongruencie, sa zdajú byť také zložité ako faktorizácia celého čísla, a preto sú východiskovým bodom pre kryptografické algoritmy a šifrovanie. Tieto problémy môžu byť stredného stupňa NP.
Príklady
Nasledujú tri pomerne rýchle funkcie C – dve na vykonávanie modulárneho násobenia a jedna na zvýšenie na modulárne čísla pre celé čísla bez znamienka až do 63 bitov, bez prechodného pretečenia.
Krátko po objavení celých čísel (1, 2, 3, 4, 5…) je zrejmé, že sú rozdelené do dvoch skupín:
- Párne: deliteľné 2 (0, 2, 4, 6..).
- Nepárne: nie je deliteľné 2 (1, 3, 5, 7…).
Prečo je toto rozlíšenie dôležité? Toto je začiatok abstrakcie. Všímame si vlastnosti čísla (napr. párne alebo nepárne) a nielen samotné číslo („37“).
To nám umožňuje preskúmať matematiku na hlbšej úrovni a nájsť vzťahy medzi typmi čísel, a nie medzi konkrétnymi.
Vlastnosti čísla
Byť „trojkou“je len ďalšou vlastnosťou čísla. Možno nie tak okamžite užitočné ako párne/nepárne, ale je to tam. Môžeme vytvárať pravidlá ako „trinásť x tri žily=trinásť“a podobne. Ale je to šialené. Nemôžeme stále vytvárať nové slová.
Operácia modulo (v mnohých programovacích jazykoch skratka mod alebo "%") je zvyšok, keďdivízie. Napríklad „5 mod 3=2“, čo znamená, že 2 je zvyšok, keď 5 vydelíte 3.
Pri prevode bežných pojmov na matematiku je „párne číslo“tam, kde je „0 mod 2“, čo znamená, že zvyšok je 0 pri delení 2. Nepárne číslo je „1 mod 2“(má zvyšok z 1).
Párne a nepárne čísla
Čo je párne x párne x nepárne x nepárne? No, je to 0 x 0 x 1 x 1=0. V skutočnosti môžete vidieť, či sa kdekoľvek vynásobí párne číslo, pričom celý výsledok bude nula.
Trik s modulárnou matematikou je v tom, že sme ju už použili na ukladanie času – niekedy nazývané aj „hodinová aritmetika“.
Napríklad: 7:00 (am/pm – nezáleží). Kde bude hodinová ručička o 7 hodín?
Modulácie
(7 + 7) mod 12=(14) mod 12=2 mod 12 [2 je zvyšok, keď 14 je delené 12. Rovnica 14 mod 12=2 mod 12 znamená 14 hodín a 2 hodiny. to isté v 12-hodinovom formáte. Sú zhodné, označené trojitým znamienkom rovnosti: 14 ≡ 2 mod 12.
Ďalší príklad: je 8:00. Kde bude veľká ruka o 25 hodín?
Namiesto pridávania 25 k 8 môžete pochopiť, že 25 hodín je len „1 deň + 1 hodina“. Odpoveď je jednoduchá. Hodiny sa teda skončia o 1 hodinu dopredu – o 9:00.
(8 + 25) mod 12 ≡ (8) mod 12 + (25) mod 12 ≡ (8) mod 12 + (1) mod 12 ≡ 9 mod 12. Intuitívne ste skonvertovali 25 na 1 a pridali toto do 8.
Pomocou hodín ako analógie môžeme zistiť, čipravidlá modulárnej aritmetiky a fungujú.
Sčítanie/odčítanie
Povedzme, že dva časy vyzerajú na našich hodinách rovnako („2:00“a „14:00“). Ak k obom pripočítame rovnakých x hodín, čo sa stane? No na hodinách menia za rovnakú sumu! 2:00 + 5 hodín ≡ 14:00 + 5 hodín – obe ukážu 7:00.
Prečo? K dvom zvyškom, ktoré majú obaja, môžeme jednoducho pridať 5 a postupujú rovnakým spôsobom. Pre všetky zhodné čísla (2 a 14) má sčítanie a odčítanie rovnaký výsledok.
Je ťažšie vedieť, či násobenie zostane rovnaké. Ak 14 ≡ 2 (mod 12), môžeme vynásobiť obe čísla a dostať rovnaký výsledok? Uvidíme, čo sa stane, keď vynásobíme 3.
No, 2:003 × 6:00. Ale koľko je 14:003?
Pamätajte, 14=12 + 2. Takže môžeme povedať
143=(12 + 2)3=(123) + (23)
Prvú časť (123) môžete ignorovať! Prekročenie 12 hodín, ktoré nesie 14, sa jednoducho opakuje niekoľkokrát. Ale koho to zaujíma? Pretečenie aj tak ignorujeme.
Násobenie
Pri násobení záleží len na zvyšku, teda na rovnakých 2 hodinách o 14:00 a 2:00. Intuitívne takto vidím, že násobenie nemení vzťah s modulárnou matematikou (môžete vynásobiť obe strany modulárneho vzťahu a získať rovnaký výsledok).
Robíme to intuitívne, ale je pekné dať tomu názov. Máte let s príletom o 15:00. Onmeškanie o 14 hodín. Kedy pristane?
14 ≡ 2 mod 12. Predstavte si to ako 2 hodiny, takže lietadlo pristane o 5:00 ráno. Riešenie je jednoduché: 3 + 2=5 hodín ráno. Je to o niečo zložitejšie ako jednoduchá operácia modulo, ale princíp je rovnaký.
