Dlaczego Miller – Rabin zamiast testu pierwotności Fermata?

10

Z dowodu Millera-Rabina , jeśli liczba przechodzi test pierwotności Fermata , musi również przejść test Millera-Rabina z tą samą podstawą (zmienną w dowodzie). A złożoność obliczeń jest taka sama. $a$

Z testu pierwotności Fermata wynika :

Chociaż liczby Carmichaela są znacznie rzadsze niż liczby pierwsze, 1 jest ich wystarczająco dużo, aby test pierwszeństwa Fermata często nie był stosowany w powyższej formie. Zamiast tego częściej stosuje się inne bardziej rozbudowane rozszerzenia testu Fermata, takie jak Baillie-PSW, Miller-Rabin i Solovay-Strassen.

Jakie są zalety Miller-Rabin i dlaczego mówi się, że ma większą moc niż test pierwotności Fermata?

algorithms primes

— ZijingWu
źródło

7

$n$ $Z_n$

$a$ $n$ $a$ $a$ $a,2a,...,2^ra$

Mamy zatem następujące:

$n$ $1/2$

$1/2$

— Shaull
źródło

Czy masz na myśli, że Carmichael numer n może odnieść sukces w teście Fermata, ale nie powiódł się u Rabina-Millera przy użyciu tej samej bazy a?

— ZijingWu

a

$a$

a

$a$

a

$a$

a

$a$

a

$a$

a

$a$

1

Istotą „bardziej złożonych” testów jest to, że ułamek zasad, które leżą (powiedzmy, że liczba jest liczbą pierwszą, jeśli nie jest), ma gwarantowany limit mniejszy niż 1. To znaczy, w Miller-Rabin można wykazać, że co najwyżej 1/4 kłamstwa (IIRC, a granica jest dość pesymistyczna).

— vonbrand,

0

Uważam, że twoje oświadczenie jest przeciwieństwem tego, co się dzieje. Zaliczenie testu Millera-Rabina dla danej bazy oznacza, że przejdzie on test Fermata dla tej samej bazy. Przeciwnie, istnieje wiele kompozytów, które przejdą test Fermata dla danej bazy, ale nie przejdą testu Millera-Rabina dla tej samej bazy.

Zobacz na przykład artykuł Pomerance / Selfridge / Wagstaff na stronie Wikipedii Miller-Rabin:

https://math.dartmouth.edu/~carlp/PDF/paper25.pdf

gdzie widzimy diagram na stronie 2 pokazujący pseudopierwsze Eulera będące podzbiorem pseudopierwszych Fermata, a silne pseudopierwsze będące podzbiorem tych. Test Solovaya-Strassena jest zatem bardziej wymagający niż test Fermata, a test Millera-Rabina bardziej niż którykolwiek z nich. Obaj unikają krytycznego problemu liczb Carmichaela. Mają zasadniczo taką samą wydajność, dlatego wolimy zastosować test Millera-Rabina.

— DanaJ
źródło

0

Powinno być oczywiste, że Miller-Rabin jest lepszy niż Fermat.

$a^{p-1}$

$a^{p-1}$ $p-1 = s·2^k$ $a^s$ $a^{p-1}$

Ponownie, jeśli wynikiem nie jest 1 (moduł p), wówczas p jest złożone. Ale jeśli wynikiem jest 1 modulo p, to sprawdzamy, czy otrzymaliśmy ten 1, podnosząc do kwadratu wynik pośredni, który nie był +1 lub -1, i w tym przypadku x jest również sprawdzonym złożonym.

Wykonujemy dokładnie taką samą ilość pracy, ale istnieje więcej sposobów na udowodnienie, że x jest złożony.

— gnasher729
źródło