Cvičení z teorie čísel a RSA
Čtvrtek 15:40 v K6
Zápočet dostanete za obdržení aspoň 65 bodů ze 100 ze 4 sad domácích úkolů. Po dohodě bude možné získat body dodatečným vyřešením většího počtu úloh. Úkoly můžete řešit společně, ale sepisovat každý zvlášť. Odevzdávejte je, prosím, před přednáškou.
První domácí úkol, odevzdat do 22. 3.
Druhý domácí úkol, odevzdat do 12.4.
Třetí domácí úkol, odevzdat do 3.5.
Čtvrtý domácí úkol, odevzdat do 17.5.
Pokud vám něco z přednášky nebo cvičení není jasné, nebojte se zeptat, buď osobně na cvičení nebo e-mailem (martinxcech na gmail.com). Budu rád za jakoukoliv zpětnou vazbu, ať už osobně nebo mailem.
Budu rád, když vyplníte anketu. Kdyby vás zajímalo, jaké je studium struktur, jaký je Víťa vedoucí nebo cokoliv jiného, klidně mi napište :)
Dění na cvičeních
1. cvičení: Příklady grup, homomorfismy, generátory grup, základy dělitelnosti. Příklady z prvního cvičení.
2. cvičení: Cyklické grupy, řád prvku a primitivní prvky, Malá Fermatova věta, Eulerova věta. Příklady z druhého cvičení.
3. cvičení: Řešení soustav kongruencí, hledání izomorfismů pomocí Čínské zbytkové věty, řešení rovnic pomocí nalezení primitivního prvku.
4. cvičení: p-valuace, cykličnost multiplikativních grup Z_n a jejich rozklad na součin. Příklady ze čtvrtého cvičení.
5. cvičení: Hledání primitivních prvků modulo mocniny prvočísel, rozklad multiplikativních grup na součin cyklických, involuce. Příklady z pátého cvičení.
6. cvičení: Míjení prvků, rychlé mocnění modulo n, Rabin-Millerův test. Příklady ze šestého cvičení.
7. cvičení: Šifrování pomocí RSA. Příklady ze sedmého cvičení. Řešení posledního příkladu je na wikipedii.
Tady je pěkný článek o útocích na RSA.
8. cvičení: Gaussova celá čísla -- norma, invertibilní prvky, prvočinitele; kvadratické zbytky. Příklady z osmého cvičení.
9. cvičení: Kvadratické zbytky, Legendreův symbol, zákon kvadratické reciprocity, charaktery. Příklady z devátého cvičení.
10. cvičení: Jacobiho symboly, jejich souvislost s řešitelností kongruencí s x2, charaktery. Příklady z desátého cvičení.
11. cvičení: Speciální případy Dirichletovy věty s použitím kvadratické reciprocity, charaktery. Příklady z jedenáctého cvičení.
12. cvičení: Pellova rovnice, řešení Diofantických rovnic pomocí rozkladu v Gaussových oborech. Příklady z dvanáctého cvičení.
13. cvičení: Diofantické rovnice, prvočísla tvaru a2 - ab + b2. Příklady z třináctého cvičení.
14. cvičení: Řetězové zlomky a dobré aproximace, periodicita ř.z. odmocnin a využití pro hledání fundamentálního řešení Pellovy rovnice.
Příklady ze čtrnáctého cvičení.
Tady najdete diplomovou práci Maroše Hrnčiara o řešení Diofantických rovnic rozkladem v číselném tělese. Pro nás jsou zajímavé sekce 4.1-4.5.
Tady najdete seriál o komplexních číslech napsaný organizátory matematického korespondenčního semináře, 3. díl (od strany 29) je o využití komplexních čísel při řešení diofantických rovnic, tj. o Gaussových a Eisensteinových celých číslech.