Ciselne sito ZS 2023/2024
Kdy a kde
V pondeli 12:20 - 13:50 v K8.
Zkouska
Ustni zkouska bude slozena ze tri otazek. Jedna otazka na hruby popis
algoritmu ciselneho sita + jedna z fazi s detailnejsim popisem,
jedna otazka na vetu a dukaz a jedna otazka bude nejaka pocetni.
Distancni zkouska by nejspise byla formou domaciho ukolu.
Nahravky prednasek (ZS 2020/2021)
najdete na studentskem ulozisti.
Porad se neco deje...
2. 10. 2023 Shrnuti nekterych algoritmu z prednasky ciselne algoritmy.
9. 10. 2023 Faktorizace cisel tvaru m^2 + 1 metodou specialniho ciselneho sita.
16. 10. 2023 Faktorizace cisel tvaru m^2 + 1 - konkretni priklad.
23. 10. 2023 Specialni ciselne sito trochu podrobneji, priklad: uplna faktorizace F9 = 2^(2^9) + 1.
Detaily viz [L]. Nastin obecneho ciselneho sita
30. 10. 2023 Ciselna telesa, shrnuti teorie z prednasky komutativni okruhy (norma a stopa).
Celistve prvky ciselneho telesa, pojem Dedekindova oboru.
6. 11. 2023 Idealy v Dedekindovych oborech. Diskriminant, dukaz ze Z_K je Dedekinduv obor (podstatna cast).
13. 11. 2023 Dokonceni dukazu, ze Z_K je Dedekinduv obor. Pohst-Zassenhausuv algoritmus (prvni cast).
20. 11. 2023 Dukaz Pohst-Zassenhausovy vety (neprilis povedeny).
27. 11. 2023 Konkretni vypocty v Pohst-Zassenhausove algoritmu, prubeh algoritmu pro kvadraticka rozsireni.
4. 12. 2023 Dedekindovo kriterium - pouze zneni, priklad pro f = x^5 - 2. Dvoufazova verze Pohst Zassenhausova algoritmu.
Norma idealu Z_K- multiplikatita a norma hlavniho idealu.
11. 12. 2023 Prvoidealy Z_K. Jak najit prvoidealy nad nespecialnimi provocisly
(trochu vice rozepsany dukaz je zde). Norma prvku tvaru (a-b\alpha), a,b cela.
19. 12. 2023 Faktorizace hlavnich idealu se specialnimi generatory. Prosivaci faze obecneho ciselneho sita.
8. 1. 2024 Zpracovani relaci, linearni faze a odmocninova faze ciselneho sita. Newtonova iteracni metoda (jak zhruba funguje,
nebude predmetem zkousky).
Info: Terminy ke zkousce nebudou vypisovany, lze je dohodnout mailem. Od 9. 2. do 18. 2. budu pravdepodobne v zahranici,
zkousku bude mozne tez slozit i v prubehu letniho semestru.
Literatura
[Pom] Carl Pomerance: The Tale of Two Sieves
[Per] Lukas Perutka: Hledani optimalnich strategii pro ciselne sito
(diplomka)
[L] A. K. Lenstra, H. W. Lenstra, M. S. Manasse, J. M. Pollard: The Factorization of the ninth Fermat number
zde
[D] Ales Drapal: Skripta k predmetu Komutativni okruhy
[C] Henri Cohen: A Course in Computational Algebraic Number Theory (str.
297)
[Cop] Don Coppersmith: Solving Homogenous Linear Equations Over GF(2)
via Block Wiedemann Algorithm
[M] Daniel Marcus: Number Fields