Rýchle algoritmy
2015/16 -- letný semester, rozsah 2-2
Vyučujúci
doc.RNDr. Karol Nemoga, CSc., nemoga@mat.savba.sk
RNDr. Karla Čipková, PhD. kontakt
Náhradná písomka v piatok 29.apríla 2016 od 14oo do 16oo v BC 300. Písomka trvá 120 minút.
Približné zloženie písomkových úloh:
- rozklad x^n-1 nad F_q (cyklotomické / ireducibilné polynómy, veta o dvoch rádoch)
- Čínska zvyšková veta (pre polynómy)
- riešenie homogénnych lineárnych rekurentných rovníc + minimálne polynómy postupností
- pre daný charakteristický polynóm - stanovenie počtu postupností, ktoré majú rovnaký minimálny polynóm
- diskrétna Fourierova transformácia nad F_q
Počas písomky je možné používať k nahliadnutiu vlastnoručne písané poznámky z prednášok/cvičení.
Rozvrh
Deň
Miestnosť
Krúžok
Od
Do
Prednáška
pondelok
b704
všetky
9:00
11:00
Nemoga
Cvičenie
pondelok
b701
1.
11:00
13:00
piatok
c802
2.
9:00
11:00
Čipková
piatok
c802
3.
11:00
13:00
Čipková
streda
c517
4.
9:00
11:00
Čipková
piatok
c802
5.
11:00
13:00
Čipková
Konzultácie
podľa dohody
Stručná osnova predmetu
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.
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
Podmienky na absolvovanie predmetu
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á.
Prílohy, linky
Tabuľka hodnôt Eulerovej funkcie (pre n<100)