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.

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).
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.
19. 4. 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.

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.