Differences between revisions 129 and 130

Deletions are marked like this. Additions are marked like this.
Line 10: Line 10:
<<Pozor>>
'''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. Prípadné nejasnosti v zadaní konzultujte priamo s ním.
## <<Pozor>>
## '''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. Prípadné nejasnosti v zadaní konzultujte priamo s ním.
Line 13: Line 14:
<<Pohov>> ## <<Pohov>>
Line 15: Line 16:
<<Pozor>>
'''Pozrieť opravenú písomku z riadneho termínu''' si môžete v pondelok 18.júna 2018 o 10:30 v bloku A v respíriu na 4.poschodí.
<<Pohov>>
## <<Pozor>>
## '''Pozrieť opravenú písomku z riadneho termínu''' si môžete v pondelok 18.júna 2018 o 10:30 v bloku A v respíriu na 4.poschodí.
## <<Pohov>>
Line 20: Line 21:
<<Pozor>>
'''Termíny skúšok:'''
## <<Pozor>>
## '''Termíny skúšok:'''
Line 23: Line 24:
 * Predtermín - 25.mája 2018 ## * Predtermín - 25.mája 2018
Line 25: Line 26:
 * Riadny termín - 6.júna 2018 ## * Riadny termín - 6.júna 2018
Line 27: Line 28:
 * Opravný termín - 27.júna 2018
<<Pohov>>
## * Opravný termín - 27.júna 2018
## <<Pohov>>
Line 30: Line 31:
<<Pozor>> ''''' Riadny termín: streda 6.júna 2018 - 11:00 - BC 300 ''''' ## <<Pozor>> ''''' Riadny termín: streda 6.júna 2018 - 11:00 - BC 300 '''''
Line 35: Line 36:
Približné/možné zloženie písomkových úloh na skúške (treba brať len orientačne): ## Približné/možné zloženie písomkových úloh na skúške (treba brať len orientačne):
Line 37: Line 38:
  1. eliptické krivky (hľadanie generátora, konštrukcia "logaritmických" tabuliek) ## 1. eliptické krivky (hľadanie generátora, konštrukcia "logaritmických" tabuliek)
Line 39: Line 40:
  2. hľadanie ortogonálnej bázy pomocou Gram-Schmidtovej ortogonalizácie ## 2. hľadanie ortogonálnej bázy pomocou Gram-Schmidtovej ortogonalizácie
Line 41: Line 42:
  3. ruksakový kryptosystém; (El-Gamalov kryptosystém) ## 3. ruksakový kryptosystém; (El-Gamalov kryptosystém)
Line 43: Line 44:
  4. faktorizácia N=pq metódou kvadratického sita ## 4. faktorizácia N=pq metódou kvadratického sita
Line 45: Line 46:
 + nejaké teoretické otázky z učiva celého semestra (treba brať vážne) ## + nejaké teoretické otázky z učiva celého semestra (treba brať vážne)
Line 47: Line 48:
Počas písomky môže mať každý vlastné, vlastnoručne písané ťaháky ľubovoľného rozsahu. '''
Nie zápisky z cvičení a prednášok.'''
<<Pohov>>
## Počas písomky môže mať každý vlastné, vlastnoručne písané ťaháky ľubovoľného rozsahu. '''
## Nie zápisky z cvičení a prednášok.'''
## <<Pohov>>

Rýchle algoritmy

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

Vyučujúci

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

Möbiova funkcia

Výpočet Jacobiho symbolu

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-07-02 11:25:59 by KarlaCipkova)