Der Test von Fermat primality ist ein Probabilistic-Test, um zu bestimmen, ob eine Zahl wahrscheinliche Blüte ist.

Konzept

Der kleine Lehrsatz von Fermat stellt das fest, wenn p erst ist und

:

Wenn wir prüfen wollen, wenn p erst ist, dann können wir zufälligen a's im Zwischenraum aufpicken und sehen, ob die Gleichheit hält. Wenn die Gleichheit für einen Wert von a nicht hält, dann ist p zerlegbar. Wenn die Gleichheit wirklich für viele Werte von a hält, dann können wir sagen, dass p wahrscheinliche Blüte ist.

Es könnte in unseren Tests sein, dass wir keinen Wert für einen solchen aufpicken, dass die Gleichheit scheitert. Irgendwelcher ein solcher dass

:

wenn n zerlegbar ist, ist als ein Lügner von Fermat bekannt. Umgekehrt in diesem Fall wird n Fermat genannt, der pseudoerst ist, um a zu stützen.

Wenn wir wirklich einen solchen dass aufpicken

:

dann bekannt als Fermat zu sein, zeugt für die Zerlegbarheit von n.

Beispiel

Nehmen Sie an, dass wir bestimmen möchten, ob n = 221 erst ist. Picken Sie zufällig 1  ein auf

Entweder 221 ist erst, oder 38 ist ein Lügner von Fermat, so nehmen wir einen anderen a, sagen 26:

:

So 221 ist zerlegbar, und 38 war tatsächlich ein Lügner von Fermat.

Algorithmus und Laufzeit

Der Algorithmus kann wie folgt geschrieben werden:

Eingänge: n: ein Wert, um für primality zu prüfen; k: Ein Parameter, der die Zahl von Zeiten bestimmt, um für primality zu prüfen

Produktion: Zusammensetzung, wenn n, sonst wahrscheinlich erster zerlegbar

ist

Wiederholung k Zeiten:

picken Sie zufällig in der Reihe [1, n &minus auf; 1]

wenn, dann Zusammensetzung zurückgeben Sie

geben Sie wahrscheinlich ersten zurück

Mit schnellen Algorithmen für modularen exponentiation ist die Laufzeit dieses Algorithmus O (k × logn × Klotz loggen n × Klotz-Klotz loggen n), wo k die Zahl von Zeiten ist, prüfen wir einen zufälligen a, und n ist der Wert, den wir für primality prüfen wollen.

Fehler

Es gibt ungeheuer viele Werte dessen (bekannt als Zahlen von Carmichael), für die Werte für der Lügner von Fermat sind. Während Zahlen von Carmichael wesentlich seltener sind als Primzahlen, gibt es genug von ihnen, dass der Primality-Test von Fermat häufig für andere Primality-Tests wie Müller-Rabin und Solovay-Strassen nicht verwendet wird.

Im Allgemeinen, wenn nicht eine Zahl von Carmichael dann mindestens Hälfte des ganzen ist

:

sind Zeugen von Fermat. Für den Beweis davon, lassen Sie, ein Zeuge von Fermat zu sein und... Lügner von Fermat zu sein. Dann

:

und so alle dafür Zeugen von Fermat sind.

Anwendungen

Das Verschlüsselungsprogramm PGP verwendet diesen Primality-Test in seinen Algorithmen. Die Chance von PGP das Erzeugen einer Zahl von Carmichael ist weniger als 1 in 10, der zu praktischen Zwecken mehr als entsprechend ist.