Modulární aritmetika

Modulární aritmetika se od té klasické liší v tom, že používá jenom omezený rozsah celých čísel. Říká se jí také hodinová aritmetika, protože pracuje s konečnou množinou čísel, které můžeme uspořádat do kruhu podobně jako na cíferníku hodin. Na vedlejším obrázku jsou "hodiny" pro tzv. modulo 8, zapisujeme zkráceně (mod 8), které používají celá čísla od nuly do sedmičky. Tak například 3 + 4 = 7 (mod 8), což je stejné jako v běžné aritmetice. Ale např. 4 + 6 = 2 (mod 8). Výsledek získáme tak, že začneme u čtyřky a na hodinách se posuneme o šest míst a skončíme u dvojky.

Formálně provedeme výpočet tak, že čísla sečteme normálním způsobem (4 + 6 = 10) a součet vydělíme modulem n. Výsledek obdržíme jako zbytek po celočíselném dělení (10/8 = 1 zbytek 2). Obecně můžeme napsat, že:

a b (mod n), pokud n | (a - b). Zápis čteme jako: čísla a, b jsou kongruentní modulo n (tři vodorovné čárky jsou symbolem pro kongruenci).

Všechna čísla se stejným zbytkem po celočíselném dělení jsou kongruentní a nazývají se množina zbytkových tříd. Zbytková třída modulo 8 může být například tato: 3,-5, 11, -13, 19, -21, 27, -29,.. Všechna tato čísla totiž při dělení n dávají stejný zbytek (v našem případě se zbytek rovná 3). Základní pravidla pro modulární aritmetiku jsou následující:

[a (mod n) + b (mod n)] (mod n) (a + b) (mod n)
[a (mod n) - b (mod n)] (mod n) (a - b) (mod n)
[a (mod n) · b (mod n)] (mod n) (a · b) (mod n)

Funkce se v modulární aritmetice často chovají jinak než v aritmetice běžné. Například exponenciální funkce a^x je pro x > 1 funkcí rostoucí. V modulární aritmetice se ta samá funkce chová nevyzpytatelněji. Vezměme si například funkci 5^x. Její funkční hodnoty v běžné a modulární aritmetice shrnuje následující tabulka.

V klasické aritmetice lze z hodnoty funkce snadno odvodit původní exponent. K exponenciální funkci je inverzí funkce logaritmická. Např.: 5^x = 125. Pomocí pravidel pro práci s logaritmy dostaneme: x · ln(5) = ln (125) => x = ln (125) / ln (5) = 3, kde ln je přirozený logaritmus.

Pokud ale dostaneme příklad: 5^x 6 (mod 7), není žádný snadný způsob, jak z výsledku získat zpátky exponent x. Pro nízké hodnoty modula můžeme samozřejmě sestavit podobnou tabulku s jednotlivými exponenty a funkčními hodnotami. Pro velká čísla je ale takový způsob značně neefektivní a zabralo by spoustu času, než by byl správný exponent nalezen. O takových funkcích říkáme, že jsou jednosměrné. Je totiž snadné vypočítat její hodnotu pro jakékoliv x, ale je mimořádně obtížné z funkční hodnoty získat zpátky x. Této vlastnosti modulární aritmetiky se využívá v kryptografii, například v RSA šifrování.

Komentáře k článku