Modulární aritmetika

Z Wikipedie, otevřené encyklopedie

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 (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

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 , jiná zbytková třída (rovněž) modulo 10 obsahuje např. prvky .

Číselné kongruence modulo n

Pro libovolné definujme relaci takto: . Čísla se nazývají kongruentní modulo n a relace se nazývá číselná kongruence modulo n. Značíme . Relace je reflexivní, symetrická a transitivní, je tedy relací ekvivalence. Znaménko 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 na vytváří má n tříd, pro které platí:

Množina zbytkových tříd

Množinu všech zbytkových tříd pro dané značíme ,kde . Pro jednoduchost píšeme jen .


Základní vlastnosti modulární aritmetiky

Zavedená ekvivalence mezi prvky tvoří na okruhu (ℤ,+,·,0,1) kongruenci, tedy ∀a,b,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.

a tvoří komutativní grupy. Důkaz plyne z Cayleyových tabulek pro tuto strukturu. Například pro 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
1 2 3 4
1 1 2 3 4
2 2 4 1 3
3 3 1 4 2
4 4 3 2 1

Další operace

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

Pokud je 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

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 ).

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

Odkazy

Literatura

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

Související články