Teorie čísel a RSA 2019/20
NMMB206
Letní semestr 2019/20
Přednáška ve středu 15:40 (K3)
Cvičení se Žanetou Semanišinovou v úterý 17:20 (K9) a čtvrtek 17:20 (K5)
Cílem předmětu je probrat základy teorie čísel: Začneme aproximacemi reálných čísel pomocí řetězových zlomků a Pellovou rovnicí. Dále využijeme komplexních čísel k řešení diofantických rovnic a důkazu zákona kvadratické reciprocity. Ke konci semestru se podíváme na rozložení prvočísel a strukturu grup počítání modulo n Z_n a její aplikace testování prvočíselnosti a kryptosystém RSA. Primárně budeme používat má nová skripta.
Zkouška
Zkouška bude písemná s několika teoretickými i početními otázkami pokrývajícími látku probranou na přednášce a cvičení. Písemka bude na 90 minut, smí se u ní používat (ne přehnaně inteligentní) kalkulačky.
Po písemce může následovat ústní dozkoušení, zejména v případě distančního konání zkoušky (nebo při nejasnostech v prezenční písemce nebo hraničním počtu bodů).
Zápočet není potřeba ke konání zkoušky.
K získání zápočtu bude třeba úspěšně vyřešit 4 sady domácích úkolů (zadaných na cvičeních). Po dohodě s cvičící je možné i opravné získání zápočtu za vyřešení většího množství úkolů po termínu.
Vzorová písemka (z předtermínu)
I v dalších písemkách půjde celkem získat 50 bodů a bodové hranice na známky budou podobné jako tady.
Pozor, další písemky se od této (samozřejmě!) budou lišit. Například v tom, ze kterých sekcí budou důkazy, resp. početní příklady, nebo může být víc otázek na 1. kapitolu atd.
Jinak upozorňuju, že letos plánuju otázky do písemky částečně losovat, takže to, že se např. nějaký důkaz už objevil ve vzorové písemce nebo v dřívějším termínu, nic neříká o tom, jestli se (ne)objeví znovu.
Materiál ze skript, který nebudu zkoušet: důkaz tvrzení 1.12, důkaz druhé implikace ve větě 1.13, důkaz lemmatu 2.8b (zkouším jen pro n=p prvočíslo), sekci 2.7, důkaz věty 3.1, alternativní sekci 3.2*, důkazy v sekci 4.4.
Konzultace
Pokud chcete cokoli probrat, napište mi email (pokud by šlo o něco rozsáhlejšího, můžeme se např. domluvit na Skype nebo Google Hangouts). Nebo se ptejte v diskusi.
Skripta – jde o má nová skripta, víceméně finální. Rozhodně ale uvítám upozornění na překlepy a návrhy na vylepšení!
Starší verze skript je tady (obsahuje víc informací o průběhu přednášky v roce 2019/20, ale není už aktualizovaná).
Průběh přednášky
Odkazy jsou na má skripta, viz také odkazy na videokomentáře ke skriptům níže.
20. 5. bonus: Úvod do L-funkcí a Langlandsova programu
odkazy: prezentace, populární článek
13. 5. náznak Čebyševových odhadů, ireducibilita cyklotomických polynomů (sekce 4.3, 4.4). Nezkouším důkazy v sekci 4.4.
6. 5. 4. Existence prvočísel: Cyklotomické polynomy, speciální případ věty o prvočíslech v aritmetické posloupnosti (od začátku kapitoly 4 do konce sekce 4.2)
29. 4. proč Rabin-Millerův test funguje, RSA (sekce 3.5, 3.6)
22. 4. Rabin-Millerův test, míjení involucí (sekce 3.3, 3.4)
Bonus 2
15. 4. 3. Faktorizace a prvočíselnost: úvod, valuace a struktura multiplikativních grup Z_{p^e}* (od začátku kapitoly 3 do konce sekce 3.2, bez důkazu věty 3.1)
8. 4. důkaz reciprocity, Jacobiho symbol, aplikace na p=a^2+2b^2 (dokončení kapitoly 2). Sekci 2.7 nebudu zkoušet, ale přečtěte si ji – je zajímavá (a částečně se objeví na cvičení) 🙂
1. 4. Gaussovy součty a okruh Z[zeta_p] (sekce 2.4 a 2.5 po důsledek 2.15 včetně)
Bonus
25. 3. charaktery (sekce 2.3). Přednáška tento týden je o něco kratší, abyste měli prostor vstřebat homomorfismy a izomorfismy – je mi jasné, že to nějaké úsilí zabere. Nebojte se ptát!
18. 3. prvočísla tvaru a^2+b^2, kvadratické zbytky (sekce 2.1, 2.2)
11. 3. periodické řetězové zlomky, aplikace na Pellovu rovnici (sekce 1.7, 1.8). 2. Charaktery a kvadratická reciprocita: gaussovská celá čísla, prvočinitele v Z[i] (sekce 2.1 po důkaz lemmatu 2.1 včetně)
4. 3. Sblížené zlomky, definice dobré aproximace, sblížené zlomky dávají dobré aproximace (do konce sekce 1.6)
26. 2. Dirichletova věta o aproximaci, existence řešení Pellovy rovnice, řetězové zlomky a řetězové polynomy (do konce sekce 1.4)
19. 2. 1. Řetězové zlomky: úvod, grupa řešení Pellovy rovnice, aproximace reálných čísel (před větu 1.2)
Videa
Případné opravy k drobným chybám píšu vždycky jako komentáře k danému videu na youtube.
Úvod do L-funkcí a Langlandsova programu (bonusová přednáška): část 1, část 2, část 3
4. Existence prvočísel
Úvod
Cyklotomické polynomy, (sekce 4.1): celek
Prvočísla kn+1 (sekce 4.2): celek
Čebyševův odhad (sekce 4.3): celek
Ireducibilita cyklotomických polynomů (sekce 4.4): celek
3. Faktorizace a prvočíselnost
Úvod
Valuace a mocniny (sekce 3.1): celek
Struktura multiplikativní grupy Z_{p^e}* (sekce 3.2): část 1, část 2
Bonus 2
Rabin-Millerův test (sekce 3.3): celek
Míjení involucí (sekce 3.4): část 1, část 2
Počet lhářů (sekce 3.5): část 1, část 2
RSA (sekce 3.6): celek
2. Charaktery a kvadratická reciprocita
Gaussovská celá čísla (sekce 2.1): část 1, část 2
Kvadratické zbytky (sekce 2.2): část 1, část 2
Charaktery (sekce 2.3): část 1, část 2, část 3
Gaussovy součty (sekce 2.4): část 1, část 2, část 3
Zákon reciprocity (sekce 2.5): část 1, část 2
Bonus
Jacobiho symbol (sekce 2.6): část 1, část 2
Aplikace (sekce 2.7): celek
Literatura
Skripta – jde o pracovní verzi mých nových skript.
Skripta Aleše Drápala (pozor, občas něco dělají jinak než my na přednášce a obsahují drobné překlepy)
Skripta Martina Klazara
Zuzana Masáková, Edita Pelantová, Teorie čísel, skripta pro FJFI ČVUT
Můj loňský web. Letošní přednáška bude podobná té loňské.
Dřívější weby Honzy Žemličky a Štěpána Holuba.
Příklady z mých prehistorických cvičení najdete tady.
