Test pierwszości Fermata

Test pierwszości Fermata – 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 $a$ nie dzieli się przez $p,$ to

$a^{p-1}\equiv 1(\mathrm{mod}p).$

Aby stwierdzić, czy $p$ jest pierwsza, można wybrać kilka losowych wartości $a$ względnie pierwszych z $p$ i sprawdzić, czy ta równość jest dla nich spełniona. Jeśli dla którejkolwiek z nich nie jest, to na pewno $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\cdot {\log }^{3}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 $\mathrm{NWD}(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ć, należy założyć, że równość nie jest spełniona dla a i jest spełniona dla $a_1,a_2,\dots ,a_s.$ Wtedy

$(a\cdot a_i{)}^{n-1}\equiv a^{n-1}\cdot a_i^{n-1}\equiv a^{n-1}\equiv ̸1(\mathrm{mod}n),$

zatem równość nie jest też spełniona dla wszystkich $a\cdot a_i$ dla $i=1,2,\dots ,s.$