===== Zadání ===== 7. Základní algoritmy teorie čísel a jejich aplikace ===== Vypracování ===== Ako sa túto otázku učiť? 1) Prejst [Gruska] pre prehľad a iný pohľad. 2) Odtiaľto a nejasné veci si dohľadávať, najlepšie v [Kucera]. 3) Zamyslieť sa v súvislosti s http://statnice.dqd.cz/mgr-szz:in-tei:3-tei ==== Poznámka k zložitosti ==== Vstup algoritmov teórie čísel býva prirodzené číslo N. Lenže to je pri vstupe dlhé log_2 N (bitov). Teda napríklad zložitosť O(N) je exponenciálna. ==== Problémy ==== „1. Je-li dáno prirozené císlo N, rychle rozhodnout, zda N splnuje nejakou podmínku, která je splnena kazdým prvocíslem, a tedy rozhodnout, zda je to urcite císlo slozené anebo zda je to asi prvocíslo (tzv. test na slozenost). 2. Víme-li, ze N je asi prvocíslo, dokázat, ze N skutecne prvocíslem je, nebo to vyvrátit (tzv. test na prvocíselnost). 3. Víme-li, ze je N slozené, nalézt netriviálního dìlitele d císla N.“ [Kucera] Alebo ekvivalentne inak: Vstup: prirodzené číslo n. Test na zloženosť: Výstup 1: n je zložené číslo. Výstup 2: n je buď zložené číslo alebo prvočíslo. Test na prvočíselnosť: Výstup 1: n je zložené číslo. Výstup 2: n je prvočíslo. Prečo nie hned test na prvočíselnosť? Typicky majú horšiu časovú zložitosť ako testy na zloženosť. Pre mnohé zložené čísla sa ušetrí čas tým, že nebudú musieť ísť do testov na prvočíselnosť. ==== Hlavné pojmy ==== (Konečné) teleso Z/mZ Najväčší spoločný deliteľ prirodzených čísel a, b: gcd(a,b) Kongruencia celých čísel a, b podľa modulu m. Eulerova funkcie: \phi: N -> N priraďujúca číslu n počet prirodzených čísel menších ako n, ktoré sú s nim nesúdeliteľné (gcd(a,n)=1). ==== Hlavné vety ==== Bezout: a, b sú prirodzené čísla, d=gcd(a,b). Potom existujú celé čísla x,y tak, že ax+by=d. Čínska zbytková veta: m, n sú prirodzené čísla, gcd(m,n)=1. Potom pre hociaké celé čísla x, y existuje celé číslo z spĺňajúce z = x (mod m), z = y (mod n). Dôkaz je konštruktívny, ktorý dané z "rýchlo" nájde. VYUŽITIE VETY: napr. pre zrýchlenie šifrovania v RSA. Eulerova veta: m je prirodzené číslo, a je celé číslo, gcd(a,m)=1. Potom a^{(\phi(m))} je kongruentné 1 modulo m. Fermatova veta: Nech p je prvočíslo, a je celé číslo nedeliteľné p. Potom platí: a^{(p-1)} je kongruentné 1 modulo p. Veta: Nech p je prvočíslo, n je prirodzené číslo: Potom existuje teleso o p^n prvkoch. Veta: Ľubovoľné dve konečné telesá o rovnakom počte prvkov sú izomorfné. ==== Hlavné (veľmi) jednoduché algoritmy ==== === EUCLID === - Vstup: 2 prirodzené čísla a, b - Výstup: gcd(a,b). - Algoritmus 1) b=0? Ano? Super, return a. Nie? Chod na 2) 2) r = a mod b, a=b, b=r, chod na 1) - Zlozitost: N=max{a,b} Pocet deleni: O(ln N) 1 delenie: O(ln^2 N) Vysledok: kubicka zlozitost Pri dobrom naprogramovani: kvadraticka === ROZSIRENY EUCLID === Vstup: a,b. Vystup: u,v,d, kde d=gcd(a,b), ua+vb=d. 1. [Inicializace] Poloz u= 1, d=a. Je-li b = 0, poloz v=0, vytiskni (u; v; d) jako odpoved a skonci. Inak poloz v1=0, v3=b 2. [Jsi hotov?] Je-li v3 = 0, pak poloz v=(d-au)/b, vytiskni (u; v; d) jako odpoved a skonci. 3. [Euklidovský krok] Soucasne spocitaj q = d div v3, t3 = d mod v3. Potom poloz t1 =u - qv1, u = v1, d = v3, v1 = t1, v3 = t3 a jdi na 2. Korektnost: celkom dlhy dokaz Zlozitost: asi dvojnasobok Euclida. === RYCHLE UMOCNOVANIE === Chcem vypočítať a^n. Netreba n násobení, stačí log(n) násobení. ALGORITMY: Binárne umocňovanie (zľava doprava alebo sprava doľava) [Kucera], strana 11. === POCITANIE INVERZIE === Problem: Sme v Z_n a chcem spočítať inverziu prvku g. Riesenie: Aby inverzia vôbec existovala, nutne gcd(g,n)=1. g^{-1} spočítame z Rozšíreného Euclida nasledovne: Spočítame koeficienty a,b tak, že an+bg=1. To platí v celých číslach, ale my sme v Z_n. Takže an vypadne a ostáva, že bg je kongruentné 1 modulo n, čo je presne to, čo chceme. b=g^{-1} ==== Využitie v problémoch ==== Overview: Preleťte si - http://en.wikipedia.org/wiki/Primality_test - http://en.wikipedia.org/wiki/Prime_factorization === Testy na zloženosť čísla === 1) - Na základe Fermatovej vety - Rýchle, lebo vieme rýchlo umocňovať (Binárne umocňovanie) - Problém: neobjaví Carmichaelove čísla 2) Algoritmus Miller-Rabin - odstráni problém s Carmichaelovými číslami pri rovnakej asymptotickej zložitosti ako 1) - pozri: http://en.wikipedia.org/wiki/Miller–Rabin_primality_test === Testy na prvočíselnosť === pozri: http://en.wikipedia.org/wiki/Primality_test#Fast_deterministic_tests === Faktorizácia === pozri: http://en.wikipedia.org/wiki/Prime_factorization#Factoring_algorithms === Ďalšie === - Testy na zloženosť čísla pri generovaní prvočísel v RSA. Rýchlo sa zbaviť vygenerovaných zložených čísel. - Ďalšie aplikácie v kryptografii. TODO. ===== Předměty ===== * [[https://is.muni.cz/auth/predmet/sci/M8190|M8190 Algoritmy teorie čísel (PřF)]] * [Kucera] http://www.math.muni.cz/~kucera/texty/ATC10.pdf * [Gruska] http://www.fi.muni.cz/usr/gruska/crypto12/appendix.ps ===== Vypracoval ===== Michal Abaffy Moja spokojnosť s vypracovaním: 70%. Nie som si istý, čo mi chýba. Asi viac aplikácii v kryptografii.