Rýchle algoritmy
2017/18 -- letný semester, rozsah 2-2
Vyučujúci
doc.RNDr. Karol Nemoga, CSc., nemoga@mat.savba.sk
2.písomka: streda 25.apríla 2018 - 10:00 Písomka trvá cca 50 minút. Obsah písomky: 1. čínska zvyšková veta pre polynómy 2. Berlekampov algoritmus na faktorizáciu polynómov 3. diskrétna Fourierova transformácia nad F_q 4. Legendrov / Jakobiho symbol; riešenie kvadratických kongruencií mod pq (použitie CRT)
|
V AIS si vyberte tému zadania a prihláste sa na ňu. Každú tému si vyberú dvojice-trojice-štvorice poslucháčov (vždy je uvedené koľko), ale skupinka odovzdá iba jeden spoločný vypracovaný projekt. Hotový program posielajte mailom doc.Nemogovi. Prípadné nejasnosti v zadaní konzultujte priamo s ním na prednáške. |
Rozvrh
Deň
Miestnosť
Od
Do
Výnimky:
Prednáška
streda
ab150
10:00
11:40
Nemoga
---
Cvičenie
utorok
ab35
8:15
9:55
Čipková
---
utorok
ab35
10:00
11:40
Čipková
---
streda
c517
13:00
14:40
Nemoga
---
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
- HOFFSTEIN, J. -- PIPHER, J. --SILVERMAN, J.: An Introduction to Mathematical Cryptography, Springer
Podmienky na absolvovanie predmetu
Z celkového počtu 100 bodov môže študent získať
- 30 bodov za priebežné písomky
- 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)
Interaktívny graf hodnôt Eulerovej funkcie (pre n<53)
Knižnica NTL (Number Theory Library) - download
Stručný prehľad - úvod do knižnice NTL
Kalkulačka pre výpočet lineárnej zložitosti binárnej postupnosti