Revision 59 as of 2016-06-07 08:40:27

Clear message

Rýchle algoritmy

2015/16 -- letný semester, rozsah 2-2

Vyučujúci

Zadanie (vykonávateľný modul s interfejsom na overenie správnosti výpočtu) odovzdávajte osobne doc.Nemogovi. Miesto a čas si musíte dohodnúť individuálne. Za dvojicu stačí odovzdať jeden spoločný program.

Písomky sú už opravené, body nájdete zapísané v AIS. Možnosť nahliadnuť do opravených skúškových písomiek: v pondelok 13.júna 2016 o 11oo.

Termíny skúšok:

Riadny termín: štvrtok 2.júna 2016

Opravný termín: pondelok 27.júna 2016 - 2.beh - CD 300

Približné zloženie písomkových úloh (na skúške):
  1. Berlekampov algoritmus na faktorizáciu polynómov
  2. Legendrov / Jakobiho symbol; riešenie kvadratických kongruencií mod pq (použitie CRT)
  3. faktorizácia N=pq metódou kvadratického sita
  4. hľadanie ortogonálnej bázy pomocou Gram-Schmidtovej ortogonalizácie
  5. ruksakový kryptosystém; El-Gamalov kryptosystém
  6. eliptické krivky (hľadanie generátora, konštrukcia "logaritmických" tabuliek)

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 Theoretic Library)