Pocitacova algebra 2

Kdy a kde

Pondeli, 14:00 - 15:30 prednaska v K8; Ctvrtek 14:00 - 15:30 nekdy prednaska, nekdy cviceni v K7

Pravidla pro udeleni zapoctu

Zapocet bude k mani za aktivni ucast na cviceni, dodatecne bude mozne ziskat zapocet za vypracovani domacich ukolu.

Zkouska

Melo by jit o pismenou zkousku s teoretickou i pocetni casti. Starsi pisemka k nahlednuti. Pisemka neni bodovana, k uspesnemu napsani je treba alespon castecne zvladnout alespon jednu ulohu ke kazdemu probiranemu tematu (faktorizace polynomu, Groebnerovy baze, LLL algoritmus). Pozadavky ke zkousce zde.

Deni na prednasce

1. 10. Strucny obsah prednasky. Bezctvercova faktorizace polynomu. Kriterium bezctvercovosti pomoci derivace.
4. 10. Dokonceni bezctvercove faktorizace v charakteristice 0. Algoritmus 23 a diskuse jeho slozitosti. Algoritmus 24 pro bezctvercovou faktorizaci polynomu nad konecnym telesem. Idea odhadu slozitosti. Dulezita je Veta 15. 2., ze ktere je relativne snadne oba algoritmy odvodit.
8. 10. Faktorizace bezctvercoveho polynomu nad konecnym telesem. Tvrzeni klicova pro Berlekampuv algoritmus. Dulezita tvrzeni 16.1 a 16.2. Testovani ireducibility polynomu.
11. 10. Cviceni, zadani k dispozici zde. Jeste se vratime k uloham 2,4,6.
15. 10. Berlekampuv algoritmus pro faktorizaci (dulezity). Slozitost Berlekampova algoritmu. Ruznostupnova faktorizace a stejnostupnova faktorizace.
18. 10. Stejnostupnova faktorizace detailneji, pomocna tvrzeni 17.1. a 17.2. Henselovo lemma, snaha o vysvetleni lemmatu jako metodu pro dopocitavani koeficientu v p-adickem rozvoji.
22. 10. Henselovo Lemma (dulezite), dukaz vcetne jednoznacnosti, ktera neni ve skriptech. Algoritmus 28. Zakladni myslenka Berlekampova-Henselova algoritmu (uvod).
25. 10. Cviceni, zadani k dispozici zde.
27. 10. Kombinacni faze Berlekampova-Henselova algoritmu.
Text k prednasce. 30. 10. Berekampuv-Henseluv algoritmus, dokonceni. Kroneckeruv algoritmus. Goebnerovy baze, uvod.
5. 11. Algoritmus pro deleni se zbytkem.
8. 11. Cviceni, zadani k dispozici zde , reseni ulohy 13 , reseni ulohy 15.
12. 11. Groebnerovy baze, zakladni vlastnosti. Nekonstruktivni dukaz existence Groebnerovych bazi. Jednoznacnost redukovaneho tvaru jako vlastnost charakterizujici Groebnerovy baze (nestihli jsme dokoncit vsechny detaily v dukazu).
15. 11. S-polynomy a Buchbergerova veta (dulezita).
19. 11. Buchbergeruv algoritmus. Minimalni a redukovane Groebnerovy baze. Text k teto casti prednasky je zde.
22. 11. Cviceni, zadani k dispozici zde
26. 11. Zakladni aplikace Groebnerovych bazi: Problem nalezeni do idealu, rovnost idealu, problem nalezeni do radikalu, prunik idealu. (zde jsme postupovali podle skript 22.1, 22.2).
29. 11. Aplikace Groebnerovych bazi 2: Struktura souradnicoveho okruhu afinni algebraicke mnoziny. Reseni soustav polynomialnich rovnic. Obarvitelnost grafu, problem nalezeni do idealu je NP-tezky.
3. 12 Uvahy o vyuziti problemu nalezeni do idealu v kryptografii. "Automaticke" dokazovani Geometrickych uloh.
6. 12. Cviceni
10. 12. Mrizky, motivce, zakladni pojmy. Grammova-Schmidtova ortogonalizace-opakovani. Pojem nejkratsi baze mrizky a Gaussova redukce mrizky.
13. 12. Dukaz korektosti Gaussovy redukce mrizky. LLL redukovana baze a jeji vlastnosti.
17. 12. Cviceni.
20. 12. LLL algoritmus. Koreknost, polynomialni omezeni poctu kroku algoritmu.
3. 1. Dokonceni dukazu slozitosti LLL jako polynomialniho algoritmu. Vyuziti LLL pri faktorizaci celociselnych polynomu.
7. 1. Kryptograficke aplikace mrizek. Utok na protokol Merkle-Hellman, pokud ma dany problem batohu nizkou hustotu. Coppersmithuv utok na RSA s malym verejnym exponentem. Navrh systemu NTRU (nestihli jsme dokoncit, ale to uz je zivot)
10. 1. Cviceni, dodelavani zapoctovych restu.

Literatura

D. Stanovsky, L. Barto: Pocitacova algebra
W. W. Adams, P. Loustaunau: An Introduction to Groebner Bases,