Modulární aritmetika

Je navrženo začlenit sem veškerý obsah z článku zbytkové třídy, třeba jako novou část, a oba tak sloučit. (diskuse)
Odtamtud sem pak má vést přesměrování.

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 $n$.

Základní vlastnosti

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.

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 $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í.

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

Související články

• zbytek po dělení
• množina zbytkových tříd
• teorie čísel
• okruh (algebra)