M04 - Bezpečnost operačního systému a síťové komunikace

Modulární aritmetika definuje tzv. kongruentní třídy celých čísel. Dvě čísla a, b
jsou modulo N kongruentní, jestliže existuje takové q, že platí (a − b) = q ∗ N .
Tento vztah se také zapsat výrazem

a ≡ b (mod N ).

(9)

Příkladem kongruentní třídy jsou čísla 2, 14, 26, 38, 50, . . . . Libovolná dvě čísla
splňují požadavek definice z předchozí věty pro N = 12. Jsou tedy kongruentní
modulo 12, resp. říkáme, že čísla náleží do kongruentní třídy modulo 12, např.
(26 − 2) = 2 ∗ 12 nebo (50 − 2) = 4 ∗ 12. Kongruenci může vyjádřit také
pomocí zbytku po dělení modulem. Všechna čísla z uvedeného příkladu mají
tu vlastnost, že zbytek po dělení 12 je číslo 2.

Poznámka:

V programovacích jazycích se pro operaci modulo obvykle pou-

žívá operátor %.

Jednou z nejdůležitějších vět modulární aritmetiky je věta označovaná jako
malá Fermatova věta. Jsou-li a, p nesoudělná celá čísla, pak platí

a

p−1 ≡ 1 mod p.

(10)

Je-li p prvočíslo, pak existuje právě p − 1 nesoudělných čísel s p. Tuto hodnotu
vyjadřuje Eulerova funkce ϕ(p) = p−1. Zobecnění Fermatovy věty se označuje
jako Euler-Fermatova věta, kterou vyjadřuje následující výraz

a

p−1 ≡ 1 mod p.

(11)

23

Informatika

Modulární aritmetika poskytuje tzv. jednosměrné funkce, tj. takové funkce, ke
kterým nelze vytvořit funkci inverzní. Právě jednosměrné funkce se používají
při vytváření kryptografických algoritmů. Pro následné úvahy spojené s asyme-
trickými šifrovacími algoritmy je vhodné uvést základní operace v modulo arit-
metice:

(a mod N ) + (b mod N ) = (a + b) mod N
(a mod N ) ∗ (b mod N ) = (a ∗ b) mod N
(a mod N )b = ab mod N
(ab)c mod N = ab∗c mod ϕ(N) mod N