Modulární aritmetika

Z Wikipedie, otevřené encyklopedie

Na rozdíl od běžné aritmetiky je modulární aritmetika definována na konečné množině. Na rozdíl od běžných operací se zde po každé operaci provede celočíselné dělení a výsledkem je zbytek.

[editovat] Základní pravidla

Pro a,b,n∈ℕ

  • (a mod n + b mod n) mod n = (a+b) mod n
  • (a mod n · b mod n) mod n = (a·b) mod n

[editovat] Použití

Díky pravidlům je používán zápis:

a + b ≡ b + a (mod n)

Trojčárka značí kongruenci na přirozených číslech. Stejné vlastnosti bychom dostali při použití celých čísel, neboť počet prvků by byl vždy roven n. Nelze použít racionální ani reálná čísla, protože bychom neměli konečný počet prvků. Zajímavou možností jsou celá komplexní čísla. Ta se ale v praxi nepoužívají. Lidem je obecně příjemnější klasická aritmetika, ale tato aritmetika má výhodu pro počítače. Lze ji totiž snadno implementovat z hlediska nároku na paměť. Na druhou stranu v ní existují funkce, které lze spočítat pouze vyzkoušením všech možností (na rozdíl od klasické aritmetiky), například diskrétní logaritmus. Pokud je možností tolik, že by se prošly za dobu, kterou existuje Země, pak lze tyto funkce použít např. v kryptografii.