Rýchle algoritmy

2015/16 -- letný semester, rozsah 2-2

Vyučujúci

V pondelok 18.apríla 2016:

bude reč o zadaniach zadaní o 8:30 v B 704 (pred prednáškou); tam sa môžete u doc.Nemogu podrobne informovať o tom, čo presne máte implementovať, konzultovať prípadné nejasnosti, opýtať sa termín, miesto a spôsob odovzdania
na témy sa môžete prihásiť v AIS, každú tému si vyberú dve dvojice (až na nejaké výnimky pri sférickej zložitosti postupností), dvojica odovzdá jeden spoločný vypracovaný projekt (konkurenčná dvojica s rovnakou témou je nezávislá od druhej dvojice)
o 9:00 bude pokračovať prednáška ako obvykle
po jej skončení o 10:40 budete môcť nahliadnuť do opravených písomiek a reklamovať (nahliadnutie a reklamácie sú možné iba v tomto jedinom termíne)
pondelkové cvičenie, ktoré podľa rozvrhu začína o 11:00 bude, no začne pravdepodobne s oneskorením (ktoré bude upresnené na prednáške)

1. Úvodné pojmy. Euklidov algoritmus. Overovanie prvočíselnosti. Konštrukcia prvočísel.

2. Základy algebry, grupy, okruhy, polia, polynómy, rozšírenia, cyklotomické polynómy.

3. Konečné polia, štruktúra a reprezentácia, norma, stopa.

4. Konštrukcia ireducibilných a primitívnych polynómov, faktorizácia, Berlekampov algoritmus.

5. Lineárne rekurentné rovnice, reprezentácia riešení, LFSR, Berlekampov Masseyov algoritmus.

6. Riešenie rovníc nad konečnými poľami, efektívne výpočty, CRT.

7. Efektívne metódy aritmetiky, (Montgomery, Karacuba, Cook, ...).

8. Diskrétna Fourierova transformácia a jej aplikácie, konvolúcie, Winogradov algoritmus.

9. Eliptické krivky, výpočty.

10. NTL, softvérové balíky pre výpočty.

11. Mrežové body, LLL algoritmus, aplikácie v kryptológii.

12. Riešenie veľkých sústav rovníc, Laczosova a Wiedemanova metóda.

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

Z celkového počtu 100 bodov môže študent získať

30 bodov za priebežnú písomku
30 bodov za zadanie (v priebehu semestra študenti vypracujú zadanie zamerané na výpočty v konečných poliach, zadaný výpočet implementujú do podoby vykonávateľných modulov s interfejsom na overenie správnosti výpočtu)
40 bodov za záverečnú skúškovú písomku

Pre udelenie zápočtu je potrebné získať z písomky a zadania aspoň 30 bodov. Účasť na prednáškach a cvičeniach je nutná.