Teorie čísel a RSA 2017/18
Cílem předmětu je probrat základy teorie čísel: strukturu grup počítání modulo n Z_n a její aplikace testování prvočíselnosti a kryptosystém RSA. Dále využijeme komplexních čísel k řešení diofantických rovnic a důkazu zákona kvadratické reciprocity a ke konci semestru se podíváme na rozložení prvočísel a aproximace reálných čísel pomocí řetězových zlomků. Budeme převážně následovat skripta Aleše Drápala (kapitoly 2–5).
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.
Studenti, kteří nebudou spokojení s výsledkem písemky, se budou moci nechat ústně přezkoušet.
Zápočet není potřeba ke konání zkoušky.
Studenti, kteří nebudou spokojení s výsledkem písemky, se budou moci nechat ústně přezkoušet.
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 cca 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.
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ůžu někdy zadat celkem třeba 3 důkazy nebo 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
(odkazy jsou na sekce ze skript)
24. 5. řetězové zlomky (5.5 bez důkazu věty, 5.6 bez důkazů, 5.7)
17. 5. posloupnost dobrých aproximací (5.3, 5.4)
17. 5. posloupnost dobrých aproximací (5.3, 5.4)
10. 5. Ireducibilita cyklotomických polynomů (nebude u zkoušky; 3.6), 5. Řetězové zlomky: dobré aproximace (5.1)
3. 5. Cyklotomické polynomy, speciální případ věty o prvočíslech v aritmetické posloupnosti (Klazar str. 7, 8), náznak Čebyševových odhadů (Drápal 4.1, 4.2)
26. 4. Jacobiho symbol (3.8), aplikace na p=a^2+2b^2, 4. Existence prvočísel: začátek cyklotomických polynomů (částečně 3.6)
19. 4. kvadratické gaussovy součty a kvadratická reciprocita (3.5, 3.7)
12. 4. charaktery a gaussovy součty (dokončení důkazu tvrzení 3.2, sekce 3.4)
5. 4. 3. Charaktery a kvadratická reciprocita: gaussova celá čísla, prvočísla tvaru a^2+b^2, kvadratické zbytky (3.1, 3.2)
29. 3. Rabin-Millerův test, RSA (2.13, 2.14)
22. 3. Míjení involucí, začátek Rabin-Millerova testu (2.12, 2.13)
15. 3. 2. Faktorizace a prvočíselnost: valuace a struktura multiplikativních grup Z_{p^e}* (2.9, 2.10)
8. 3. Čínská zbytková věta (2.7, 2.8)
1. 3. Homomorfismy, invertibilní prvky, malá Fermatova a Wilsonova věta (2.4, 2.11, 2.5)
22. 2. 1. Cyklické grupy: Úvod, podgrupy Z a Z_n (víceméně 2.1 a 2.3)
Literatura
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
Příklady z mých prehistorických cvičení najdete tady.
