Test pierwszości Fermata

Test pierwszości Fermataprobabilistyczny 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 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

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

Zobacz też