Teorie čísel a RSA 2018/19

NMMB206

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.

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

[MP] Zuzana Masáková, Edita Pelantová, Teorie čísel, skripta pro FJFI ČVUT

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.

at Shingo La (5000 m.)