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 ${\displaystyle p}$ jest liczbą pierwszą i ${\displaystyle a}$ nie dzieli się przez ${\displaystyle p,}$ to

${\displaystyle a^{p-1}\equiv 1\ (\operatorname {mod} \,p).}$

Aby stwierdzić, czy ${\displaystyle p}$ jest pierwsza, można wybrać kilka losowych wartości ${\displaystyle a}$ względnie pierwszych z ${\displaystyle p}$ i sprawdzić, czy ta równość jest dla nich spełniona. Jeśli dla którejkolwiek z nich nie jest, to na pewno ${\displaystyle p}$ jest liczbą złożoną. Jeśli wszystkie ją spełniają, ${\displaystyle p}$ jest prawdopodobnie liczbą pierwszą albo pseudopierwszą

Używając algorytmu szybkiego potęgowania, możemy wykonać to w czasie ${\displaystyle \mathrm {O} (k\cdot \log ^{3}n),}$ gdzie ${\displaystyle k}$ jest liczbą losowo wybranych ${\displaystyle a.}$

Wady

Istnieją liczby złożone (liczby Carmichaela), dla których równość z twierdzenia zachodzi dla wszystkich ${\displaystyle a,}$ takich że ${\displaystyle \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 ${\displaystyle 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 ${\displaystyle a_{1},a_{2},\dots ,a_{s}.}$ Wtedy

${\displaystyle (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 ${\displaystyle a\cdot a_{i}}$ dla ${\displaystyle i=1,2,\dots ,s.}$