Warum Miller-Rabin statt Fermat-Primalitätstest?

Nach dem Beweis von Miller-Rabin muss eine Zahl, die den Fermat-Primalitätstest besteht , auch den Miller-Rabin-Test mit derselben Basis (eine Variable im Beweis) bestehen. Und die Komplexität der Berechnung ist dieselbe. $a$

Folgendes stammt aus dem Fermat-Primalitätstest :

Während Carmichael-Zahlen wesentlich seltener sind als Primzahlen 1, gibt es genug davon, dass der Fermat-Primalitätstest in der obigen Form oft nicht verwendet wird. Stattdessen werden häufiger leistungsstärkere Erweiterungen des Fermat-Tests wie Baillie-PSW, Miller-Rabin und Solovay-Strassen verwendet.

Was ist der Vorteil von Miller-Rabin und warum soll es leistungsfähiger sein als der Fermat-Primalitätstest?

algorithms primes ZijingWu
quelle

Antworten:

Der Rabin-Miller-Algorithmus testet bei einer gegebenen Zahl , ob eine nichttriviale Wurzel der Einheit hat. $n$ $Z_n$

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

Wir haben also folgendes:

$n$ $1/2$

$1/2$

Shaull
quelle

Meinen Sie damit, dass Carmichael Nummer n bei Fermats Test erfolgreich sein kann, bei Rabin-Miller jedoch mit derselben Basis gescheitert ist a?

ZijingWu

a

$a$

a

$a$

a

$a$

a

$a$

a

$a$

a

$a$

Der Punkt der "komplexeren" Tests ist, dass der Anteil der Basen, die liegen (sagen wir, die Zahl ist vielleicht eine Primzahl, wenn dies nicht der Fall ist), eine garantierte Grenze von weniger als 1 hat. Das heißt, in Miller-Rabin kann gezeigt werden, dass höchstens 1/4 Lüge (IIRC, und die Grenze ist ziemlich pessimistisch).

Vonbrand

Ich glaube, Ihre Aussage ist das Gegenteil von dem, was passiert. Wenn der Miller-Rabin-Test für eine bestimmte Basis bestanden wird, besteht der Fermat-Test für dieselbe Basis. Im Gegensatz dazu gibt es viele Verbundwerkstoffe, die den Fermat-Test für eine bestimmte Basis bestehen, den Miller-Rabin-Test für dieselbe Basis jedoch nicht bestehen.

Siehe zum Beispiel das Papier von Pomerance / Selfridge / Wagstaff auf der Wikipedia Miller-Rabin-Seite:

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

Hier sehen wir ein Diagramm auf Seite 2, in dem die Euler-Pseudoprimes eine Teilmenge der Fermat-Pseudoprimes und die starken Pseudoprimes eine Teilmenge davon sind. Der Solovay-Strassen-Test ist daher anspruchsvoller als der Fermat-Test und der Miller-Rabin-Test mehr als beide. Beide vermeiden das kritische Problem der Carmichael-Zahlen. Sie haben im Wesentlichen die gleiche Leistung, daher bevorzugen wir den Miller-Rabin-Test.

DanaJ
quelle

Es sollte offensichtlich sein, dass Miller-Rabin besser ist als Fermat.

$a^{p-1}$

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

Wenn das Ergebnis nicht 1 (modulo p) ist, ist p wieder zusammengesetzt. Wenn das Ergebnis jedoch 1 modulo p ist, überprüfen wir, ob wir diese 1 erhalten haben, indem wir ein Zwischenergebnis quadrieren, das nicht +1 oder -1 war, und in diesem Fall ist x auch als zusammengesetzt erwiesen.

Wir machen also genau den gleichen Arbeitsaufwand, aber es gibt noch mehr Möglichkeiten, um zu beweisen, dass x zusammengesetzt ist.

gnasher729
quelle