Test pierwszości Fermata

Aby zapoznać się z testem określającym, czy liczba Fermata jest liczbą pierwszą, zobacz test Pépina .

Test pierwszości Fermata jest testem probabilistycznym służącym do określenia, czy liczba jest prawdopodobną liczbą pierwszą .

Pojęcie

Małe twierdzenie Fermata mówi, że jeśli p jest liczbą pierwszą i a nie jest podzielne przez p , to

${\ Displaystyle a ^ {p-1} \ równoważnik 1 {\ pmod {p}}.}$

Jeśli ktoś chce sprawdzić, czy p jest liczbą pierwszą, możemy wybrać losowe liczby całkowite a niepodzielne przez p i sprawdzić, czy zachodzi równość. Jeśli równość nie zachodzi dla wartości a , to p jest złożone. Ta zgodność jest mało prawdopodobna dla losowego a, jeśli p jest złożone. Dlatego jeśli równość zachodzi dla jednej lub więcej wartości a , to mówimy, że p jest prawdopodobnie liczbą pierwszą .

$.$ trywialna dla ponieważ relacja kongruencji jest potęgowaniem $,$ odnosi się to również do że p jest powodu. Dlatego zwykle wybiera się losowo a w przedziale ${\ Displaystyle 1 <a <p-1$ }

Jakieś takie _

${\ Displaystyle a ^ {n-1} \ równoważnik 1 {\ pmod {n}}}$

gdy n jest złożone, jest znane jako kłamca Fermata . W tym przypadku n nazywa się pseudopierwszą Fermata , aby oprzeć a .

Jeśli wybierzemy takie , że

${\ Displaystyle a ^ {n-1} \ nie \ równoważnik 1 {\ pmod {n}}}$

wtedy a jest znane jako świadek Fermata dla złożoności n .

Przykład

Załóżmy, że chcemy ustalić, czy n = 221 jest liczbą pierwszą. Wybierz losowo 1 < a < 220, powiedzmy a = 38. Sprawdzamy powyższą równość i stwierdzamy, że zachodzi:

${\ Displaystyle a ^ {n-1} = 38 ^ {220} \ równoważnik 1 {\ pmod {221}}.}$

Albo 221 jest liczbą pierwszą, albo 38 jest kłamcą Fermata, więc bierzemy kolejne a , powiedzmy 24:

${\ Displaystyle a ^ {n-1} = 24 ^ {220} \ równoważnik 81 \ nie \ równoważnik 1 {\ pmod {221}}.}$

Więc 221 jest złożone, a 38 rzeczywiście było kłamcą Fermata. Co więcej, 24 jest świadkiem Fermata dla złożoności 221.

Algorytm

Algorytm można zapisać w następujący sposób:

Wejścia : n : wartość do sprawdzenia pierwszości, n > 3; k : parametr, który określa, ile razy należy przetestować pierwszorzędność

Wyjście : złożone, jeśli n jest złożone, w przeciwnym razie prawdopodobnie pierwsze

Powtórz k razy:

Wybierz losowo a z zakresu [2, n − 2]

Jeśli ${\ Displaystyle a ^ {n-1} \ not \ equiv 1 {\ pmod {n}}}$ , a następnie zwróć kompozyt

Jeśli kompozyt nigdy nie zostanie zwrócony: zwróć prawdopodobnie liczbę pierwszą

Wartości a 1 i n -1 nie są używane, ponieważ równość obowiązuje odpowiednio dla wszystkich n i wszystkich nieparzystych n , dlatego ich testowanie nie dodaje żadnej wartości.

Złożoność

Wykorzystując szybkie algorytmy modułowego potęgowania i mnożenia z wieloma precyzjami, czas działania tego algorytmu wynosi O ( k log ² n log log n ) = Õ ( k log ² n ) , gdzie k to liczba testów losowego a , a n jest wartością, którą chcemy przetestować pod kątem pierwszości; szczegółowe informacje można znaleźć w teście pierwszości Millera – Rabina .

Wada

Istnieje nieskończenie wiele liczb pseudopierwszych Fermata dla dowolnej bazy a>1 . Co gorsza, istnieje nieskończenie wiele liczb Carmichaela . Są to liczby $n$$a, n) = 1}$ których wszystkie wartości z $Displaystyle \ operatorname {gcd}$ są kłamcami Fermata. W przypadku tych liczb wielokrotne zastosowanie testu pierwszości Fermata działa tak samo, jak proste losowe wyszukiwanie czynników. Chociaż liczby Carmichaela są znacznie rzadsze niż liczby pierwsze (górna granica Erdösa dla liczby liczb Carmichaela jest niższa niż funkcja liczb pierwszych n/log(n) ) jest ich wystarczająco dużo, aby test pierwszości Fermata nie był często używany w powyższej formie. Zamiast tego częściej stosuje się inne, potężniejsze rozszerzenia testu Fermata, takie jak Baillie – PSW , Miller – Rabin i Solovay – Strassen .

Ogólnie rzecz biorąc, jeśli jest $złożoną$ , która nie jest liczbą Carmichaela, to co najmniej połowa wszystkich

${\ Displaystyle a \ in (\ mathbb {Z} / n \ mathbb {Z}) ^ {*}}$ (tj. ${\ Displaystyle \ nazwa operatora {gcd} (a,n)=1}$ )

są świadkami Fermata. Aby to udowodnić, niech $\$ Fermata i $displaystyle a_ {1}}$ , ${\ displaystyle a_ {2}}$ , ..., ${\ displaystyle a_ { s}}$ być kłamcami Fermata. Następnie

${\ Displaystyle (a \ cdot a_ {i}) ^ {n-1} \ równoważnik a^{n-1}\cdot a_{i}^{n-1}\równoważnik a^{n-1}\not \równoważnik 1{\pmod {n}}}$

i tak wszystko ${\ Displaystyle a \ cdot a_ {i}}$ dla ${\ Displaystyle i = 1,2, ..., s}$ świadkami Fermata.

Aplikacje

Jak wspomniano powyżej, większość aplikacji wykorzystuje test pierwszości Millera-Rabina lub Baillie-PSW . Czasami test Fermata (wraz z próbnym dzieleniem przez małe liczby pierwsze) jest wykonywany jako pierwszy w celu poprawy wydajności. GMP od wersji 3.0 używa testu Fermata base-210 po podziale próbnym i przed uruchomieniem testów Millera-Rabina. Libgcrypt używa podobnego procesu z podstawą 2 do testu Fermata, ale OpenSSL tego nie robi.

W praktyce w przypadku większości bibliotek dużych liczb, takich jak GMP, test Fermata nie jest zauważalnie szybszy niż test Millera-Rabina i może być wolniejszy dla wielu danych wejściowych.

Jako wyjątek, OpenPFGW używa tylko testu Fermata do testowania prawdopodobnych liczb pierwszych. Program jest zwykle używany z wejściami zawierającymi wiele tysięcy cyfr, których celem jest maksymalna prędkość przy bardzo dużych wejściach. Innym dobrze znanym programem, który opiera się tylko na teście Fermata, jest PGP , w którym jest używany tylko do testowania generowanych przez siebie dużych losowych wartości (odpowiednik open source, GNU Privacy Guard , używa wstępnego testu Fermata, po którym następują testy Millera-Rabina).

•   Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein (2001). „Sekcja 31.8: Testowanie pierwszości” . Wprowadzenie do algorytmów (wyd. Drugie). MIT Press; McGraw-Hill. P. 889–890. ISBN 0-262-03293-7 . {{ cite book }} : CS1 maint: wiele nazwisk: lista autorów ( link )