Differences between revisions 109 and 110

Deletions are marked like this. Additions are marked like this.
Line 57: Line 57:
 || ||Deň||Miestnosť||Od||Do||
 ||'''Prednáška'''||streda||ab150||10:00||11:40||
 ||'''Cvičenie'''||utorok||ab35||8:15||9:55||
 || ||utorok||ab35||10:00||11:40||
 || ||streda||c517||13:00||14:40||
 ||'''Konzultácie'''||<-4> podľa dohody||
 || ||'''Deň'''||'''Miestnosť'''||'''Od'''||'''Do'''|| ||'''Výnimky:'''||
 ||'''Prednáška'''||streda||ab150||10:00||11:40||Nemoga||---||
 ||'''Cvičenie'''||utorok||ab35||8:15||9:55||Čipková||27.februára nebude, nahradíme neskôr počas semestra||
 || ||utorok||ab35||10:00||11:40||Čipková||27.februára nebude, nahradíme neskôr počas semestra||
 || ||streda||c517||13:00||14:40||Nemoga||---||
 ||'''Konzultácie'''||<-6> podľa dohody||

Rýchle algoritmy

2017/18 -- letný semester, rozsah 2-2

Vyučujúci

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á

    27.februára nebude, nahradíme neskôr počas semestra

    utorok

    ab35

    10:00

    11:40

    Čipková

    27.februára nebude, nahradíme neskôr počas semestra

    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

  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ť

  • 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)

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

RychleAlgoritmy (last edited 2018-02-14 08:38:50 by KarlaCipkova)