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\ (\operatorname {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 $\mathrm {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 $\operatorname {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}\not \equiv 1\ (\operatorname {mod} \,n),$

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