Fermaov test za proste brojeve

Iz Vikipedije, slobodne enciklopedije
Idi na navigaciju Idi na pretragu

Fermaov test je nasumični test kojim se utvrđuje da li je broj potencijalno prost.

Ideja[uredi]

Mala Fermaova teorema tvrdi da, ako je p prost broj, i , onda važi

Ukoliko želimo da utvrdimo da li je p prost broj, možemo birati proizvoljne brojeve a u zadatom intervalu i proveravati da li važi jednakost. Ukoliko nađemo broj a za koji jednakost nije ispunjena, dokazali smo da je broj p složen. Sa druge strane, ukoliko je jednakost ispunjena za puno različitih brojeva a, možemo reći da je p verovatno prost broj, ili pseudoprost broj.

Može se desiti da u testiranju ne izaberemo vrednost broja a za koju jedakost ne bi bila tačna. Svaki broj a za koji važi

kada je n složen, se naziva Fermaov lažov. Ukoliko izaberemo a tako da je

onda se a naziva Fermaov svedok za složenost broja n.

Algoritam i vreme izvršavanja[uredi]

Algoritam testa može biti formulisan na sledeći način:

Ulaz
n: broj za koji se testira da li je prost
k: parametar koji zadaje koliko puta treba testirati da li je broj prost
Izlaz
složen ako je n složen, inače verovatno prost
ponovi k puta:
izaberi proizvoljan a iz intervala (1, n − 1]
ako je an − 1 mod n ≠ 1 vrati složen
vrati verovatno prost

Korišćenjem brzih algoritama za modularno stepenovanje dobija se da je vreme izvršavanja ovog algoritma

O(k × log2n × log log n × log log log n),

gde k broji koliko puta smo testirali proizvoljno a, dok je n broj za koji ispitujemo da li je prost.

Mane[uredi]

Postoje izvesne vrednosti broja n, poznate kao Karmajklovi brojevi, za koje su svi brojevi a, koji su uzajamno prosti sa n, Fermaovi lažovi. Iako su takvi brojevi retki, ima ih dovoljno da se umesto Fermaovog testa za proveru da li je dati broj prost često upotrebljavaju drugi testovi, kao što su Miler-Rabin i Solovej-Štrasen.

U opštem slučaju, ako n nije Karmajklov broj, onda bar pola svih brojeva

ima osobinu da su Fermaovi svedoci. Da bi se ovo pokazalo, dovoljno je pretpostaviti da je a Fermaov svedok, a da su a1, a2, ..., as Fermaovi lažovi. Onda važi

što znači da su svi a × ai za i = 1, 2, ..., s Fermaovi svedoci.

Upotreba[uredi]

Program za enkripciju PGP koristi ovaj test u svojim algoritmima. Verovatnoća da će PGP izgenerisati Karmajklov broj je manja od 1 : 1050, što je više nego dovoljno za praktičnu upotrebu.

Literatura[uredi]

  • Tomas Kormen (Thomas H. Cormen), Čarls Lejserson (Charles E. Leiserson), Ronald Rivest (Ronald L. Rivest) i Kliford Stin (Clifford Stein). Uvod u algoritme (Introduction to Algorithms), drugo izdanje, MIT Press and McGraw-Hill, 2001. ISBN 978-0-262-03293-3. str. 889-890.

Vidi još[uredi]