Fermaov test za proste brojeve

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

Ideja

Mala Fermaova teorema tvrdi da, ako je p prost broj, i $1\leq a<p$, onda važi

$a^{p-1}\equiv 1{\pmod {p}}$

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

$a^{n-1}\equiv 1{\pmod {n}}$

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

$a^{n-1}\not \equiv 1{\pmod {n}}$

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

Algoritam i vreme izvršavanja

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 a^{n − 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 × log²n × 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

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

$a\in (\mathbb {Z} /n\mathbb {Z} )^{*}$

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

$(a\cdot a_{i})^{n-1}\equiv a^{n-1}\cdot a_{i}^{n-1}\equiv a^{n-1}\not \equiv 1{\pmod {n}}$

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

Upotreba

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

Literatura

• 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š

• Mala Fermaova teorema