Čo je modulo?
V matematike a výpočtovej praxi označuje operácia modulo zvyčajne zvyšok po celočíselnom delení. Pre dve celé čísla a a n (n > 0) hovoríme, že a mod n je zvyšok r z delenia a : n, teda také celé r so 0 ≤ r < n, že existuje celé q s a = q·n + r. Tiež sa často používa symbolika kongruencie: a ≡ r (mod n) znamená, že n delí rozdiel a − r.
Definícia, notácia a záporné hodnoty
Štandardná matematická definícia vyžaduje nezáporný zvyšok v intervale od 0 do n−1. Pri praktickom použití však existujú rôzne konvencie pre záporné operandy: niektoré definície vždy vracajú nezáporný zvyšok (euclidovský prístup), iné definície ponechávajú znamienko po delení podľa vlastností prostredia. To znamená, že výraz 17 mod 5 = 2 je jednoznačný, ale výraz ako -3 mod 4 môže byť podľa konvencie interpretovaný rôzne; preto sa pri implementácii v softvéri odporúča pozrieť si dokumentáciu príslušného programovacieho jazyka alebo výpočtového prostredia.
Konvencie v počítačoch a kalkulačkách
V prostredí počítačov a kalkulačiek je správanie operátora modulo závislé od implementácie procesora, kompilátora alebo knižníc. Preto pri prenose algoritmov medzi platformami treba brať do úvahy, či výsledok pre záporné čísla bude normalizovaný na nezáporný zvyšok, alebo či sa bude riadiť inou konvenciou (napr. podľa smeru zaokrúhľovania kvocientu). Hardvérové a jazykové špecifikácie (pozri dokumentáciu k hardvéru a jazykom) popisujú detailné pravidlá správania.
Vlastnosti a pravidlá
- Kongruencia: a ≡ b (mod n) práve vtedy, keď n | (a − b).
- Kompatibilita s operáciami: (a + b) mod n = ((a mod n) + (b mod n)) mod n, podobne pre násobenie.
- Existencia modulárneho inverzu: prvok a má inverzný prvok modulo n práve ak gcd(a,n) = 1; inverzný prvok sa nájde rozšíreným Euklidovským algoritmom.
Tieto vlastnosti sú základom pre prácu s triedami zvyškov a umožňujú efektívne redukovať medzivýsledky pri výpočtoch, takže výpočty s veľmi veľkými číslami (napr. pri modularnej exponentiácii) zostávajú prakticky realizovateľné.
Algoritmy a výpočtové techniky
Na výpočet zvyšku sa používa bežné celočíselné delenie. Pre zložitejšie úlohy sú dôležité tieto algoritmy:
- Euklidov algoritmus pre výpočet najväčšieho spoločného deliteľa (gcd),
- rozšírený Euklidov algoritmus na získanie modulárneho inverzu,
- rýchla modularna exponentiácia (metóda opakovaného štvorenia) na výpočet a^k mod n bez priameho počítania a^k.
Pri implementácii do jazyka alebo hardvéru sa využívajú techniky na zamedzenie pretečeniu celočíselných typov, napríklad redukcia mod n počas medzivýpočtov alebo použitie veľkých celých čísel.
Použitie v matematike a informatike
Modulo má široké využitie: v teórii čísel pri štúdiu kongruencií, pri dôkazoch a v konštrukcii teoretických výsledkov; v matematike a jej aplikáciách; v počítačových algoritmoch na hashovanie, indexovanie do kruhových bufferov, generovanie náhodných sekvencií a pri práci s časovými údajmi; a v kryptografii, kde modularita leží v jadre verejných šifrovacích schém a digitálnych podpisov.
- Čínsky zvyškový teorém umožňuje skladať riešenia pre systémy kongruencií.
- V kryptografii sa používajú výsledky ako Eulerova veta alebo Malá Fermatova veta pri konštrukcii a analýze algoritmov založených na modulárnej aritmetike.
Príklady
Jednoduché príklady pomáhajú pochopiť variácie definícií: 17 mod 5 = 2, lebo 17 = 3·5 + 2. Pri záporných operandoch je potrebné poznať používanú konvenciu: ak sa požaduje nezáporný zvyšok, potom -3 mod 4 = 1 (pretože -3 = (-1)·4 + 1 s r = 1).
Krátka história a zdroje
Systematické používanie kongruencií a moderne poňatá modulárna aritmetika boli významne rozvinuté v dielach Carla Friedricha Gaussa. Pre ďalšie štúdium a konkrétne implementačné detaily pozrite základné texty a dokumentáciu: všeobecné matematické príručky, návody a špecifikácie programovacích jazykov, materiály k počítačom a kalkulačkám a technické dokumenty k hardvéru. Ďalšie súvisiace témy: delenie, celé čísla, kvocient a aritmetické operácie.