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