Teorie čísel a RSA 2019/20

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)

Diskuse a dotazy

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