[Prethodno poglavlje]   [Sljedeće poglavlje]   [Sadržaj]

4. Testovi prostosti i metode faktorizacije

4.1. Pseudoprosti brojevi

Vidjeli smo u prethodnom poglavlju da kod RSA kriptosustava, a i kod nekih drugih kriptosustava s javnim ključem, moramo na početku odabrati jedan ili više velikih prostih brojeva. Stoga se postavlja pitanje kako za veliki prirodan broj n odrediti da li je prost ili ne. To se radi pomoću testova prostosti. To su kriteriji za koje vrijedi da ako ih n ne zadovolji, onda je sigurno složen, dok ako ih zadovolji, onda može biti prost, ali i ne mora. Što više testova "prođe", to je veća vjerojatnost da je n prost.

Jedan način za provjeru da li je n prost jest da n dijelimo sa svim prostim brojevima ≤ √n. Ukoliko n nije djeljiv s niti jednim od njih, onda je n sigurno prost. Ovo je vrlo neefikasan test. Budući da prostih brojeva manjih od √n ima O(√n / log n), a za svako dijeljenje trebamo O(log2 n) operacija, to za ovaj test trebamo O(√n log n) operacija.

Efikasniji testovi se zasnivaju na nekim važnim svojstvima prostih brojeva. Prvo takvo svojstvo je mali Fermatov teorem:

Ako je n prost, onda za svaki cijeli broj b takav da je (b,n) = 1 vrijedi

bn -1 ≡ 1 (mod n).                 (*)

Važno je uočiti da obrat ovog teorema ne vrijedi. Naime, n može biti složen, a da ipak za neki b vrijedi relacija (*).

Primjer 4.1: Broj 91 je očito složen jer je 91 = 7 . 13. Međutim,

390 ≡ 2730 ≡ (-1)30 ≡ 1 (mod 7)   i   390 ≡ 2730 ≡ 130 ≡ 1 (mod 13),

pa je 390 ≡ 1 (mod 91). No, 290 ≡ 64 (mod 91), pa i odavde možemo zaključiti da je 91 složen.


Definicija: Ako je n neparan složen broj, te b cijeli broj takav da je (b,n) = 1 i bn -1 ≡ 1 (mod n), onda kažemo da je n pseudoprost u bazi b (ili da je n psp(b)).

Na primjer, broj 91 je pseudoprost u bazi 3.

Teorem 4.1: Neka je n neparan složen broj. Tada vrijedi:

(1)   n je pseudoprost u bazi b, gdje je (b,n) = 1, ako i samo ako red od b modulo n (tj. najmanji prirodan broj a takav da je ba ≡ 1 (mod n)) dijeli n - 1.

(2)   Ako je n pseudoprost u bazama b1 i b2, onda je n pseudoprost i u bazama b1 . b2 i b1 . b2-1.

(3)   Ako n ne zadovoljava (*) za neki b, onda n ne zadovoljava (*) za barem pola mogućih baza b (brojeva između 1 i n koji su relativno prosti s n).

Dokaz: (1)   Neka je a red od b. Pretpostavimo da a ne dijeli n - 1, tj. n - 1 = a . q + r, 0 < r < a. Tada je

br = bn -1-aqbn -1 (ba)-q ≡ 1 (mod n),

što je u suprotnosti s minimalnošću od a.

Obrnuto, neka je n - 1 = a · k. Tada je bn -1 ≡ (ba)k ≡ 1 (mod n).

(2)   Iz b1n -1b2n -1 ≡ 1 (mod n), slijedi (b1b2)n -1b1n -1 b2n -1 ≡ 1 (mod n) i (b1b2-1)n -1b1n -1 (b2n -1)-1 ≡ 1 (mod n).

(3)   Neka je { b1, b2, ... , bs } skup svih baza za koje vrijedi (*), te neka je b fiksna baza za koju ne vrijedi (*). Tada baze bb1, bb2, ... , bbs ne zadovoljavaju (*), jer ako bi bbi zadovoljavala (*), onda bi po (2) to vrijedilo i za b = (bbi)bi-1. Prema tome, postoji barem s baza za koje ne vrijedi (*), što je i trebalo dokazati.


Teorem 4.1 se može iskoristiti kao osnova za vjerojatnosni test prostosti. Naime, ako pretpostavimo da postoji baza b za koju ne vrijedi (*), te ako uzmemo k slučajno odabranih baza i n zadovolji test (*) za sve njih, onda je po Teoremu 5.1(3) vjerojatnost da je n složen ≤ 1/2k. Nažalost, nedostatak ovog testa jest u tome što postoje složeni brojevi koji su pseudoprosti za sve baze b.

Definicija: Složen broj n za kojeg (*) vrijedi za svaki cijeli broj b takav da je (b,n) = 1 zove se Carmichaelov broj.

Poznato je da postoji beskonačno mnogo Carmichaelovih brojeva. Najmanji među njima je 561 = 3 · 11 · 17. Nije teško pokazati da Carmichaelov broj mora biti kvadratno slobodan (nije djeljiv s kvadratom niti jednog prirodnog broja većeg od 1) i imati barem 3 prosta faktora. Nadalje, kvadratno slobodni broj n je Carmichaelov ako i samo ako p - 1 dijeli n - 1 za svaki prosti faktor p od n.


[Prethodno poglavlje]   [Sljedeće poglavlje]   [Sadržaj]
Web stranica kolegija Kriptografija Andrej Dujella - osobna stranica