Test pierwszości Fermata

Test pierwszości Fermata to probabilistyczny test umożliwiający sprawdzenie, czy dana liczba jest złożona, czy prawdopodobnie pierwsza. Jest jednym z najprostszych testów pierwszości i pomimo swoich wad jest wykorzystywany w algorytmach szyfrowania PGP.

Zasada działania

Małe twierdzenie Fermata mówi, że jeśli jest liczbą pierwszą i , to

.

Aby stwierdzić, czy jest pierwsza, można wybrać kilka losowych wartości i sprawdzić, czy ta równość jest dla nich spełniona. Jeśli dla którejkolwiek z nich nie jest, to na pewno jest liczbą złożoną. Jeśli wszystkie ją spełniają, jest prawdopodobnie liczbą pierwszą albo pseudopierwszą

Używając algorytmu szybkiego potęgowania, możemy wykonać to w czasie , gdzie jest liczbą losowo wybranych .