Test pierwszości Fermata

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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[edytuj]

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 .

Wady[edytuj]

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 a1, a2, ..., as. Wtedy

,

zatem równość nie jest też spełniona dla wszystkich aai dla i = 1, 2, ..., s.

Zobacz też[edytuj]