Ciselne algortimy, LS 2023/2024

Kdy a kde

Prednaska: Patek 10:40 - 12:10, K7
Cviceni: Patek 12:20 - 13:50, K7 (pouze sude tydny)

Zkouska a zapocet

Zkouska bude ustni a jednoducha. Pro ziskani zapoctu je treba vyresit alespon 55% zadanych uloh (vetsinou je to pet uloh z osmi). Domaci ukoly budu zadavat prubezne na prednasce, reseni ukolu je mozne odevzdavat az do 31. 8.

Prihlasovani ke zkousce

Terminy nejsou v SISu vypisovany, jelikoz jde o ustni zkouseni, lze si dohodnout termin zkousky individualne emailem.

Deni na prednasce

23. 2. 2024: RSA a problem faktorizace - faktorizacni algoritmus s orakulem na hledani soukromeho klice RSA. Literatura [B], str. 145 - 148. Prezentace (LS 2020/2021) zde.
1. 3. 2024: Zkusme deleni - scenare pro odhady slozitosti. Pollardova rho-metoda, posloupnosti vytvorene funkci, perioda, preperioda. Floydova metoda hledani cyklu. Strucny komentar k heuristickemu odhadu slozitosti v prumernem pripade. Literatura [C], str. 419 - 421. Prezentace (LS 2020/2021) zde.
Cviceni: Coppersmithova metoda hledani malych korenu, prvni cast. Cviceni k Pollardove metode zaradime pozdeji, mozno si rozmyslet nevhodne volby polynomu, podrobneji zde.
8. 3. 2024: Pollarova (p-1)-metoda, zakladni princip, odstranovani problemu s prilis velkou volbou B. Odhady slozitosti v zavislosti na volbe B. Prezentace (LS 2020/2021) zde.
15. 3. 2024: Dvoufazova (p-1)-metoda, princip (p+1)-metody. Literatura [P], str. 236 - 237, tez [C], str. 431 - 435. ECM - projektivni rovinne krivky, elipticke krivky zadane Weierstrassovou rovnici, grupa bodu elipticke krivky nad p-prvkovym telesem a jeji velikost (bez dukazu). Prezentace (LS 2020/2021) zde
Cviceni: Naznak dukazu Coppersmithovy vety alespon na urovni, ze ktere je patrna konstrukce algoritmu pro hledani korenu polynomialnich kongruenci.
22. 3. 2024 ECM princip algoritmu, nasobnost pruniku primky a krivky v projektivni rovine (intuitivni vysvetleni specialniho pripadu Bezoutovy vety), odvozeni vzorcu pro grupove operace na elipticke krivce (stihli jsme jenom operaci opacneho prvku). Prezentace (LS 2020/2021) zde.
29. 3. 2024 Velky patek
5. 4. 2024 Odvozeni vzorcu pro ECM - scitani, slozitost ECM(*), paralelni inverze. Literatura [C], str. 476 - 481. Odmocnovani v konecnem telese, specialni pripad p = 4k + 3.
12. 4. 2024 Tonelli-Shanksuv algoritmus. Odmocnovani v okruhu Z_p^k - Henselovo zdvihani.
Na cviceni - Pollard rho - priklad k prumernemu poctu iteraci pro p = 11. Vhodne a nevhodne polynomy pro Pollard rho. Prezentace (LS 2020/2021) zde
19. 4. 2024 Odmocnovani modulo N a problem faktorizace, algoritmus pro hledani korenu polynomu nad telesem prvociselneho radu. Prezentace (LS 2020/2021) zde. Fermatova faktorizace a par slov na uvod k Dixonove faktorizaci.
26. 4. Dixonova faktorizace: relace, hladke relace, faktorizacni baze, linearni faze, dobra a spatna reseni. Parcialni relace s jednim velkym prvocislem a jejich zpracovani. Retezove zlomky - velmi strucne shrnuti a zavedeni znaceni. Algoritmus pro retezovy rozvoj odmocniny - odvozeni vztahu. Prezentace (LS 2020/2021) zde
3. 5. 2024 CFRAC - odvozeni vztahu pro generovani relaci. Optimalizace algoritmu pro vypocet retezoveho rozvoje odmocniny.
Prezentace (LS 2020/2021) Prezentace (LS 2020/2021) zde a zde
10. 5. 2024 Odhad velikosti prave strany CFRACu. Kvadraticke sito, hledani hladkych relaci pomoci prosivani. Jednoducha verze, prosivani vyssich mocnin, hledani parcialnich relaci. MPQS - pouze inicializace polynomu, MPQS nebude predmetem zkousky. Prezentace (LS 2020/2021) zde
Cviceni: Odmocnovani modulo prvocisla tvaru 8k + 5, dobra a spatna reseni v Dixonove faktorizaci - dukaz, ze spatna reseni tvori podprostor. Pokus o vysvetleni, proc spatna reseni tvori podprostor. Parovani parcialnich relaci, trivialni dusledky zvetsi matici ale nemeni pomer spatnych reseni vuci vsem resenim. Ciste periodicke retezove zlomky, detekce periody v algoritmu pro pocitani rozvoje. Pro zajemce dukaz vety charakterizujici cisla s ciste periodickym retezovym rozvojem.
17. 5. 2024 Slozitost kvadratickeho sita, nastaveni parametru optimalizaci heuristickeho odhadu slozitosti (nebude predmetem zkousky). Problem diskretniho logaritmu, Pohlig-Hellmanova redukce. Starsi text ke slozitosti QS, viz tez [B], str 178 - 181. Prezentace (LS 2020/2021) zde.
24. 5. 2024 Faktorizace pomoci orakula pro reseni zobecneneho problemu diskretniho logaritmu v Z_n*. Algoritmus Baby-steps, giant-steps a Pollard-rho pro vypocet diskretniho logaritmu (z vetsi casti preteklo do cviceni, kde jsme tez spocitali priklady na Pollard rho a pristup kombinujici Pohlig-Hellmanovu redukci s Pollard-rho). Prezentace (LS 2020/2021) zde.

To je pro letosek vse. Dekuji za pozornost a tesim se na hezke vykony u zkousky. Infomace o prihlasovani ke zkousce najdete jsou uvedeny nahore.

Literatura

[B] J. A. Buchmann: Introduction to Cryptography.
[C] H. Cohen: A Course in Computational Number Theory.
[M] A. May: Using LLL-Reduction for Solving RSA and Factorization problems.
[P] R. Crandall, C. Pomerance: Prime Numbers. A Computational Perspective.