mgr-szz:in-tei:7-tei [Státnice na FI MUNI]

Obsah

Zadání
Vypracování
Předměty
Vypracoval

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