Test pierwszości Fermata
Test pierwszości Fermata – 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
[edytuj | edytuj kod]Małe twierdzenie Fermata mówi, że jeśli jest liczbą pierwszą i nie dzieli się przez to
Aby stwierdzić, czy jest pierwsza, można wybrać kilka losowych wartości względnie pierwszych z 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
Wady
[edytuj | edytuj kod]Istnieją liczby złożone (liczby Carmichaela), dla których równość z twierdzenia zachodzi dla wszystkich takich że . 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ć, należy założyć, że równość nie jest spełniona dla a i jest spełniona dla Wtedy
zatem równość nie jest też spełniona dla wszystkich dla