Rýchle algoritmy
2015/16 -- letný semester, rozsah 2-2
Vyučujúci
doc.RNDr. Karol Nemoga, CSc., nemoga@mat.savba.sk
V 4.týždni semestra nebude cvičenie. Individuálne sa pohrajte s knižnicou NTL (download nižšie). |
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
1. LIDL, R. -- NIEDERREITER, H. Finite Fields. Cambridge: Cambridge University Press, 2nd Ed., 1997. 768 s. ISBN 0-521-39231-4.
2. POMERANCE, C. -- CRANDALL, R. Prime Numbers. New York: Springer, 2001. 546 s. ISBN 0-387-94777-9.
Prílohy, linky
Tabuľka hodnôt Eulerovej funkcie (pre n<100)