Modulární aritmetika: Porovnání verzí
m Robot: Přidávám hi:मॉड्युलर गणित |
|||
Řádek 34: | Řádek 34: | ||
* [[množina zbytkových tříd]] |
* [[množina zbytkových tříd]] |
||
* [[teorie čísel]] |
* [[teorie čísel]] |
||
* [[okruh (algebra)]] |
|||
Verze z 19. 11. 2012, 14:05
Na rozdíl od běžné aritmetiky je modulární aritmetika definována na konečné množině ℤn. Ta vznikne ze ℤ tak, že jsou ztotožněna čísla se stejným zbytkem po dělení číslem .
Základní vlastnosti
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.
Zápis
Rovnosti v modulární aritmetice se obvykle zapisují s trojčárkou, která značí kongruenci:
a + b ≡ b + a (mod n)
Další operace
Na ℤn lze přirozeně dodefinovat i další operace:
- opačné číslo, jako inverzní operaci vzhledem ke sčítání
- odčítání, jako součet s opačným číslem
- mocnění, jako iterace násobení
- odmocnina a logaritmus, jako inverzní operace k mocnění
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í.
Použití
Lidem je přirozenější klasická aritmetika, ale 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 realizová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.
Související články