Fermatov test temelji se na rezultatima iz teorije brojeva poznatih kao Fermatov mali teorem.
Prema Fermatovom malom teoremu, ako je n prost broj i d je bilo koji pozitivan cijeli broj manji od n , tada je d podignut u n- tu stepen podudaran s d modula n .
Ako dva broja imaju isti ostatak kad se podijele s n, tada se kaže da su podudarni po modulu n . d modul n je jednostavno ostatak broja d kada se podijeli s n .
Na primjer, 34 je podudarno sa 16 (modul 3) kao
34 modula 3 = 1 i 16 modula 3 = 1.
Fermatov test za primarnost
- Za zadani broj n odaberite slučajni pozitivan broj d takav da je d < ; n.
- Izračunaj (d ^ n) modulo n .
- d modulo n će uvijek biti d jer uvijek odabiremo d koji zadovoljava uvjet d < ; n.
- Ako rezultat (d ^ n) modula n nije jednak d , tada d sigurno nije prost.
- Ako je rezultat (d ^ n) modula n jednak d , tada su velike šanse da je n prost.
- Odaberite drugi slučajni d koji zadovoljava uvjet d < n i ponovite gornje korake.
Napomena : Primjeri u ovom postu koriste Swift 4.1
Trebamo funkciju za izračunavanje eksponencija broja modulo drugog broja.
Koristimo modularno potenciranje za izračunavanje vrijednosti kada je eksponent veći od 1, jer nam to omogućuje izvođenje izračuna, a bavimo se samo brojevima manjim od n ( modul u gornjoj funkciji).
Fermatov test slučajnim odabirom uključuje broj d između 1 i n-1 ( broj - 1 u gornjoj funkciji). Cilj je provjeriti je li ostatak modula n-te snage d jednak d.
Fermat test se izvodi za navedeni broj. Ako broj padne na Fermatovom testu, uvjeravamo se da nije prost. Ako broj prođe Fermatov test, nije zajamčeno da je prost. Pokušavamo smanjiti vjerojatnost pogreške u našem testu primarnosti izvođenjem testa dovoljno puta.
Pokušavajući sve više i više vrijednosti d (slučajni pozitivan broj između 1 i n-1), možemo povećati svoje povjerenje u rezultat.