Elementární teorie čísel

Note	Dělitelnost, Euklidův algoritmus, modulární operace, prvočíselnost a její testování, aplikace teorie čísel (RSA, DSA, lineární a polynomiální kódy). MB104/MB204

Teorie čísel je odvětví matematiky zabývající se vlastnostmi čísel - zejména celých.

— Wikipedie

Celá čísla $Z$ jsou množina. Ba co víc je to obor integrity $(Z, +, \cdot)$ . Platí tedy následující tabulka vlastností:

Note	V následující tabulce: $(\forall a, b \in Z)$

Vlastnost	Sčítání	Násobení
Uzavřenost	$a + b \in Z$	$a \cdot b \in Z$
Asociativita	$a + (b + c) = (a + b) + c$	$a \cdot (b \cdot c) = (a \cdot b) \cdot c$
Komutativita	$a + b = b + a$	$a \cdot b = b \cdot a$
Neutrální prvek	$a + 0 = a$	$a \cdot 1 = a$
Inverzní prvek	$a + (- a) = 0$	$(Z, \cdot)$ není grupa, jen monoid
Distributivita	$(\forall c \in Z) (a \cdot (b + c) = (a \cdot b) + (a \cdot c))$

Vlastnost

Sčítání

Násobení

Uzavřenost

$a + b \in Z$

$a \cdot b \in Z$

Asociativita

$a + (b + c) = (a + b) + c$

$a \cdot (b \cdot c) = (a \cdot b) \cdot c$

Komutativita

$a + b = b + a$

$a \cdot b = b \cdot a$

Neutrální prvek

$a + 0 = a$

$a \cdot 1 = a$

Inverzní prvek

$a + (- a) = 0$

$(Z, \cdot)$ není grupa, jen monoid

Distributivita

$(\forall c \in Z) (a \cdot (b + c) = (a \cdot b) + (a \cdot c))$

Dělitelnost

Dělitelnost je binární relace $∣$ nad celými čísly taková, že platí

(\forall a \in Z) (\forall b \in Z) (a ∣ b ⟺ (\exists c) (a \cdot c = b)) .

Celé číslo $a$ dělí celé číslo $b$ , právě když existuje celé číslo $c$ takové, že $a \cdot c = b$ .

Vlastnosti dělitelnosti

Vlastnost	Popis
Všechno dělí nulu	$(\forall a \in Z) (a ∣ 0)$
Všechno dělí samo sebe	$(\forall a \in Z) (a ∣ a)$
Tranzitivita	$(\forall a \in Z) (\forall b \in Z) (\forall c \in Z) (a ∣ b \land b ∣ c ⟹ a ∣ c)$
Bezoutova věta	$(\forall a, b \in Z) (\exists m, n \in Z) (a \cdot m + b \cdot n = GCD (a, b))$ , což se může zdát neintuivní, než si uvědomíš, že celý čísla můžou být záporný.

Vlastnost

Popis

Všechno dělí nulu

$(\forall a \in Z) (a ∣ 0)$

Všechno dělí samo sebe

$(\forall a \in Z) (a ∣ a)$

Tranzitivita

$(\forall a \in Z) (\forall b \in Z) (\forall c \in Z) (a ∣ b \land b ∣ c ⟹ a ∣ c)$

Bezoutova věta

$(\forall a, b \in Z) (\exists m, n \in Z) (a \cdot m + b \cdot n = GCD (a, b))$ , což se může zdát neintuivní, než si uvědomíš, že celý čísla můžou být záporný.

Dělitelnostní™ pojmy

Největší společný delitěl

$GCD (a, b)$ je nejvetší $c \in Z$ takové, že $(c ∣ a) \land (c ∣ b)$ . Zapisuje se taky jako $(a, b)$ , což vůbec není matoucí.

Nejmenší společný násobek

$LCM (a, b)$ je nejmenší $c \in Z$ takové, že $(a ∣ c) \land (b ∣ c)$ .

Nesoudělná čísla (coprimes)

Celá čísla $a$ a $b$ jsou nesoudělná, právě tehdy když 1 je jejich jediný společný dělitel.

Note	1 je nesoudělná se vším!

Prvočíslo

Číslo $p$ , které je dělitelé pouze číslem 1 a sebou samým. Nebo jinými slovy, $p$ není násobkem žádných dvou menších celých čísel různých od 1.

Bezoutovy koeficienty

Čísla $m, n$ z věty výše. Počítají se jako vedlejší produkt Euklidova algoritmu.

Inverze vzhledem k násobení

Číslo $a^{- 1}$ takové, že $a \cdot a^{- 1} \equiv 1 (mod m)$ .

$x \equiv a^{- 1} (mod n)$ lze vyřešit jako Bezoutovu rovnici $a x + n y = 1$ pomocí Euklidova algoritmu.

Eulerova funkce $φ (n)$

Počet čísel nesoudělných s $n$ v intervalu $[1, n]$ . Pár zajímavostí:

Pokud $n$ je prvočíslo, pak $φ (n) = n - 1$ .
Pokud $n = p^{k}, k \geq 1$ , kde $p$ je prvočíslo, pak $φ (n) = p^{k - 1} \cdot (p - 1)$ .
Platí $φ (mn) = φ (m) \cdot φ (n)$ .
Třeba $φ (12) = φ (2^{2} \cdot 3) = φ (2^{2}) \cdot φ (3) = (2^{1} \cdot (2 - 1)) \cdot 2 = 4$ .

Euklidův algoritmus

Najde nejmenšího společného dělitele (GCD) dvou celých čísel.

def gcd(a: int, b: int) -> int:
    # `a` must be greater than `b`
    a = a mod b
    if a == 0:
        return b
    return gcd(b, a)

Příklad s 133 a 15: $13315132 GCD (133, 15) = 8 \cdot 15 + 13 = 1 \cdot 13 + 2 = 6 \cdot 2 + 1 = 2 \cdot 1 + 0 = 1 a = 133, b = 15 a = 15, b = 13 a = 13, b = 2 a = 2, b = 1 a = 1, b = 0$

Modulární operace

Líbilo by se nám nějak vyjádřit, že, když dvě celá čísla mají po dělení stejným číslem $n$ stejný zbytek, tak jsou si tak nějak "podobná". Téhle relaci se říká kongruence modulo $n$ .

Note	Kongruence je relace ekvivalence vztahující se k nějaké operaci. Ne nutně modulo $n$ . Hlavní je, aby kongruentní prvky daly ten samý výsledek, když na ně člověk tu operaci použije.

Vlastnosti modulární aritmetiky

Note	V následující tabulce: $(\forall a, b, c, d \in Z) (\forall m \in Z^{+})$

Pokud $a \equiv b (mod m)$ , pak:

Vlastnost	Popis
Komutativita	$b \equiv a (mod m)$
Přidání konstanty	$a + c \equiv b + c (mod m)$
Přidání násobku $m$	$a + c m \equiv b (mod m)$ , $a \equiv b + c m (mod m)$
Násobení konstantou	$a c \equiv b c (mod m)$
Násobení modulu konstantou $c > 0$	$a c \equiv b c (mod m c)$
Dělení modulu konstantou	$(a c \equiv b c (mod m) \land d = GCD (m, c)) ⟹ a \equiv b (mod m / d)$
Sčítání kongruencí	$c \equiv d (mod m) ⟹ a + c \equiv a + d (mod m)$
Násobení kongruencí	$c \equiv d (mod m) ⟹ a \cdot c \equiv a \cdot d (mod m)$
Fermatova malá věta	$(p je prvo \overset{c}{ˇ} \overset{ı}{ˊ} slo \land p ∤ a) ⟹ a^{p - 1} \equiv 1 (mod p)$
Eulerova věta	$GCD (a, m) = 1 ⟹ a^{φ (m)} \equiv 1 (mod m)$
Rozklad modulu na 2 nesoudělná čísla	$(x \equiv a^{b} (mod m \cdot n) \land GCD (m, n) = 1) ⟹ (x \equiv a^{b} (mod m) \land x \equiv a^{b} (mod n))$

Vlastnost

Popis

Komutativita

$b \equiv a (mod m)$

Přidání konstanty

$a + c \equiv b + c (mod m)$

Přidání násobku $m$

$a + c m \equiv b (mod m)$ , $a \equiv b + c m (mod m)$

Násobení konstantou

$a c \equiv b c (mod m)$

Násobení modulu konstantou $c > 0$

$a c \equiv b c (mod m c)$

Dělení modulu konstantou

$(a c \equiv b c (mod m) \land d = GCD (m, c)) ⟹ a \equiv b (mod m / d)$

Sčítání kongruencí

$c \equiv d (mod m) ⟹ a + c \equiv a + d (mod m)$

Násobení kongruencí

$c \equiv d (mod m) ⟹ a \cdot c \equiv a \cdot d (mod m)$

Fermatova malá věta

$(p je prvo \overset{c}{ˇ} \overset{ı}{ˊ} slo \land p ∤ a) ⟹ a^{p - 1} \equiv 1 (mod p)$

Eulerova věta

$GCD (a, m) = 1 ⟹ a^{φ (m)} \equiv 1 (mod m)$

Rozklad modulu na 2 nesoudělná čísla

$(x \equiv a^{b} (mod m \cdot n) \land GCD (m, n) = 1) ⟹ (x \equiv a^{b} (mod m) \land x \equiv a^{b} (mod n))$

Modulární (ve smyslu souvislosti s modulem) pojmy

Čínská zbytková věta: Pro $a, b, m_{1}, m_{2}$ , kde $GCD (m_{1}, m_{2}) = 1$ , má soustava kongruencí:

$x x \equiv a (mod m_{1}) \equiv b (mod m_{2})$

právě jedno řešení v $[0, m_{1} \cdot m_{2})$ .
Řád čísla: Pro $a \in Z, m \in N, GCD (a, m) = 1$ je řád čísla nejmenší $n \in N$ takové, že $a^{n} \equiv 1 (mod m)$ .
Primitivní kořen: Pro $m \in N$ je primitivní kořen číslo $g \in Z, GCD (g, m) = 1$ takové, že jeho řád je roven $φ (m)$ .

Testování prvočíselnosti

Pro otestování zda $n \in Z$ je prvočíslo existuje několik přístupů:

Postupné dělení čísly z intervalu $[2, n)$ (resp. stačí $[2, n)$ ).
Eratosthenovo síto: Vyrob si seznam čísel $[2, n]$ a postupně z něj odebírej násobky 2, 3, 5, …, $n$ . To, co ti v seznamu zůstane, jsou prvočísla.
Fermatův test: Pokud Fermatova malá věta platí pro čísla $a$ nesoudělná s $p$ , pak je $p$ nejspíš prvočíslo. (Ano, jen nejspíš.)

Kryptografie

Teorie čísel má své využití zejména v oblasti šifrování a digitálních podpisů.

Problém diskretního logaritmu

Kryptografie mnohdy spoléhá na výpočetní náročnost diskrétního logaritmu.

Pro daný základ $b \in N$ a číslo $a \in N$ je diskrétní logaritmus číslo $k \in N$ takové, že $b^{k} = a$ , píšeme $lo g_{b} (a) = k$ .

Kryptografie nepoužívá všechna $N$ , ale jen nějakou cyklickou grupu o $p$ prvcích, proto $b^{k} \equiv a (mod p)$ , kde $b$ je primitivní kořen $p$ a $GCD (a, m) = 1$ .

Rivest-Shamir-Adleman (RSA)

Asymetrická šifra používájící dva klíče: veřejný, který dáš všem, a soukromý, který si necháš pro sebe.

Generování klíčů

Zvol dvě velká, ruzná prvočísla $p$ a $q$ .
$n = p \cdot q$ .
Spočítej $φ (n) = (p - 1) (q - 1)$ .
Zvol celé číslo $e$ menší než $φ (n)$ takové, že $GCD (e, φ (n)) = 1$ .
Nalezni číslo $d$ takové, že $d \cdot e \equiv 1 (mod φ (n))$ .
Veřejný klíč je $(n, e)$ , soukromý klíč je $(n, d)$ .

Šifrování zprávy

Měj zprávu $M$ a veřejný klíč $(n, e)$ . Platí $M < n$ .
Zašifrovaná zpráva je $C = M^{e} (mod n)$ .

Dešifrování zprávy

Měj zašifrovanou zprávu $C$ a soukromý klíč $(n, d)$ .
Původní zpráva je $M = C^{d} (mod m)$ .

ElGamal

Vytvoření klíčů

Zvol prvočíslo $p$ .
Spočítej $g$ — primitivní kořen $p$ .
Zvol soukromý klíč $x$ .
Spočítej $h = g^{x} (mod p)$ .
Tvůj veřejný klíč je $(p, g, h)$ , tvůj soukromý je $x$ .

Šifrování zprávy $M$

Zvol náhodně $y \in Z$ .
Spočítej $C_{1} = g^{y} (mod p)$ .
Spočítej $C_{2} = M \cdot h^{y} (mod p)$ .
Pošli $(C_{1}, C_{2})$ .

Dešifrování $(C_{1}, C_{2})$

\frac{C _{2}}{C _{1}^{x}} \equiv \frac{M \cdot h ^{y}}{g ^{y} ^{x}} \equiv \frac{M \cdot g ^{x} ^{y}}{g ^{y} ^{x}} \equiv \frac{M \cdot g ^{x y}}{g ^{x y}} \equiv M (mod p)

Digital Signature Algorithm (DSA)

Standard pro digitální podpisy podobný algoritmu ElGamal.

Podepsání

Vyrob hash zprávy.
Zašifruj hash svým soukromým klíčem.
Přilož podpis ke zprávě a zprávu pošli.

Ověření

Vyrob hash zprávy.
Dešifruj přiložený podpis odesílatelovým veřejným klíčem.
Porovnej hashe.

Kódy

Chyby při přenosu se dějí a úplně zabránit se jim nedá. Přenášená informace se ale dá transformovat kódem tak, že poznáme, že k chybě došlo nebo ji dokonce můžeme opravit. Kódy využívají teorie čísel.

Hammingova vzdálenost: Počet bitů, ve kterých se slova (posloupnosti bitů) liší.
$(n, k)$ -kód: Původní informace má délku $k$ bitů. Zakódovaná informace má délku $n$ bitů, kde $n > k$ . Přidáním $n - k$ bitů jsme schopní detekovat a opravovat chyby způsobené přenosem informace.

Lineární kódy

Lineární kód je takový kód, kde lineární kombinace dvou kódových slov je opět kódové slovo.

Generující matice: Linární kód lze reprezentovat generující maticí $G$ o $n$ řádcích a $k$ sloupcích, která funguje jako báze vektorového podprostoru kódových slov. Pro každé slovo $u$ je $v = G \cdot u$ kódové slovo.
Matice kontroly parity: Matice $H$ o $n - k$ řádcích a $n$ sloupcích, kde pro každé kódové slovo $v$ platí $H \cdot v = 0$ . Pokud $G = (I _{k} P)$ , pak $H = (I_{n - k} P)$ ( $I_{x}$ je matice identity o velikosti $x$ ).
Syndrom slova $u$: Je hodnota $H \cdot u$ . Pokud je nenulový, slovo je chybné. Pokud syndrom připočteme ke všem validním kódovým slovům. Výsledná hodnota z nejméně jedničkami odpovídá původní zprávě za předpokladu, že nastalo nejmenší možné množství chyb.

Polynomiální kódy

Mějme polynom $p (x) = a_{0} + a_{1} x + a_{2} x^{2} + ... + a_{n - k} x^{n - k} \in Z_{2} [x]$ , kde $a_{0} = 1$ a $a_{n - k} = 1$ . Polynomiální kód generovaný polynomem $p (x)$ je lineární $(n, k)$ -kód, jehož kódová slova jsou polynomy stupně menšího než $n$ dělitelné $p (x)$ .

Note	$Z_{2} [x]$ je množina polynomů, kde $a_{n} \in {0, 1}$ .

Zakódování: $v (x) = r (x) + x^{n - k} \cdot m (x)$ ,

kde $r (x)$ je zbytek po dělení polynomu $x^{n - k} \cdot m (x)$ polynomem $p (x)$ .
Chybový polynom: Pokud $v (x) / p (x) \neq = 0$ , pak zpráva obsahuje chybu a $v (x) mod p (x)$ je chybový polynom.