2. Elementární teorie čísel
Dělitelnost
Euklidův algoritmus
Modulární operace
Prvočíselnost a její testování
Aplikace teorie čísel
RSA
DSA
lineární (n, k) kódy
polynomiální kódy
podepisování a šifrování
a/b
věta o dělení celých čísel se zbytkem
největší společný dělitel (gdc)
kongruence
čínská zbytková věta
Eulerova funkce
malá Fermatova věta
modulární umocňování
prvočíslo
test prvočíselnosti
zkusmé dělení
hledání prvočísel
Eratosthenovo síto
pravděpodobnostní algoritmy
Fermatův test
detekce a oprava chyb
digitální podpis
hammingova vzdálenost
nesoudělnost
nejmenší společný násobek
n = [a, b]
nsd = (a, b)
př.: krácení zlomků
určení největšího spol. dělitele (gdc)
bezoutova věta
rozšifrování RSA
φ(n) = (p-1)(q-1)
alg. pro výp. φ(n) --> ohrožení RSA
V --> S
nsd (a, p) = 1
Eulerova věta
obecně v polynomiálním čase
všechna N < x
N < než odmocnina x
2 + lichá čísla
expo. složitost, pro malá čísla optim.
nexp. slož.
zal. na malé Fermatově v.
čísla tvářící se jako p
neplatí -> není; platí -> možná je
větší pam. náročnost
vyrobím: v(n, e), s(n, d):
p, q... velká
n = p*q
φ(n) = (p-1)(q-1)
zvol e < φ(n); (e, φ(n)) = 1... V
spočti (eukl. alg.) d; ed ≡ 1 (mod φ(n)) ... S
šifr: c ≡ M^e (mod n) --> pošle c
dešifr: M ≡ c^d (mod n)
zal. na problému výpočtu diskr. alg.
ke k-bit slovu přidám (n-k)-bit
kódování: v = G*u
syndrom H*u
kontrolní matice H(n-k, n)
generující matice G(n, k)
detekce chyb
oba potřebují V i S
n veřejné, φ(n) X dopočítat
modulo
hash
El Gamal
bezoutova rovnost
nsd(a, b) = A*a + B*b