Teorie čísel a RSA 2018/19
Letní semestr 2018/19
Přednáška čtvrtek 14:00 v K2
Cvičení středa 15:40 v K3 nebo čtvrtek 12:20 v K5, obojí s Martinem Žuravem
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. Částečně budeme následovat skripta Aleše Drápala (kapitoly 2–4).
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.
V případě nejasností v písemce nebo hraničního počtu bodů může (spíš výjimečně) následovat ústní dozkoušení.
Zápočet není potřeba ke konání zkoušky.
V případě nejasností v písemce nebo hraničního počtu bodů může (spíš výjimečně) následovat ústní dozkoušení.
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ím je možné i opravné získání zápočtu za vyřešení většího množství úkolů po termínu.
Zkouškové termíny jsou vypsané v SISu; pokud vám vůbec nevyhovují, ozvěte se (včas!) a zkusíme se domluvit.
Vzorová písemka (= písemka z předtermínu).
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 mít víc otázek na 3. kapitolu, atd.Konzultace
Pokud máte zájem o konzultaci, dejte mi vědět osobně nebo emailem.
Průběh přednášky
(čísla v odkazech jsou sekce z příslušných skript)
23. 5. náznak Čebyševových odhadů (D 4.1, 4.2), ireducibilita cyklotomických polynomů (D 3.6, důkaz nezkouším)
16. 5. 4. Existence prvočísel: Cyklotomické polynomy, speciální případ věty o prvočíslech v aritmetické posloupnosti (K str. 7, 8, částečně D 3.6) 2. 5. Rabin-Millerův test, RSA (D 2.13, 2.14)
25. 4. Míjení involucí, začátek Rabin-Millerova testu (D 2.12, 2.13)
18. 4. 3. Faktorizace a prvočíselnost: Wilsonova věta, Fermatův test, valuace a struktura multiplikativních grup Z_{p^e}* (D 2.11, 2.9, 2.10)11. 4. důkaz reciprocity, Jacobiho symbol (D 3.8), aplikace na p=a^2+2b^2
4. 4. Gaussovy součty a kvadratická reciprocita (D 3.5, 3.7)
28. 3. charaktery a gaussovy součty (D důkaz tvrzení 3.2, sekce 3.4)21. 3. 2. Charaktery a kvadratická reciprocita: Gaussova celá čísla, prvočísla tvaru a^2+b^2, kvadratické zbytky (D 3.1, 3.2)
14. 3. sblížené zlomky dávají dobré aproximace (MP většina 6.4), periodické řetězové zlomky, aplikace na Pellovu rovnici (MP části 6.5 a 6.6)
7. 3. Sblížené zlomky (MP začátek 6.4), definice dobré aproximace
28. 2. existence řešení Pellovy rovnice (MP dokončení 5.6), řetězové zlomky a řetězové (=kontinuální) polynomy (MP 6.2, 6.3)
21. 2. 1. Řetězové zlomky: úvod, grupa řešení Pellovy rovnice, Dirichletova věta o aproximaci (MP 5.6)
Literatura
[D] Skripta Aleše Drápala (pozor, občas něco dělají jinak než my na přednášce a obsahují drobné překlepy)
[K] Skripta Martina Klazara
Můj loňský web.
Dřívější weby Honzy Žemličky a Štěpána Holuba.Příklady z mých prehistorických cvičení najdete tady.
