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

Zápis[editovat | editovat zdroj]

Rovnosti v modulární aritmetice se obvykle zapisují s trojčárkou, která značí kongruenci:

a + b ≡ b + a (mod n)

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.

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