Test pierwszości Fermata

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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

Małe twierdzenie Fermata mówi że jeśli p jest liczbą pierwszą i 1 \le a < p, to

a^{p-1} \equiv 1 \pmod{p}.

Aby stwierdzić czy p 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 p jest liczbą złożoną. Jeśli wszystkie ją spełniają, p 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.

Wady[edytuj | edytuj kod]

Istnieją liczby złożone (liczby Carmichaela) dla których równość z twierdzenia zachodzi dla wszystkich a takich że \operatorname{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 a\in(\mathbb{Z}/n\mathbb{Z})^* 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

(a\cdot a_i)^{n-1} \equiv a^{n-1}\cdot a_i^{n-1} \equiv a^{n-1} \not\equiv 1\pmod{n}

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

Zobacz też[edytuj | edytuj kod]