Test Fermata na liczbę pierwszą, prawdopodobieństwo

[gszpetkowski]

Załóżmy, że mamy następujący algorytm do określania, czy liczba jest pierwsza, czy złożona (oparty o małe twierdzenie Fermata):

1. Pobierz liczbę \(\displaystyle{ n \in \mathbb{N} : n > 3}\)
2. Wybierz losową bazę \(\displaystyle{ a \in \mathbb{N} : 2 \le a \le n-2}\)
3. Oblicz \(\displaystyle{ b = a^{n-1} \mod n}\)
4. Jeżeli \(\displaystyle{ b = 1}\), to uznaj \(\displaystyle{ n}\) za liczbę prawdopodobnie pierwszą, w przeciwnym wypadku jako z pewnością złożoną

Moje pytanie brzmi czy jeżeli warunek (4.) będzie spełniony dla wszystkich baz, to czy można z całą pewnością stwierdzić, że \(\displaystyle{ n}\) jest liczbą pierwszą (w szczególności nie jest liczbą Carmichaela) ?

Ze względów praktycznych obliczeniowo chciałbym jednak zastosować algorytm dla \(\displaystyle{ k}\) losowych baz, gdzie \(\displaystyle{ k}\) jest arbitalnie wybraną wartością np. 20 tak aby osiągnąć prawdopodobieństwo poprawnego rozpoznania liczby pierwszej lub liczby Carmichaela:

\(\displaystyle{ p \ge 1 - \frac{1}{2^{20}}}\)

Jak rozumiem główną "słabością" takiego podejścia są liczby Carmichela, stąd stosuje się inne metody np. Miller-Rabin ?

[Kartezjusz]

Właśnie. Liczy Carmichaela powodują, że mamy to "prawdopodobnie. Nawet po przetestowaniu wszystkich baz.

[gszpetkowski]

Właśnie. Liczy Carmichaela powodują, że mamy to "prawdopodobnie. Nawet po przetestowaniu wszystkich baz.

Rozumiem, tylko czy na pewno dotyczy to także drugiej postaci (co do pierwszej postaci pełna zgoda, zresztą taka jest wręcz definicja liczby Carmichela) małego twierdzenia Fermata, które wymaga aby \(\displaystyle{ n}\) i \(\displaystyle{ a}\) były względnie pierwsze ? Chodzi mi o to, że dla liczby Carmichela (jako że jest złożona) na którymś \(\displaystyle{ a}\) na pewno zajdzie nierówność \(\displaystyle{ NWD(n, a) \ne 1}\) i algorytm wykryje liczbę złożoną. Przykładowo dla \(\displaystyle{ 561 = 3 \cdot 11 \cdot 17}\) mamy:

dla \(\displaystyle{ a = 2}\):

\(\displaystyle{ 2^{560} \mod 561 = 1}\)

dla \(\displaystyle{ a = 3}\):

\(\displaystyle{ 3^{560} \mod 561 = 375 \ne 1}\)

[Zordon]

No tak, w końcu trafisz coś co ma nietrywialne gcd z liczbą, ale duże liczby Carmichela moga mieć duże dzielniki pierwsze, więc szansa trafienia jest nikła.

[gszpetkowski]

No tak, w końcu trafisz coś co ma nietrywialne gcd z liczbą, ale duże liczby Carmichela moga mieć duże dzielniki pierwsze, więc szansa trafienia jest nikła.

Tak, o to właśnie mi chodziło. Zdaje sobie sprawę, że takie pełne sprawdzanie byłoby nieefektywne dla dużych liczb, tym bardziej że udowodniono, że liczb Carmichela jest nieskończenie wiele.

Jak rozumiem test Fermata natomiast bardzo dobrze nadaje się do sprawdzania, czy liczba jest złożona, czy inaczej pisząc do szybkiej eliminacji większości liczb złożonych w danym zakresie (ew. jeszcze wcześniej można by spróbować ang. trial division dla pierwszych \(\displaystyle{ k}\) liczb pierwszych), stanowiąc dobry punkt wyjścia dla innych, "cięższych" obliczeniowo metod takich jak Miller-Rabin, czy dalej deterministyczny AKS.

[Zordon]

Miller-Rabin w istocie nie jest cięższy. Tzn. złożoność jest w gruncie rzeczy taka sama.

[gszpetkowski]

Miller-Rabin w istocie nie jest cięższy. Tzn. złożoność jest w gruncie rzeczy taka sama.

Czy na pewno ? Zauważ, że algorytm Millera-Rabina (z tego co przeczytałem w ) oparty został o nieco bardziej złożone twierdzenie i wydaje mi się, że wymaga nieco większego nakładu obliczeniowego. Rzeczone twierdzenie mówi, że jeżeli n jest liczbą pierwszą, nieparzystą oraz mamy:

\(\displaystyle{ n-1 = 2^{s}t}\) (gdzie t jest liczbą nieparzystą)

to spełnione jest:

\(\displaystyle{ a^{t}\equiv 1 \pmod{n}}\)

lub

\(\displaystyle{ a^{2^{i}t}\equiv -1 \pmod{n}}\) dla pewnego \(\displaystyle{ i : 0 \le i \le s -1}\)

Pisząc oględnie w porównaniu do testu Fermata nie dość, że trzeba (na początku) wyznaczyć \(\displaystyle{ s}\) i \(\displaystyle{ t}\) dla parzystej \(\displaystyle{ n-1}\), to dla każdej wylosowanej bazy \(\displaystyle{ a}\) do sprawdzenia są dwie kongruencje zamiast jednej, przy czym druga wymaga dodatkowo rozbicia na pętle.

[Zordon]

Jeśli założyć, że mnożysz w czasie \(\displaystyle{ O(1)}\) to obie metody mają złożoność \(\displaystyle{ O(\log n)}\), czyli nie ma wielkiej różnicy w czasie działania.

Edit: oczywiście jest inna różnica - fundamentalna - metoda Rabina-Millera działa, a test Fermata nie

[gszpetkowski]

Jeśli założyć, że mnożysz w czasie \(\displaystyle{ O(1)}\) to obie metody mają złożoność \(\displaystyle{ O(\log n)}\), czyli nie ma wielkiej różnicy w czasie działania.

Edit: oczywiście jest inna różnica - fundamentalna - metoda Rabina-Millera działa, a test Fermata nie

Rzeczywiście masz rację, każdy z tych kroków zamyka się w \(\displaystyle{ O(\log n)}\), stąd taka, a nie inna złożoność całego algorytmu. Dzięki za uwagę Natomiast ciekawi mnie jak to wyjdzie w praktyce i czy warto kombinować ze sobą Fermata (do odrzucenia większej części liczb złożonych) i Millera-Rabina w celu wyszukiwania liczb pierwszych typu industrial-grade w zadanym przedziale \(\displaystyle{ [n, k]}\).