Matematické metody informační bezpečnosti (Mgr.) - SZZ

Informace uvedené na této stránce se týkají pouze nové akreditace (počátek studia v roce 2013 nebo později.)

Předměty potřebné k pokrytí požadované látky

NMMB401 Automaty a konvoluční kódy (AutKonKódy)
NMMB402 Číselné algoritmy (ČísAlg)
NMMB403 Počítačová algebra 2 (PočAlg2)
NMMB405 Složitost pro kryptografii (SloKry)
NMMB407 Pravděpodobnost a kryptografie (PraKry)

1. Algebraické základy kryptografie

Vlastnosti oborů integrity a jejich hierarchie

Eukleidovy okruhy a eukleidovy normy; jednoznačnost faktorizace a struktura ideálů v Eukleidových oborech (PočAlg2). Vlastnosti okruhu Zn: ideály, aditivní podgrupy, multiplikativní grupa a její struktura (ČísAlg).

Okruhy polynomů a konečná tělesa

Hilbertova věta o bázi pro polynomy více proměnných nad tělesem (PočAlg2). Struktura okruhu polynomů modulo (ne nutně ireducibilní) polynom: konstrukce konečných těles, struktura množiny {h | hq = h mod f} (PočAlg2).

Eliptické křivky

Definice eliptické křivky. Grupová operace na eliptické křivce. Algebraické množiny, Hilbertova věta o nulách pro algebraicky uzavřené těleso (ČísAlg).

Jiné (teorie čísel)

Čínská věta o zbytcích v obecných okruzích a aplikace na Zn (ČísAlg). Okruh formálních mocninných řad a jeho grupa invertibilních prvků, těleso racionálních funkcí (AutKonKódy). Narozeninový paradox (ČísAlg). Řetězové zlomky a dobré aproximace (ČísAlg). Kvadratické zbytky, výpočet Legenderova symbolu (ČísAlg).

2. Kódování a kryptologické algoritmy

Číselné algoritmy (ČísAlg)

Faktorizace

Jednoduché faktorizační metody: Pollardova rho metoda, p-1 metoda, ECM. Hledání vhodných kongruencí v kvadratickém sítu. Racionální aproximace sqrt(N) a metoda CFRAC. Tonelliho-Shanksův algoritmus pro modulární odmocňování.

Diskrétní logaritmus

Pollardova lambda metoda. Redukce problému diskrétního logaritmu na problém diskrétního logaritmu v grupě prvočíselného řádu. Indexový kalkulus.

Algoritmy pro práci s polynomy (PočAlg2)

Výpočet NSD pro polynomy jedné proměnné: Eukleidův algoritmus a jeho praktická použitelnost, posloupnosti polynomiálních zbytků. Faktorizace polynomů nad konečnými tělesy (bezčtvercová faktorizace; Berlekampův algoritmus). Gröbnerovy báze a Buchbergerův algoritmus. Princip přepisovacích algoritmů. Řešení soustav polynomiálních rovnic. Časová složitost uvedených algoritmů. Řešení soustav polynomiálních rovnic.

Iterativní kódování (AutKonKódy)

Souvislost posuvného registru a racionální funkce. Viterbiho algoritmus. Rozdíl mezi MAP a ML dekódováním.

Složitost a pravděpodobnost

Deterministické a nedeterministické výpočetní modely a jejich složitost

Konečné automaty (AutKonKódy)

Konečné automaty, regulární výrazy a racionální množiny monoidu. Kleeneova věta. Minimální automat, jeho konstrukce pomocí Myhillovy-Nerodovy ekvivalence. Syntaktický monoid jazyka, jeho charakterizace jako minimální kongruence, pro kterou se jazyk rozkládá na třídy, isomorfismus s transformačním monoidem minimálního automatu.

Turingovy stroje a složitostní třídy (SloKry)

Definice Turingova stroje. Výpočtový problém jako funkce nebo jazyk. Časová a prostorová složitost výpočtu. Koncept přijímání jazyka nedeterministickým strojem. Determinizace pomocí vektoru voleb. Simulace vícepáskového stroje jednopáskovým. Random Access Machine, srovnání s Turingovým strojem a současnými počítači. Nerozhodnutelné problémy (nerozhodnutelnost HALTING). Definice třídy NP pomocí nedeterministického stroje a pomocí svědecké relace, jejich ekvivalence. Popis problému P vs. NP.

Náhodnost a pseudonáhodnost (SloKry)

Definice pravděpodobnostního Turingova stroje. Třída BPP. Amplifikace pravděpodobnosti v BPP. Definice zanedbatelné funkce. Jednosměrné funkce, definice a příklady kandidátů. Pseudonáhodné generátory a jejich konstrukce z jednosměrných funkcí. Výpočetně nerozlišitelné distribuce. Důkazy s nulovou znalostí, definice a příklady.

Informační geometrie (PraKry)

Vlastnosti relativní entropie a Pinskerova nerovnost. Sanovova věta o velkých odchylkách. Pythagorova věta pro relativní entropie a informační projekce. Maximálně věrohodné odhady v exponenciálních rodinách. Extrakce tajných bitů z náhodného zdroje pomocí Ahlswedeova-Csiszárova lemmatu.

Last modified: 31 Jan 2014, 09:20:22