Modulární aritmetika

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Na rozdíl od běžné aritmetiky je modulární aritmetika definována na nějaké konečné množině n. Tato množina vznikne ze tak, že jsou všechna čísla se stejným zbytkem po dělení číslem n (zbytková třída) brána jako kongruentní a ztotožněna s jediným reprezentantem. Taková množina se pak nazývá množina zbytkových tříd.

Zbytková třída[editovat | editovat zdroj]

Zbytkovou třídou modulo n rozumíme množinu všech celých čísel, které při dělení přirozeným číslem n dávají stejný zbytek. Tuto množinu pak můžeme chápat jako jeden celek a celá čísla, která obsahuje, již dál nerozlišovat. Například jedna ze zbytkových tříd modulo 10 je tvořena množinou \{2, 12, 22, 32, ... \}, jiná zbytková třída (rovněž) modulo 10 obsahuje např. prvky \{7, 17, 27, -3, -13, -1234567893, 1147, ... \}.

Číselné kongruence modulo n[editovat | editovat zdroj]

Pro libovolné n\in \mathbb N, a,b \in \mathbb Z definujme relaci \phi_n takto: (a,b)\in\phi_n \Leftrightarrow n|a-b. Čísla a,b se nazývají kongruentní modulo n a relace \phi_n se nazývá číselná kongruence modulo n. Značíme a\equiv b(mod\ n). Relace \phi_n je reflexivní, symetrická a transitivní, je tedy relací ekvivalence. Znaménko \equiv tedy můžeme používat podobně jako znaménko =. Rovnosti v modulární aritmetice se obvykle zapisují jako kongruence a značí se trojčárkou: a + b ≡ b + a (mod n)

Obecně vzato, rozklad, který kongruence \phi_n na \mathbb Z vytváří má n tříd, pro které platí: [0]_{\phi_n}=\{k\cdot n|k\in \mathbb Z\},
[1]_{\phi_n}=\{1+k\cdot n|k\in \mathbb Z\},\dots ,
[n-1]_{\phi_n}=\{(n-1)+k\cdot n|k\in \mathbb Z\}.

Množina zbytkových tříd[editovat | editovat zdroj]

Množinu všech zbytkových tříd pro dané n značíme \mathbb Z_n=\{[a]_n|a\in \mathbb Z\} ,kde [a]_n=\{b|b\equiv a(mod\ n)\}. Pro jednoduchost píšeme jen \mathbb Z_n=\{0,1,\dots ,n-1\}.


Základní vlastnosti modulární aritmetiky[editovat | editovat zdroj]

Zavedená ekvivalence mezi prvky tvoří na okruhu (ℤ,+,·,0,1) kongruenci, tedy ∀a,b,n∈ℤ

  •  (a\;\bmod\;n + b\;\bmod\;n)\;\bmod\;n =(a+b)\;\bmod\;n
  •  (a\;\bmod\;n + n - b\;\bmod\;n)\;\bmod\;n =(a-b)\;\bmod\;n
  •  (a\;\bmod\;n \cdot b\;\bmod\;n)\;\bmod\;n =(a\cdot b)\;\bmod\;n

Proto je možné při výpočtech vzájemně zaměňovat prvky ve stejných třídách. Pro zjednodušení se nejčastěji používá vždy nejmenší nezáporné číslo.

(\mathbb Z_n,+) a (\mathbb Z_n,\cdot ) tvoří komutativní grupy. Důkaz plyne z Cayleyových tabulek pro tuto strukturu. Například pro \mathbb Z_5 mají Cayleyovy tabulky tvar:

+ 0 1 2 3 4
0 0 1 2 3 4
1 1 2 3 4 0
2 2 3 4 0 1
3 3 4 0 1 2
4 4 0 1 2 3
\cdot 0 1 2 3 4
0 0 0 0 0 0
1 0 1 2 3 4
2 0 2 4 1 3
3 0 3 1 4 2
4 0 4 3 2 1

Další operace[editovat | editovat zdroj]

Na ℤn lze přirozeně dodefinovat i další operace:

Pokud je n prvočíslo, pak ℤn tvoří těleso, protože pro každý nenulový prvek existuje inverzní prvek (vzhledem k násobení). Dělení se pak definuje jako násobení inverzním prvkem.

Operace dělení a diskrétní logaritmus v modulární matematice se nechovají stejně jako v klasické aritmetice a tedy není možné jejich výsledky přímo převést do ℤn jako u sčítání a násobení.

Aplikace[editovat | editovat zdroj]

Lidem je přirozenější klasická aritmetika, avšak modulární aritmetika má řadu výhod. Díky tomu, že je zde množina čísel konečná, jsou běžné operace jednodušší, rychlejší a potřebují konstantní množství paměti. Toho se využívá v počítačích, kde bývá typ "celých čísel" obvykle implementován v modulární aritmetice (nejčastěji n=2^{32}).

Na druhou stranu pro některé funkce není znám efektivní algoritmus (diskrétní logaritmus, faktorizace), čehož se často využívá v kryptografii.

Odkazy[editovat | editovat zdroj]

Literatura[editovat | editovat zdroj]

  • Hort D., Rachůnek J.; Algebra 1. UP Olomouc, 2003
  • Rachůnek J.; Grupy a okruhy, UP Olomouc, 2005

Související články[editovat | editovat zdroj]