Revision 97 as of 2017-05-03 09:33:43

Clear message

Rýchle algoritmy

2016/17 -- letný semester, rozsah 2-2

Vyučujúci

V stredu 3.mája 2017: na prednáške 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ú dvojice-trojice-štvorice, skupinka odovzdá jeden spoločný vypracovaný projekt (konkurenčná dvojica-trojica-štvorica s rovnakou témou je nezávislá od druhej skupiny); už pri prihlasovaní si správne zvoľte "kolegu", nech je zrejmé, aké skupiny ste vytvorili (prihlasujte sa radšej bezprostredne po sebe).

Zadanie (vykonávateľný modul s interfejsom na overenie správnosti výpočtu) odovzdávajte mailom doc.Nemogovi. Za dvojicu/trojicu/štvoricu stačí odovzdať jeden spoločný program.

Termíny skúšok:
  • Riadny termín: streda 24.mája 2017 - 2.beh - bc 300, cd 300

  • Opravný termín: piatok 16.júna 2017 - 1.beh - ab 300

Rozvrh

Deň

Miestnosť

Od

Do

Prednáška

streda

ab150

10oo

12oo

Cvičenie

pondelok

bc35

9oo

11oo

streda

c517

13oo

15oo

piatok

c802

9oo

11oo

piatok

c802

11oo

13oo

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.
  3. WILF, H.S.: Algorithms and Complexity.
  4. COHEN, H. -- FREY, G. et al.: Handbook of Elliptic and Hyperelliptic Curve Cryptography, Chapman & Hall/CRC

  5. LeVEQUE, W.: Fundamentals of Number Theory
  6. 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ť

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)

Möbiova funkcia

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