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łaniaEdytuj

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  

WadyEdytuj

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żEdytuj