Lucas-Primzahltest

Geben Sie eine ungerade ganze Zahl n, einen vorgeschlagenen Lucas-Zeugen und die vollständige Primfaktorzerlegung von n minus eins an. Der Rechner prüft die Faktorisierung selbst, berechnet die erforderlichen modularen Potenzen und größten gemeinsamen Teiler und zertifiziert n nur, wenn sämtliche Bedingungen des Satzes von Lucas erfüllt sind. Dezimalzeichenfolgen erhalten ganze Zahlen exakt, auch jenseits des üblichen sicheren Zahlenbereichs von JavaScript.

Bereiten Sie ein vollständiges Zertifikat vor

Beginnen Sie mit der ungeraden ganzen Zahl, die Sie zertifizieren möchten, und faktorisieren Sie n minus eins vollständig. Geben Sie n und jeden Primfaktor als kanonische Dezimalzeichenfolge ein, denn Zeichenfolgen bewahren exakte Werte bis zur 64-Bit-Grenze. Jeder Faktor erscheint genau einmal mit seinem positiven Exponenten. Für n = 29 gilt beispielsweise n minus eins = 28 = 2 zum Quadrat mal 7; die Liste enthält daher 2 mit Exponent 2 und 7 mit Exponent 1. Zusätzlich müssen Sie eine Basis a mit 1 < a < n angeben. Diese Basis ist der vorgeschlagene Lucas-Zeuge. Der Prüfer verlangt den Zeugen bewusst, statt nach ihm zu suchen: Die Prüfung eines Zertifikats ist schnell, begrenzt und wiederholbar, während die Dauer einer Suche von der Eingabe abhängen kann. Falls Sie noch keinen Zeugen haben, testen Sie kleine Basen mit einem separaten Werkzeug für Primitivwurzeln und reichen Sie anschließend das erhaltene Zertifikat ein. Leerraum, Vorzeichen, führende Nullen, Gleitkommanotation, doppelte Primzahlen, zusammengesetzte Faktoren und fehlende Faktoren werden abgelehnt und nicht stillschweigend normalisiert. Dadurch eignet sich das Zertifikat für Prüfprotokolle und automatisierte Abläufe.

Verstehen Sie die beiden Lucas-Bedingungen

Die erste Berechnung prüft, ob a hoch n minus eins kongruent zu 1 modulo n ist. Dies ist die bekannte Fermat-Bedingung, die allein jedoch keine Primzahl beweist, weil Pseudoprimzahlen sie erfüllen können. In der entscheidenden zweiten Stufe wird jede verschiedene Primzahl q verwendet, die n minus eins teilt. Für jedes q berechnet der Prüfer a hoch (n minus eins) geteilt durch q modulo n, zieht eins ab und prüft, ob das Ergebnis mit n den größten gemeinsamen Teiler 1 hat. Wenn alle Prüfungen erfolgreich sind, ist die multiplikative Ordnung von a modulo n nachweislich genau n minus eins. Ein Element modulo n kann diese Ordnung nur besitzen, wenn n prim ist; das ist der Kern des Satzes von Lucas. Die zurückgegebenen Prüfeinträge zeigen den modularen Rest und den größten gemeinsamen Teiler für jedes verschiedene q, während der Exponent als Teil der validierten Faktorisierung sichtbar bleibt. Die modulare Potenzierung nutzt wiederholtes Quadrieren mit exakter BigInt-Arithmetik. Die Berechnung hängt daher weder von Gleitkommarundung noch von Zufallsbasen, Netzwerkdiensten oder probabilistischer Sicherheit ab.

Deuten Sie Fehler und erfolgreiche Ausgaben

Eine erfolgreiche Antwort ist das Ergebnis eines Primzahlzertifikats und nicht bloß die Einstufung als wahrscheinlich prim. Sie wiederholt n, nennt den akzeptierten Zeugen, gibt den Fermat-Rest aus und führt für jeden verschiedenen Faktor von n minus eins eine erfolgreiche Prüfung des größten gemeinsamen Teilers auf. Bewahren Sie die ursprüngliche Eingabe zusammen mit dieser Antwort auf, wenn ein anderes System den Beweis nachvollziehen soll. Fehlermeldungen sind absichtlich präzise. Ergibt das Produkt der Faktorpotenzen nicht genau n minus eins, ist die Faktorisierung unvollständig oder anderweitig falsch. Ist ein angegebener Faktor zusammengesetzt oder erscheint dieselbe Primzahl zweimal, ist die Faktorisierung selbst bei passendem Rohprodukt fehlerhaft. Das Scheitern einer modularen Bedingung bedeutet, dass die angegebene Basis kein Lucas-Zeuge ist; allein dadurch lässt sich eine zusammengesetzte Zahl n nicht von einer Primzahl mit ungeeigneter Basis unterscheiden. Probieren Sie einen mathematisch begründeten anderen Zeugen, falls Sie weiterhin eine Primzahl erwarten. Die Eingabe ist auf ungerade ganze Zahlen von 3 bis 2^64 minus 1 beschränkt. So lassen sich die angegebenen Primfaktoren vor der Zertifikatsprüfung deterministisch validieren. Der API-Preis beträgt $0.002 je Anfrage.