7. Základní algoritmy teorie čísel a jejich aplikace

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

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.

„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ť.

(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).

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

- 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

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.

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.

Problem: Sme v a chcem spočítať inverziu prvku .
Riesenie: Aby inverzia vôbec existovala, nutne .
spočítame z Rozšíreného Euclida nasledovne:
Spočítame koeficienty tak, že . To platí v celých číslach, ale my sme v . Takže an vypadne a ostáva, že je kongruentné 1 modulo , čo je presne to, čo chceme.

Overview: Preleťte si
- http://en.wikipedia.org/wiki/Primality_test - http://en.wikipedia.org/wiki/Prime_factorization

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

pozri: http://en.wikipedia.org/wiki/Primality_test#Fast_deterministic_tests

pozri: http://en.wikipedia.org/wiki/Prime_factorization#Factoring_algorithms

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

• 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

Michal Abaffy
Moja spokojnosť s vypracovaním: 70%. Nie som si istý, čo mi chýba. Asi viac aplikácii v kryptografii.