Differences between revisions 126 and 127

Deletions are marked like this. Additions are marked like this.
Line 18: Line 18:
 * Predtermín - 25.mája 2018  * Predtermín - 25.mája 2018 
Line 20: Line 20:
 * Riadny termín - 6.júna 2018 - 2.beh - AB 300, BC 300  * Riadny termín - 6.júna 2018
Line 22: Line 22:
 * Opravný termín - 27.júna 2018 - 2.beh - BC 300
 * Opravný termín - 27.júna 2018
Line 26: Line 25:
## <<Pozor>> ''''' Opravný termín: piatok 16.júna 2017 - 8:30 - ab 300 ''''' <<Pozor>> ''''' Predtermín: piatok 25.mája 2018 - 10:00 - B 704 '''''

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

  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

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

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

## diskrétna Fourierova transformácia nad F_q

## čínska zvyšková veta pre polynómy

## Berlekampov algoritmus na faktorizáciu polynómov

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

## čínska zvyšková veta

## 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
Line 35: Line 70:

## Približné zloženie písomkových úloh (na skúške):

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

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

## 3. diskrétna Fourierova transformácia nad F_q

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

##1. čínska zvyšková veta pre polynómy

##2. Berlekampov algoritmus na faktorizáciu polynómov

##3. diskrétna Fourierova transformácia nad F_q

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

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

##2. čínska zvyšková veta

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

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

## 5. faktorizácia N=pq metódou kvadratického sita
## 6. Berlekampov algoritmus na faktorizáciu polynómov


## Počas písomky je možné používať k nahliadnutiu vlastnoručne písané poznámky z prednášok/cvičení.

## <<Pohov>>

Rýchle algoritmy

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

Vyučujúci

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.

Termíny skúšok:
  • Predtermín - 25.mája 2018
  • Riadny termín - 6.júna 2018
  • Opravný termín - 27.júna 2018

Predtermín: piatok 25.mája 2018 - 10:00 - B 704

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

  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
  • + 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.

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-05-17 09:29:38 by KarlaCipkova)