Test pierwszości Fermata
Z Wikipedii
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.
[edytuj] Zasada działania
Małe twierdzenie Fermata mówi że jeśli p jest liczbą pierwszą i 
, to
.
Aby stwierdzić czy n jest pierwsza, możemy wybrać kilka losowych wartości a i sprawdzić czy ta równość jest dla nich spełniona. Jeśli dla któregokolwiek nie jest, wiemy na pewno że n jest liczbą złożoną. Jeśli wszystkie ją spełniają, n jest prawdopodobnie liczbą pierwszą albo pseudopierwszą
Używając algorytmu szybkiego potęgowania możemy wykonać to w czasie O(k × log3n), gdzie k jest liczbą losowo wybranych a.
[edytuj] Wady
Istnieją liczby złożone (liczby Carmichaela) dla których równość z twierdzenia zachodzi dla wszystkich a takich że gcd(a,n)=1. Tym samym test ma bardzo duże prawdopodobieństwo uznania takich liczb za pierwsze.
W ogólności, jeśli n nie jest liczbą Carmichaela, wtedy co najmniej połowa 
nie spełnia równości. Aby to udowodnić załóżmy że równość nie jest spełniona dla a, i jest spełniona dla a1, a2, ..., as. Wtedy
zatem równość nie jest też spełniona dla wszystkich a × ai dla i = 1, 2, ..., s.
