Studijní program P4M1 Algebra, teorie čísel a matematická logika

Oborová rada

Aktuální složení rady je na adrese http://mff.cuni.cz/phd/or/p4m1.

Spolupracující ústavy

– Matematický ústav AV ČR, v.v.i.
Žitná 25, 115 67 Praha 1
http://www.math.cas.cz

– Ústav informatiky AV ČR, v.v.i.
Pod Vodárenskou věží 2, 182 07 Praha 8
http://www.ustavinformatiky.cz/

Vypsaná témata

Jsou k nahlédnutí v SIS na adrese http://mff.cuni.cz/phd/temata/p4m1.

Poskytovaná výuka

kód	Předmět		ZS	LS
NAIL056	Logický seminář I		0/2 Z	—
NAIL080	Logický seminář II		—	0/2 Z
NDMI045	Analytická a kombinatorická teorie čísel		—	2/0 Zk
NMAG265	Studentský seminář z teorie množin		0/2 Z	—
NMAG405	Universální algebra 1		2/2 Z+Zk	—
NMAG407	Teorie modelů		2/0 Zk	—
NMAG446	Logika a složitost		—	2/0 Zk
NMAG450	Universální algebra 2		—	2/1 Z+Zk
NMAG455	Kvadratické formy a třídová tělesa I		2/0 Zk	—
NMAG456	Kvadratické formy a třídová tělesa II		—	2/0 Zk
NMAG462	Modulární formy a L-funkce I		2/0 Zk	—
NMAG466	Teorie svazů 2		—	2/0 Zk
NMAG470	Seminář z teorie čísel		0/2 Z	0/2 Z
NMAG473	Modulární formy a L-funkce II		—	2/0 Zk
NMAG475	Výběrový seminář z MSTR		0/2 Z	0/2 Z
NMAG498	Výběrová přednáška z MSTR 1		2/0 Zk	—
NMAG499	Výběrová přednáška z MSTR 2		—	2/0 Zk
NMAG531	Aproximace modulů		—	2/0 Zk
NMAG536	Důkazová složitost a P vs. NP problém		—	2/0 Zk
NMAG562	Homologická a homotopická algebra		2/0 Zk	—
NMAG563	Úvod do složitosti CSP		2/0 Zk	—
NMAG565	Algebra a nekonečná kombinatorika		2/0 Zk	—
NMAG567	Reprezentace grup 2		2/2 Z+Zk	—
NMAG571	Algebraický seminář		0/2 Z	0/2 Z
NMAG573	Seminář k problému CSP		0/2 Z	0/2 Z
NMIN160	Teorie množin		2/0 Zk	—
NMMB451	Aplikace matematiky v informatice		—	0/2 Z
NMMB452	Seminář z matematiky inspirované kryptografií		0/2 Z	0/2 Z
NMMB453	Studentský logický seminář		0/2 Z	0/2 Z
NMMB471	Výběrový seminář z MIT		—	0/2 Z
NMMB498	Výběrová přednáška MIT 1		2/0 Zk	—
NMMB499	Výběrová přednáška MIT 2		—	2/0 Zk
NMMB551	Seminář z kombinatorické, algoritmické a finitní algebry		0/2 Z	0/2 Z
NMMB621	Doktorandský seminář z kryptologie		0/2 Z	0/2 Z
NTIN071	Automaty a gramatiky		—	2/2 Z+Zk
NTIN090	Základy složitosti a vyčíslitelnosti		2/1 Z+Zk	—
NMAG575	Forsing		2/0 Zk	—
NMAG576	Seminář z forsingu		—	0/2 Z
NLTM014	Nestandardní seminář 1		0/2 Z	—
NLTM015	Nestandardní seminář 2		—	0/2 Z
NMAG577	Seminář z počtů		0/2 Z	0/2 Z
NTIN062	Složitost I		2/1 Z+Zk	—
NTIN064	Vyčíslitelnost		—	2/0 Zk
NTIN073	Rekurze		2/0 Zk	—
NTIN088	Algoritmická náhodnost		—	2/0 Zk
NMAI067	Logika v informatice		2/0 Zk	—
NAIL021	Booleovské funkce a jejich aplikace		2/0 Zk	—
NMAI040	Úvod do teorie čísel		2/0 Zk	—
NDMI066	Algebraická teorie čísel		2/0 Zk	—

Seznam požadavků ke státní doktorské zkoušce

Student si po dohodě se školitelem vybere jednu ze tří specializací: ,,Algebra", ,,Matematická logika" nebo ,,Teorie čísel." Státní doktorskou zkoušku koná ve vybrané specializaci podle následujícího seznamu požadavků:

Algebra

I. Širší základ
Povinná část.

I.1 Základy algebry
Teorie grup: konečné grupy, Sylowovy věty, struktura konečně generovaných komutativních grup, volné grupy a jejich podgrupy.

Galoisova teorie: Galoisova rozšíření a grupy, radikálová rozšíření těles, neřešitelnost polynomiálních rovnic v radikálech.

Teorie reprezentací a algebraická geometrie: Reprezentace konečných grup, Maschkeho věta, charaktery. Korespondence mezi afinními algebraickými množinami a ideály okruhů polynomů, Hilbertova věta o nulách.

Univerzální algebra: Variety algeber, subdirektní rozklady, volné algebry, Birkhoffova věta. Svazy, úplné svazy, uzávěrové operátory, Galoisovy korespondence.

II. Pokročilé partie
Studující si vybere po dohodě se školitelem dvě různá témata z pokročilých partií specializace ,,Algebra'', ,,Teorie čísel'' nebo ,,Matematická logika.'' Aspoň jedno z nich ale musí být některé z následujících (II.1–II.10):

II.1. Teorie grup
Akce grupy na množině. Permutační, řešitelné a nilpotentní grupy. Lineární grupy. Jenoduché konečné grupy, jednoduchost A_n a PSL_n(K). Základy teorie rozšíření grup, semidirektní součiny grup. Indukované reprezentace grup a Frobeniova reciprocita, Mackeyova věta a její důsledky.

II.2 Binární systémy
Levodistributivní grupoidy (volné, monogenerované, problém slov), souvislost s grupami pletenců. Mediální a oboustranně distributivní grupoidy, rovnicová teorie mediálních idempotentních grupoidů. Normální podkvazigrupy a kongruence lup a kvazigrup, nuklea, centrum, nilpotence. Vazby na multiplikační grupu. LCC, CC, extra, bolovské a moufangovské lupy. Inverzní vlastnosti, diasociativita. Izotopie, centrální a mediální kvazigrupy. Toyodova věta.

II.3 Komutativní algebra
Komutativní noetherovské okruhy: spektrum, lokalizace, primární rozklady. Celistvá rozšíření, Dedekindovy obory, faktorizace ideálů. Lokalizace a zúplnění modulů. Krullova věta o hlavních ideálech. Regulární posloupnosti, hloubka, Auslander–Buchsbaumova věta.

II.4 Algebraická geometrie
Afinní a projektivní algebraické množiny, Zariského topologie, rozklad na ireducibilní komponenty. Funkční tělesa, racionální zobrazení, biracionální ekvivalence. Homomorfismy algebraických množin, projektivní eliminace, uzavřenost morfismů z projektivních algebraických množin. Bézoutova věta. Krullova dimenze a její vlastnosti.

II.5 Teorie modulů a homologická algebra
Projektivní a injektivní moduly. Řetězcové podmínky na ideály, Hopkinsova-Levitzkého věta, Faitova charakterizace noetherovskosti. Moritova ekvivalence. Kategorie modulů, tenzorový součin, funktory Ext a Tor, dlouhé exaktní posloupnosti. Direktní limity, čistá vnoření, čistě–injektivní moduly a modelově–teoretické souvislosti. Derivované kategorie.

II.6 Aproximace modulů a nekonečná kombinatorika
Kotorzní páry, filtrace, Eklofovo lemma a Hillovo lemma. Dekonstruovatelnost pro regulární a singulární kardinály (závislost na rozšíření ZFC, Shelahova věta o singulární kompaktnosti). Struktura Whiteheadových a Baerových modulů.

II.7 Reprezentace algeber konečné dimenze
Konečně dimenzionální algebry jako faktory algeber cest grafů. Krullova-Schmidtova věta. Konečný, krotký a divoký reprezentační typ. Dědičné algebry a Gabrielova charakterizace konečného reprezentačního typu. Vychylující moduly a vychýlené algebry. Skoro štěpitelná zobrazení, AR–posloupnosti, AR–graf konečně dimenzionální algebry.

II.8 Univerzální algebra a teorie svazů
Malcevské podmínky. Abelovskost a komutátor v obecných algebrách. Rovnicové teorie, přepisující systémy a Knuthův-Bendixův algorithmus, konečně bázované variety. Distributivní, modulární, semimodulární a geometrické svazy, kongruence svazů, volné svazy a problém slov. Jónssonovo lemma a variety svazů.

II.9 Univerzálně algebraické metody v CSP
Relační a algebraické klony, homomorfismy klonů a primitivně pozitivní interpretace relačních struktur. Složitost CSP a klony polymorfismů, Taylorovy klony, malcevské CSP a problémy konečné šířky, Schaeferova věta o klasifikaci CSP nad dvouprvkovou množinou.

II.10 Kombinatorika na slovech
Dicksonovo lemma. F–pologrupy (minimální množina generátorů, kódy, podmínka stability, řády pologrupy). Chomskeho hierarchie (formální gramatiky a odpovídající automaty, Kleenova věta, pumpovací lemmata, Parikhova věta). Rovnice ve volných monoidech (věta o kompaktnosti, grafové lemma, vlastnosti defektu, ekvivalenční a testovací množiny). Postův korespondenční problém.

Doporučená literatura

–Anderson, F. W., Fuller, K. R.: Rings and Categories of Modules. GTM 13. 2nd ed. Springer, New York, 1992.

–Assem I., Simson, D., Skowronski, A.: Elements of the Representation Theory of Associative Algebras I. LMSST 65. Cambridge University Press, Cambridge, 2006.

–Atiyah, M. F., Macdonald, I. G.: Introduction to commutative algebra. Addison-Wesley Publishing Co., 1969.

–Auslander M., Reiten, I., Smalo. S. O.: Representation theory of Artin algebras. Cambridge University Press, Cambridge, 1997.

–Barto L., Krokhin, A., Willard, R.: Polymorphisms, and how to use them. Dagstuhl Follow-Ups. Vol. 7. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017.

–Bergman C.: Universal Algebra: Fundamentals and Selected Topics. Chapman and Hall/CRC, 2011.

–Berstel, J., Perrin, D.: Theory of Codes. Academic Press, London, 1985.

–Bruck, R. H.: A Survey of Binary Systems. Springer, Berlin, 1971.

–Bruns, W., Herzog, J.: Cohen–Macaulay Rings. CSAM 39. Cambridge University Press, Cambridge, 1998.

–Bulatov, A., Krokhin, A., Larose, B.: Dualities for constraint satisfaction problems. In: Complexity of Constraints, LNCS 5250. Springer, New York, 2008.

–Bulatov, A., Valeriote, M.: Results on the algebraic approach to the CSP. Proc. Dagstuhl Sem., LNCS, Springer, New York, 2008.

–Burris, S., Sankappanavar, H. P.: A Course in Universal Algebra. Springer, New York, 1981.

–Cox, D. A., Little, J., O'Shea, D.: Ideals, varieties, and algorithms. 4th edition. Springer, Cham, 2015.

–Crawley, P., Dilworth, R. P.: Algebraic Theory of Lattices. Prentice Hall, 1973.

–Dehornoy, P.: Braids and Self Distributivity. Birkhauser. Basel, 2000.

–Eilenberg, S.: Automata, languages and machines A and B. Academic Press, 1973, 1974.

–Eisenbud, D.: Commutative Algebra. GTM 150. Springer, New York, 1995.

–Eklof, P. C., Mekler, A. H.: Almost–Free Modules. 2nd ed. Elsevier, Amsterdam, 2002.

–Enochs, E. E., Jenda, O. M. G.: Relative Homological Algebra. Vol. 1,2. GEM 30, 54. 2nd ed. W. de Gruyter, Berlin, 2011.

–Facchini, A.: Module Theory. Birkhauser, Basel, 1998.

–Fulton, W.: Algebraic Curves. Reprint of 1969 original. Addison-Wesley Publishing Company, 1989.

–Goebel, R., Trlifaj, J.: Approximations and Endomorphism Algebras of Modules. Vol. 1,2. GEM 41. 2nd ed. W. de Gruyter, Berlin, 2012.

–Goertz, U., Wedhorn, T.: Algebraic geometry I. Advanced Lectures in Mathematics. Vieweg + Teubner, Wiesbaden, 2010.

–Gratzer, G.: General Lattice Theory. 2nd ed. Birkauser, Basel, 1998.

–Hobby, D., McKenzie, R.: The structure of finite algebras. Contemp. Math. 76. AMS, Providence, 1988.

–Jezek, J.: Universal Algebra. Text přístupný na http://www.karlin.mff.cuni.cz/~jezek.

–Lallement, G.: Semigroups and combinatorial applications. Wiley, 1979.

–Lang, S.: Algebra. 3rd ed. Academic Press, New York, 1993.

–Lothaire, M.: Algebraic Combinatorics on Words. Cambridge University Press, Cambridge, 2002.

–Lothaire, M.: Applied Combinatorics on Words. Cambridge University Press, Cambridge, 2005.

–Lothaire, M.: Combinatorics on Words. Cambridge University Press, Cambridge, 1997.

–Matsumura, H.: Commutative Ring Theory. CSAM 8. Cambridge University Press, Cambridge, 1994.

–Pflugfelder, H. O.: Quasigroups and Loops: Introduction. Heldermann Vlg, Berlin, 1990.

–Prest, M.: Purity, spectra and localisation. Cambridge University Press, Cambridge, 2009.

–Prochazka, L. a kolektiv: Algebra. Academia, Praha, 1990.

–Rotman, J. J.: An introduction to the theory of groups. Springer, New York, 1995.

–Rotman, J. J.: An introduction to homological algebra. 2nd edition. Springer, New York, 2009.

–Rowen, L .H.: Graduate Algebra: Commutative View. GSM 73. AMS, Providence, 2006.

–Rowen, L. H.: Graduate Algebra: Noncommutative View. GSM 91. AMS, Providence, 2008.

–Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages, vol. 1 – 3. Springer, 2004.

–Shafarevich, I. R.: Basic algebraic geometry 1 3rd edition. Springer, Heidelberg, 2013.

–Weibel, C.: An Introduction to Homological Algebra. CSAM 38. Cambridge University Press, Cambridge, 1994.

–Weintraub, S. H.: Representation Theory of Finite groups. GSM 59. AMS, Providence, 2003.

Matematická logika

I. Širší základ
Povinná část.

I.1 Základy logiky
Výroková logika a logika prvního řádu. Struktury prvního řádu, Tarského definice splňování. Predikátový počet, dokazatelnost. Věty o úplnosti a o kompaktnosti. Teorie množin jako teorie prvního řádu. Gödelova věta o neúplnosti a o nedokazatelnosti bezespornosti. Turingovy stroje: universální stroj, algoritmicky nerozhodnutelné problémy, halting problem. Eliminace kvantifikátorů v uspořádaném tělese reálných čísel.

II. Pokročilé partie
Studující si vybere po dohodě se školitelem dvě různá témata z pokročilých partií specializace ,,Algebra'', ,,Teorie čísel'' nebo ,,Matematická logika.'' Aspoň jedno z nich ale musí být některé z následujících (II.1–II.6):

II.1. Obecná teorie modelů
Základní pojmy: podstruktura a elementární podstruktura, diagram, homomorfisimus, vnoření a elementární vnoření, isomorfismus. Löwenheim–Skolemovy věty. Modelová úplnost. Definovatelné množiny, typy, eliminace kvantifikátorů. Konstrukce modelů: pomíjení typů, Henkinova konstrukce, Skolemizace. Craigova interpolace, elementarní řetězce, Robinsonova věta o bezespornosti, nerozlišitelné prvky. Saturované a homogenní modely, prvomodely. Ultraprodukt a jeho zakladní vlastnosti. Elementarní třídy.

II.2 Aplikovaná teorie modelů
Realně uzavřená uspořádaná tělesa a jejich redukty a rozšíření, Věty Tarského a Wilkiova. O–minimálni struktury a jejich základní geometrické a topologické vlastnosti. Stabilní a omega–stabilní teorie, nespočetná kategoričnost, Morleyho věta. Minimální a silně minimalní struktury, obecné uzávěrové operace, geometrie a dimense v silně minimálních strukturách. Omega–stabilní grupy, Cherlin–Zilberova hypotéza. Hrushovského amalgamačni metoda.

II.3. Teorie množin
Axiomatika teorie ZFC. Axiom výběru AC, Zornovo lema, dobrá uspořádání. Ordinální a kardinální aritmetika, transfinitní indukce. Nekonečná kombinatorika: nezávislé a skorodisjunktní systémy množin, Ramseyova věta, uzavřené a neomezené množiny a stacionární množiny, diamantový princip, Martinův axiom. Stromy (Suslinovy, Aronszajnovy, Kurepovy), Suslinova hypotéza. Booleovy algebry, ultrafiltry, Stoneova dualita. GCH. Konstruktivní množiny, axiom V=L. GCH a AC v L. Forcing a Booleovské modely, nezávislost CH. Nedosažitelné a měřitelné kardinály, elementární vnoření. Deskriptivní teorie množin: Borelovské, analytické a projektivní množiny, nekonečné hry, determinovanost. Uniformizační věty. Borelovské ekvivalence. Polské prostory, Polské grupy a jejich akce.

II.4. Teorie vyčíslitelnosti
Částečně rekurzivní funkce, rekurzivní množiny a rekurzivně spočetné množiny. Univerzální částečně rekurzivní funkce, index. Věty o rekurzi, Riceova věta. Kreativní množiny. Efektivní neoddělitelnost. Operace skoku. Aritmetická hierarchie. Stupně nerozhodnutelnosti. Aritmetický forcing, prioritní metody. Kolmogorovská složitost, základy algoritmické náhodnosti.

II.5 Teorie důkazů a formální aritmetika
Gentzenův sekvenční kalkulus, eliminace řezu, Herbrandova věta. Craigova interpolace. Robinsonova aritmetika Q a Peanova aritmetika PA. Interpretovatelnost teoríi. Nerozhodnutelnost Q a PA. Dokazatelně totální rekursivní funkce. Nemožnost konečné axiomatizace PA. Logika druhého řádu, jednoduchá teorie typů, infinitární logika. Reversní matematika. Neklasické logiky: intuitionistická, modální, vícehodnotové.

II.6 Logika a složitost
Časová a prostorová složitost algoritmů, hlavní třídy složitosti. Boolovské obvody a hlavní známé spodní odhady na jejich velikost. Koncept přirozených důkazů spodních odhadů (Razborov–Rudich). Teorie konečných modelů, deskriptivní složitost. Definovatelnost v konečných strukturách, Faginova věta. Logiky s operátorem pevného bodu. 0–1 zákony. Ehrenfeucht–Fraissého metoda. Lokalita a věty Gaifmana a Hanfa. Oblázkové hry. Problém spektra. Důkazová složitost, vyrokové důkazové systémy (Cook–Reckhow). Resoluce, DPLL algoritmus pro SAT a jejich souvislost. Fregeho systémy a rozšířené Fregeho systémy. Spodní odhad na délku důkazů v resoluci. Omezená aritmetika. Definovatelnost polynomiální hierarchie. Dosvědčovací funkce a vyhledávací problémy. Překlady do výrokové logiky. Problém konečné axiomatizovatelnosti omezené aritmetiky.

Doporučená literatura

–Balcar, B., Stěpánek, P.: Teorie množin. Academia, Praha, 1986, 2001.

–Bartoszynski, T., Judah, H.: Set Theory, On the Structure of Real Line. A. K. Peters, Wellesley, Massachussets, 1995.

–Barwise, J. (ed.): Handbook of Mathematical Logic. NHPC, 1972 (rusky Nauka, Moskva, 1982).

–Buss, S. R. (ed.): Handbook of Proof Theory, Studies in Logic and the Foundations of Mathematics 137. Elsevier, Amsterdam, 1998.

–Cook, S. A., Nguyen, P.: Logical foundations of proof complexity. Cambridge University Press.

–Demuth, O., Kryl, R., Kučera, A.: Teorie algoritmů I, II. SPN, Praha, 1984, 1989.

–Devlin, K. J.: Constructibility. Springer–Verlag, Heidelberg, 1984.

–Dries van den, L.: Tame Topology and O–minimal Structures. London Mathematical Society Lecture Note Series, no. 248, 1998.

–Ebbinghaus, H.–D., Flum, J., Thomas, W.: Mathematical Logic. Springer–Verlag, Heidelberg, 1984.

–Ebbinghaus, H.–D., Flum, J.: Finite Model Theory. Springer–Verlag, 2005.

–Gabbay, D., Guenthner, F. (eds.): Handbook of Philosophical Logic I–IV. D. Riedel Publishing comp., 1983.

–Hájek, P., Pudlák, P.: Metamathematics of First–Order Arithmetic. Springer–Verlag, Heidelberg, 1993.

–Hodges, W.: Model Theory. Cambridge University Press, Cambridge, 1993.

–Chang, C. C., Keisler, H. J.: Model–Theory. NHPC, New York, 1973 (rusky Mir, Moskva, 1977).

–Jech, T.: Set Theory. Springer–Verlag, 2002.

–Kechris, A.: Classical descriptive set theory. Springer–Verlag, New York, 1994.

–Krajíček, J.: Bounded arithmetic, propositional logic, and complexity theory. Cambridge University Press, Cambridge, 1995.

–Kunen, K.: Set Theory, An Introduction to Independence Proofs. NHPC, New York, 1980.

–Laxembourgh, W. A. J., Stroyan, K. D.: Introduction to the Theory of Infinitesimals. Academic Press, London, 1976.

–Li, M., Vitanyi, P.: An Introduction to Kolmogorov Complexity and Its Applications. Springer, 1997.

–Marker, D.: Model Theory — An Introduction. Springer, 2002.

–Moschovakis, Y.: Descriptive Set Theory. North–Holland, 1980.

–Odifreddi, P.: Classical Recursion Theory. The Theory of Functions and Sets of Natural Numbers. NHPC, New York, 1989.

–Papadimitriou, C. H.: Computational Complexity. Addison Wesley, 1994.

–Pillay, A.: Geometric Stability Theory. Clarendon Press, Oxford, 1996.

–Priest, G.: An Introduction to Non–Classical Logic Cambridge University Press, 2001.

–Rogers, H., Jr.: Theory of Recursive Functions and Effective Computability. Mc Graw–Hill, New York, 1967.

–Shelah, S.: Classification Theory. NHPC, New York, 1990.

–Shelah, S.: Proper and Unproper Forcing. Springer–Verlag, Heidelberg, 1998.

–Shoenfield, J. R.: Mathematical Logic. Addison Wesley Publishing Company, Reading, 1967 (rusky Nauka, Moskva, 1975).

–Simpson, S.: Subsystems of second order arithmetic. Springer–Verlag, New York, 1999.

–Soare, R. I.: Recursively Enumerable Dets and Degrees, A Study of Computable Functions and Computably Generated Sets. Springer–Verlag, Heidelberg, 1987.

–Takeuti, G.: Proof Theory. Elsevier, Amsterdam, 1987.

Teorie čísel

I. Širší základ
Základy teorie čísel: Hustota prvočísel, Legendreovy a Jacobiho symboly, kvadratická reciprocita, řetězové zlomky, kvadratická číselná tělesa, Rabinův–Millerův algoritmus a RSA.

Algebraická teorie čísel: číselná tělesa, existence celistvé báze, Dedekindovskost. Větvení a štěpení prvočísel. Geometrie čísel, třídové číslo, Dirichletova věta o jednotkách. Cyklotomická tělesa, řešení diofantických rovnic. p–adická čísla.

Počítačová algebra: Berlekampův algoritmus pro faktorizaci polynomů. Groebnerovy báze a Buchbergerův algoritmus. Faktorizace polynomů s celočíselnými koeficienty.

II. Pokročilé partie oboru
Studující si vybere po dohodě se školitelem dvě různá témata z pokročilých partií specializace ,,Algebra'', ,,Teorie čísel'' nebo ,,Matematická logika.'' Aspoň jedno z nich ale musí být některé z následujících (II.1–II.6):

II.1 Kryptologie a faktorizace
Generátory pseudonáhodných čísel, symetrické a proudové šifry, hašovací funkce, dokazatelná bezpečnost, kryptografické protokoly, důkazy s nulovou znalostí. Číselné síto a jeho dílčí algoritmy (hledání odmocniny, volba polynomu aj.). Další faktorizační algoritmy (p-1, p+1, rho, použití eliptických křivek) a jejich význam pro číselné síto. Testy a důkazy prvočíselnosti (kvadratický Frobeniův, N-1 test, ECPP, algoritmy pracující v polynomiálním čase).

II.2 Pokročilé kryptoanalytické metody
Teorie booleovských funkcí, S–boxy, jejich kryptografické vlastnosti, lineární a diferenciální kryptoanalýza, LLL–algoritmus a jeho kryptoanalytické aplikace.

II.3 Samoopravné kódy
Klasická teorie cyklických kódů. Samoduální kódy a teorie invariantů. Konvoluční kódy. Turbo kódy. Dekódovací algoritmy, zejména Viterbiho a různé algoritmy pro Reed–Solomonovy kódy. Kvaternární kódy. Pokrývací poloměr a aplikace ve steganografii. Podrobná znalost BCH, alternatních, Kerdockových, Preparatových, Justensenových, Reedových–Mullerových a QR kódů. Asymptotické odhady a konstrukce asymptoticky dobrých kódů. LDPC kódy. MDS kódy. Základní odhady (Plotkin, Hamming, Griesmer, Singleton, Johnson, Gilbert–Varšamov, lineární programování).

II.4 Eliptické křivky
Variety nad konečnými tělesy (Frobeniův morfismus, Hasse–Weilova věta pro jakobián, Tatova věta). Aritmetika eliptických křivek (grupový zákon, racionální body, torzní body, izomorfismy a izogenie). Montgomeryho skalární násobení. Párování a jeho implementace. Výpočet počtu bodů (elementární metody, Schoofův a Satohův algoritmus, komplexní násobení). Výpočet diskrétního logaritmu (činská věta o zbytku, baby–step giant–step, Pollardovy metody). Kryptografie založená na párování. Použití eliptických křivek pro faktorizaci a testy prvočíselnosti.

II.5 Algebraická teorie čísel II
Kvadratické formy: grupa tříd binárních forem, teorie rodů, prvočísla reprezentovaná binárními formami, univerzální formy, Hasseho-Minkowského věta, Hilbertův symbol. Adély a idély, lokálně kompaktní grupy. Globální a lokální teorie třídových těles.

II.6 Analytická teorie čísel
L-funkce: Riemannova zéta-funkce, Dirichletovy L-funkce, Eulerův součin, meromorfní rozšíření, funkcionální rovnice, Dirichletova věta o aritmetické posloupnosti. Modulární formy: Základní vlastnosti, dimenze prostoru modulárních forem. Fourierův rozvoj, Eisensteinovy řady. Heckeho operátory, aplikace.

Doporučená literatura

–Cassels, J. W. S.: Local Fields. Cambridge University Press, Cambridge, 1986.

–Cohen H.: A course in computational algebraic number theory. Springer, Berlin, 1993.

–Cohen, H., Frey, G. et al. (eds.): Handbook of Elliptic and Hyperelliptic Curve Cryptography. Chapman & Hall–CRC, Boca Raton, 2005.

–Cox, D. A., Primes of the Form x2+ny2: Fermat, Class Field Theory, and Complex Multiplication. Wiley, 1989.

–Crandall, R., Pomerance, C.: Prime Numbers — A Computational Perspective. 2nd ed. Springer, New York, 2005.

–Goldreich, O.: Foundations of Cryptography, Basic Tools. Cambridge University Press, Cambridge, 2001.

–Gôuvea, F. Q.: P–adic Numbers: An Introduction. Springer, New York, 1997.

–Hardy, G. H., Wright, E. M.: An Introduction to the Theory of Numbers. Clarendon Press, Oxford, 1945.

–Irelan, K., Rosen, M.: A classical introduction to modern number theory. Springer, Berlin, 1990.

–Koblitz, N.: Introduction to Elliptic Curves and Modular Forms. Springer, 1993.

–Koblitz, N.: P–adic Numbers, P–adic Analysis and Zeta–Functions. Springer, 1984.

–Lang, S.: Algebra. Springer, New York, 2003.

–Lang, S.: Algebraic Number Theory. Springer, New York, 1994.

–Marcus, D. A.: Number Fields. Springer, 1977.

–Menezes, A.J. et al. (eds.): Handbook of Applied Cryptography. Chapman & Hall–CRC, Boca Raton, 2006.

–Milne, J. S.: Algebraic Number Theory. Text přístupný na http://www.jmilne.org/math/.

–Milne, J. S.: Class Field Theory. Text přístupný na http://www.jmilne.org/math/.

–Milne, J. S.: Elliptic Curves. Text přístupný na http://www.jmilne.org/math/.

–Pless, V. S., Brualdi, R. A., Huffman, W. C. (eds.): Handbook of Coding Theory. North Holland, 1998.

–Serre, J.-P. A Course in Arithmetic. Graduate Texts in Mathematics 7, 1973.

–Silverman, J. H.: The Arithmetic of Elliptic Curves. Springer, 1986.

–Steuding, J.: Diophantine Analysis. Chapman & Hall, 2005.

–Stinson, D. R.: Cryptography: Theory and Practice. CRC Press, Boca Raton, 2006.

–Sudan, M.: Algorithmic Introduction to Coding Theory. Text přístupný na http://theory.lcs.mit.edu/~madhu/FT01/course.html.