Test pierwszości Fermata to probabilistyczny test umożliwiający sprawdzenie czy dana liczba jest złożona czy prawdopodobnie pierwsza. Jest on jednym z najprostszych testów pierwszości. Oparty jest na małym twierdzeniu Fermata, które mówi, że jeżeli liczba p jest liczbą pierwszą to dla każdego a takiego, że 1≤a<p
a ^p-1 mod p = 1.

Test Fermata polega na losowym wybraniu liczby a takiej, że 1<a<p i sprawdzeniu czy równość jest prawdziwa (nie ma sensu sprawdzać dla a=1, gdyż dla każdej liczby nierówność będzie prawdziwa). W uproszczeniu możemy to zapisać następująco:
k- określa dokładność testu
p - liczba do sprawdzenia

powtórz k razy:
  wylosuj a takie, że 1<a<p
  sprawdź czy ap-1 mod p = 1
  jeżeli nie to przerwij test - liczba nie jest pierwsza
jeżeli równość była spełniona dla wszystkich prób, liczba prawdopodobnie jest pierwsza


Algorytm można przedstawić za pomocą następującego schematu blokowego:

Na pierwszy rzut oka trudność sprawiać może obliczenie wartości a^p-1 mod p, szczególnie dla dużych wartości p. Szybko i bezproblemowo obliczymy taką wartość używając algorytmu szybkiego potęgowania modularnego lub dużo wolniejszego, ale prostszego algorytmu naiwnego potęgowania modularnego

Przykład
Sprawdzimy z dokładnością k=3 czy liczba p=13 jest pierwsza.
Pierwsza próba, wylosowaliśmy a=12. 12¹² mod 13 = 1.
Druga próba, wylosowaliśmy a=3. 3¹² mod 13 = 1.
Trzecia próba, a=4. 4¹² mod 13 = 1.
Zatem prawdopodobnie liczba 13 jest liczbą pierwszą.

Sprawdzimy z dokładnością k=3 czy liczba p=63 jest pierwsza.
Pierwsza próba, wylosowaliśmy a=8. 8⁶² mod 63 = 1.
W drugiej próbie wylosowaliśmy a=34. 34⁶² mod 63 = 22.
Równość nie jest spełniona zatem liczba 63, z całą pewnością nie jest liczbą pierwszą.

Komentarze