Test pierwszości Fermata

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

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 × log³n), gdzie k jest liczbą losowo wybranych a.

Wady

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 a₁, a₂, ..., a_s. 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 × a_i dla i = 1, 2, ..., s.

Zobacz też

• Test pierwszości
• Test Millera-Rabina