Rýchle algoritmy

2018/19 -- letný semester, rozsah 2-2

Vyučujúci

• doc.RNDr. Karol Nemoga, CSc., nemoga@mat.savba.sk

• RNDr. Karla Čipková, PhD. kontakt

V stredu 3.apríla 2019 bude prednáška s V.Hromadom (od 10oo v AB 150 ako obvykle), kde Vám predstaví knižnicu NTL, pretože v priebehu semestra budete mať pomocou nej vypracovať zadanie zamerané na výpočty v konečných poliach. Odporúčam účasť, na inom mieste o NTL už reč nebude.

Písomka v stredu 3.apríla 2019 o 13:00 v miestnosti AB 150. Približné/možné zloženie písomkových úloh na písomke (treba brať len orientačne - je to podľa minulého roku, v utorok 2.apríla upresním): 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) diskrétna Fourierova transformácia nad F_q 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

Rozvrh

• 	Deň	Miestnosť	Od	Do		Výnimky:
  Prednáška	streda	ab150	10:00	11:40	Nemoga	3.4. s V.Hromadom
  Cvičenie	streda	c801	13:00	14:40	Čipková	3.4. písomka v AB 150
  	streda	c517	13:00	14:40	Nemoga	3.4. písomka v AB 150
  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í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