Algoritmy na mrizich, ZS 2024/2025

Kdy a kde

Ctvrtek 15:40 - 17:20 v seminarni mistnosti KA

Zkouska

Bude ustni, dve otazky z probrane latky.

Prezentace a zaznam prednasek ze ZS 2020/2021

Jsou k dispozici na studentskem ulozisti .
Nekolik neprilis zdarilych pokusu o prezentace latky z letosnich prednasek je zde. (prubezne doplnuju, ale kompletni to asi nebude)

Domaci ukoly

Prvni sada domacich ukolu odtajnena, kod k povinne uloze c. 8. Reseni prosim odevzdejte do 20. prosince cvicicimu (mozno i mailem). Kod k povinne uloze c. 8 je ke stazeni zde.
Druhou sadu ukolu najdete zde. Tentokrat je potreba odevzdat vsechny ulohy, ktere nejsou oznaceny jako volitelne. V pripade potreby dostanete moznost reseni opravit ci doplnit. Reseni prosim odevzdejte do 30. brezna.

Deni na prednasce

3. 10. 2024 Definice mrize, mrize a diskretni podgrupy. V dalsi hodine bude zasadni implikace ze kazda mriz je diskretni podgrupa.

10. 10. 2024 Baze v mrizich, determinant pro uplne mrize i obecne mrize. Geometricky vyznam determinantu. Kratke vektory - Minkowskeho veta a jeji dukaz, bez zaverecneho kroku.

17. 10. 2024 Problem SVP a jeho varianty. Vicemene neformalni povidani o vztahu slozitosti a velikosti aproximacniho faktoru. Problemy se SISem a problem s vysvetlenim myslenky redukce hledani reseni nejtezsi instance SVP na prumernou instanci SISu s aplikaci pro dukaz "bezpecnosti" mnoziny hashovacich funkci.

24. 10. 2024 Mrize v dimenzi 2, algoritmus pro hledani nejkratsi baze - proc skonci a proc vrati korektni vystup. Vylepseni Minkowskeho meze pro dimenzi 2 a jednoducha aplikace v teorii cisel.

31. 10. 2024 Analyza Gaussovy redukce dvourozmerne mrize. LLL redukovana baze, definice a komentar k ni.

7. 11. 2024 Vlastnosti LLL redukovane baze mrize, LLL algoritmus, nestihli jsme jedno tvrzeni k tomu, proc algoritmus skonci.

14. 11. 2024 Slozitost LLL, zhruba mame, ze pocet operaci v Q bude polynomialni a snazime se pohlidat delku cisel v algoritmu. Jeste chybi odhlad velikosti citatelu koeficientu z G.-S.

21. 11. 2024 Dokonceni LLL. Aplikace - hledani malych korenu polynomialnich kongruenci (Coppersmithova metoda).

28. 11. 2024 Dokonceni algoritmu pro hledani malych korenu. Klasicky Hastadtuv utok na RSA a jeho rozsireni (nestihli jsme dodelat).
Zapisky z prednasky O. Regeva zde.

5. 12. 2024 Problem hledani nejblizsiho vektoru v mrizi (CVP). Nearest plane algorithm (zbyva dokoncit dukaz korektnosti).

7. 12. 2024 Koreknost NPA (dokonceni), NP uplnost rozhodovaciho CVP. Schema Merkle-Hellman a primocary utok pres kratke vektory. Jak resit optimalizacni CVP pomoci orakula pro rozhodovaci CVP.
Zapisky z prednasky O. Regeva zde.

19. 12. 2024 Jak resit vyhledavaci CVP pomoci orakula pro rozhodovaci CVP a NPA. NP uplnost CVP. Popis algoritmu AKS sieve.
Zapisky z prednasky O. Regeva ke slozitosti CVP AKS zde. Delali jsme Lemma 1 a Theorem 2, ale myslim, ze to stoji za procteni cele.

9. 1. 2025 Dukaz koreknosti AKS - dokonceni. Kombinacni faze Berlekampova-Henselova algoritmu pomoci LLL - bohuzel jsme stihli jenom popis algoritmu bez jakehokoliv vysvetleni. Podrobnosti lze najit ve skriptech Pocitacova algebra nebo tez na teto prezentaci.
Zapisky z prednasky O. Regeva k AKS zde.

Info: Nektere studijni materialy jeste pridam v prubehu prvniho tydne zkouskoveho obdobi, bohuzel jsem je nestihnul vyrobit behem vanocnich prazdnin. Termin zkousky si lze domluvit individualne po mailu.