= Rýchle algoritmy =

2023/24 -- letný semester, rozsah 2-2

== Vyučujúci ==

 * doc.RNDr. Karol Nemoga, CSc., nemoga@mat.savba.sk
 * [[KarlaCipkova| RNDr. Karla Čipková, PhD.]] {i} [[Pracovnici| kontakt]]

## <<Pozor>> '''Zadanie''', ak ho ešte nemáte vybraté a prihlásené, si môžete rezervovať mailom na karla.cipkova@stuba.sk. Zadanie je Vaše až po tom, keď Vám na mail odpoviem.
## [[attachment:Zadania RA 2019.docx| Zadania]]

## <<Pohov>>

## <<Pozor>>  
## '''Náhradná písomka''' v utorok 7.mája 2019 o 13:00 '''v miestnosti C 801'''.


## Približné zloženie písomkových úloh na písomke:

##  * konečné polia F_q (konštrukcia, ireducibilné polynómy)

##  * čínska zvyšková veta (v Z aj pre pre polynómy)

##  * rozklad x^n-1 nad F_q (cyklotomické / ireducibilné polynómy, veta o dvoch rádoch)

##  * riešenie homogénnych lineárnych rekurentných rovníc + minimálne polynómy postupností

##  * pre daný charakteristický polynóm - stanovenie počtu postupností, ktoré majú rovnaký minimálny polynóm


##Písomka trvá cca 50 minút.

## Rozdelenie do miestností:

## * '''bc 300''' - poslucháči s priezviskom A - L

## * '''cd 300''' - poslucháči s priezviskom M - Ž

## <<Pohov>>

## <<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.

## <<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>>


## <<Pozor>> 
## '''Termíny skúšok:'''

##  * Predtermín - 25.mája 2018 

## * Riadny termín - 20.mája 2019 - BC 300 - od 14oo - 3.beh 

## * Opravný termín - '''14.júna 2019 - AB 150 - od 14oo''' - 3.beh 
## <<Pohov>> 

## <<Pozor>> ''''' Riadny termín: streda 6.júna 2018 - 11:00 - BC 300 '''''

## RT - 2.beh - AB 300, BC 300
## OT - 2.beh - BC 300

## Približné/možné zloženie písomkových úloh na skúške (treba brať len orientačne):

## Legendrov / Jakobiho symbol; riešenie kvadratických kongruencií mod pq (použitie CRT)

## Berlekampov algoritmus na faktorizáciu polynómov

##   1. eliptické krivky (hľadanie generátora, konštrukcia "logaritmických" tabuliek)

##   2. hľadanie ortogonálnej bázy pomocou Gram-Schmidtovej ortogonalizácie
  
##   3. ruksakový kryptosystém; (El-Gamalov kryptosystém)

##   4. faktorizácia N=pq metódou kvadratického sita

## * diskrétna Fourierova transformácia nad F_q

##  + nejaké teoretické otázky z učiva celého semestra (treba brať vážne)

## 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>> 

## Ak máte pocit, že sa Vám skúška v riadnom termíne nepodarila, môžete si prísť na opravný termín vylepšiť bodové skóre.

## == Rozvrh ==

##  || ||'''Deň'''||'''Miestnosť'''||'''Od'''||'''Do'''|| ||'''Výnimky:'''||
##  ||'''Prednáška'''||streda||ab150||10:00||11:40||Nemoga||učí sa v utorok 7.mája||
##  ||'''Cvičenie'''||streda||c801||13:00||14:40||Čipková||v utorok 7.mája - písomka||
##  || ||streda||c517||13:00||14:40||Nemoga||v utorok 7.mája - písomka v c801||
##  ||'''Konzultácie'''||<-6> 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
   * 10 bodov za prezenčky (bude ich 10, každá za 1 bod)
   * 20 bodov za zadanie (podrobnosti sa dozviete počas semestra)

Na skúšku môže ísť každý, kto počas semestra získa aspoň 30 bodov.

============================

Skúška bude za 40 bodov. Pre úspešné zvládnutie predmetu je potrebné získať na skúške aspoň 15 bodov.

============================

Účasť na prednáškach a cvičeniach je nutná. 

== Prílohy, linky ==

[[attachment:Phi(n).pdf| Tabuľka hodnôt Eulerovej funkcie (pre n<100)]]

[[https://www.khanacademy.org/computing/computer-science/cryptography/modern-crypt/p/euler-totient-exploration| Interaktívny graf hodnôt Eulerovej funkcie (pre n<53)]]

[[https://en.wikipedia.org/wiki/M%C3%B6bius_function| Möbiova funkcia]]

[[http://math.fau.edu/richman/jacobi.htm| Výpočet Jacobiho symbolu]]

[[http://www.shoup.net/ntl/download.html| Knižnica NTL (Number Theory Library) - download]]

[[attachment:NTL.pdf| Stručný prehľad - úvod do knižnice NTL]]

[[http://bma.bozhu.me/| Kalkulačka pre výpočet lineárnej zložitosti binárnej postupnosti]]