Fermat-Pseudoprimzahlen für jede Basis prüfen

Eine bestehende zusammengesetzte Zahl ist zur gewählten Basis eine Fermat-Pseudoprimzahl: Sie verhält sich in diesem einzelnen Test wie eine Primzahl, obwohl sie keine ist. Zusätzlich wird der größte gemeinsame Teiler ausgegeben, damit Sie das Ergebnis leichter untersuchen und erklären können.

Was ein positives Ergebnis tatsächlich bedeutet

Der kleine Satz von Fermat besagt: Ist n eine Primzahl und a nicht durch n teilbar, dann hinterlässt a hoch n minus eins bei Division durch n den Rest eins. Die Umkehrung gilt jedoch nicht. Auch manche zusammengesetzten ganzen Zahlen ergeben für bestimmte Basen den Rest eins; sie heißen Fermat-Pseudoprimzahlen zu diesen Basen. Dieses Werkzeug verlangt ausdrücklich eine zusammengesetzte Zahl n, prüft diese Voraussetzung zuerst und wertet danach die Kongruenz exakt aus. Sind passes_fermat_test und is_fermat_pseudoprime wahr, hat die angegebene zusammengesetzte Zahl den Fermat-Test für genau diese Basis getäuscht. Das bedeutet weder, dass n prim oder wahrscheinlich prim ist, noch dass n für jede Basis pseudoprim ist. Die Basis gehört zur Aussage und sollte stets zusammen mit dem Ergebnis genannt werden. Der ausgegebene Rest liefert den unmittelbaren rechnerischen Nachweis: Eins bedeutet bestanden, jeder andere Wert bedeutet nicht bestanden. Der größte gemeinsame Teiler ist ebenfalls hilfreich, weil ein nicht trivialer Teiler viele Fehlschläge sofort erklärt und Versuche mit teilerfremden Basen von Eingaben unterscheidet, die bereits eine Faktorbeziehung zeigen.

Wie die Berechnung exakt bleibt

Beide Eingaben werden als Dezimalzeichenketten übergeben, damit ganze Zahlen oberhalb des sicheren JavaScript-Zahlenbereichs vor der Berechnung nicht gerundet werden. Der zulässige Bereich endet bei der größten vorzeichenlosen 64-Bit-Ganzzahl. Dadurch besitzt die Primzahlprüfung eine klare, durchsetzbare Grenze. Vor dem Fermat-Test verwendet das Werkzeug ein deterministisches Miller–Rabin-Verfahren mit einer Zeugenmenge, die für diesen gesamten Bereich ausreicht. Wird eine Primzahl erkannt, folgt ein Eingabefehler: Primzahlen erfüllen zwar den Satz, können definitionsgemäß aber keine Pseudoprimzahlen sein. Für eine gültige zusammengesetzte Zahl nutzt die modulare Potenzierung wiederholtes Quadrieren, statt den riesigen Wert a^(n-1) aufzubauen. Jede Multiplikation wird modulo n reduziert, sodass die Zwischenwerte mit BigInt begrenzt und exakt bleiben. Den Wert gcd(a,n) berechnet der euklidische Algorithmus separat. Die Basis muss 2 <= a <= n - 2 erfüllen. Zufällige Zeugen, Zeitwerte, Netzwerkaufrufe oder Gleitkommaoperationen beeinflussen die Antwort nicht; gleiche Eingaben führen daher immer zur gleichen Ausgabe.

Einsatz beim Lernen und Überprüfen

Ein klassisches Beispiel ist n = 341 mit der Basis a = 2. Obwohl 341 zusammengesetzt ist, ist 2^340 kongruent zu eins modulo 341. Die Zahl besteht daher den Test und ist zur Basis zwei eine Fermat-Pseudoprimzahl. Bei einer anderen Basis kann dieselbe zusammengesetzte Zahl durchfallen; ein einzelner Fermat-Test ist deshalb kein allgemeines Primzahlzertifikat. Im Unterricht verbindet die strukturierte Ausgabe die Definition direkt mit dem berechneten Rest. In einer Testsuite können Sie bekannte Vektoren für Pseudoprimzahlen und Nicht-Pseudoprimzahlen festhalten, ohne von einem Mathematikpaket oder maschinenabhängigen Zahlenumwandlungen abhängig zu sein. Für eigene Untersuchungen vergleichen Sie mehrere zulässige Basen bei festem n und beobachten, wie entscheidend die Wahl des Zeugen ist. Verstehen Sie ein wahres Ergebnis als Beleg für die Grenze des Fermat-Tests, nicht als Erlaubnis, die Zahl in kryptografischem oder sicherheitskritischem Code als prim anzunehmen. Die API kostet $0.002 pro geprüftem Paar; im Browser läuft dieselbe deterministische Berechnung lokal.