Organizácia predmetu
Predmet je členený do nasledujúcich aktivít:
- Prednášky: 2 hodiny týždenne
- Cvičenie: 2 hodiny týždenne
- Samostatné domáce štúdium
Rozvrh
- prednáška – streda – CD 150 – 08:00 – 10:00
- cvičenie – streda – CD 150 – 10:00 – 12:00
- cvičenie – streda – BC 35 – 10:00 – 12:00
- konzultácie – po dohode (osobne alebo mailom)
Cieľ predmetu
Získať základné znalosti z algebraickej teórie štruktúr, hlavne z teórie konečných polí a postupností nad konečnými poľami. Ďalej znalosti z efektívnych a rýchlych výpočtov nad konečnými poľami. Študent získa znalosti o matematickom aparáte a programovacích technikách, ktoré sa využívajú v najrozmanitejších krypto API. Po absolvovaní predmetu pochopí princípy konštrukcie algoritmov tvoriacich jadro najrozmanitejších aplikácii na prenos a uchovávanie utajovaných skutočností.
Plán semestra
- Úvodné pojmy. Euklidov algoritmus. Overovanie prvočíselnosti. Konštrukcia prvočísel.
- Základy algebry, grupy, okruhy, polia, polynómy, rozšírenia, cyklotomické polynómy.
- Konečné polia, štruktúra a reprezentácia, norma, stopa.
- Konštrukcia ireducibilných a primitívnych polynómov, faktorizácia, Berlekampov algoritmus.
- Lineárne rekurentné rovnice, reprezentácia riešení, LFSR, Berlekampov Masseyov algoritmus.
- Riešenie rovníc nad konečnými poľami, efektívne výpočty, CRT.
- Efektívne metódy aritmetiky, (Montgomery, Karacuba, Cook, …)
- Diskrétna Fourierova transformácia a jej aplikácie, konvolúcie, Winogradov algoritmus.
- Eliptické krivky, výpočty.
- NTL, softvérové balíky pre výpočty.
- Mrežové body, LLL algoritmus, aplikácie v kryptológii.
- Riešenie veľkých sústav rovníc, Laczosova a Wiedemanova metóda.
Podmienky absolvovania
Z celkového počtu 100 bodov môže študent získať:
- 2 x 15 bodov za dve priebežné písomky
- 10 bodov za prezenčky (bude ich 10, každá za 1 bod)
- 20 bodov za zadanie (podrobnosti sa dozviete počas semestra)
Na skúšku môže ísť každý, kto počas semestra získa aspoň 30 bodov.
- Skúška bude za 40 bodov. Pre úspešné zvládnutie predmetu je potrebné získať na skúške aspoň 15 bodov.
Účasť na prednáškach a cvičeniach je nutná.
Všetky informácie budú počas celého semestra priebežne uverejňované v MOODLE. Prihláste sa do predmetu RAL podľa inštrukcií, ktoré dostanete mailom.
Literatúra
- LIDL, R. — NIEDERREITER, H.: Finite Fields. Cambridge: Cambridge University Press, 2nd Ed., 1997. 768 s. ISBN 0-521-39231-4.
- POMERANCE, C. — CRANDALL, R.: Prime Numbers. New York: Springer, 2001. 546 s. ISBN 0-387-94777-9.
WILF, H.S.: Algorithms and Complexity.
- COHEN, H. — FREY, G. et al.: Handbook of Elliptic and Hyperelliptic Curve Cryptography, Chapman & Hall/CRC
- LeVEQUE, W.: Fundamentals of Number Theory
- HOFFSTEIN, J. — PIPHER, J. –SILVERMAN, J.: An Introduction to Mathematical Cryptography, Springer
