4. Testovi prostosti i metode faktorizacije

4.1. Pseudoprosti brojevi

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(log² 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,

3⁹⁰ ≡ 27³⁰ ≡ (-1)³⁰ ≡ 1 (mod 7)   i   3⁹⁰ ≡ 27³⁰ ≡ 1³⁰ ≡ 1 (mod 13),

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

b^r = b^{n -1-aq} ≡ b^{n -1} (b^a)^-q ≡ 1 (mod n),

Obrnuto, neka je n - 1 = a · k. Tada je b^{n -1} ≡ (b^a)^k ≡ 1 (mod n).

(2)   Iz b₁^{n -1} ≡ b₂^{n -1} ≡ 1 (mod n), slijedi (b₁b₂)^{n -1} ≡ b₁^{n -1} b₂^{n -1} ≡ 1 (mod n) i (b₁b₂^-1)^{n -1} ≡ b₁^{n -1} (b₂^{n -1})^-1 ≡ 1 (mod n).

(3)   Neka je { b₁, b₂, ... , b_s } skup svih baza za koje vrijedi (*), te neka je b fiksna baza za koju ne vrijedi (*). Tada baze bb₁, bb₂, ... , bb_s ne zadovoljavaju (*), jer ako bi bb_i zadovoljavala (*), onda bi po (2) to vrijedilo i za b = (bb_i)b_i^-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/2^k. 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.