Proth-Primzahltest mit Zeugen

Zunächst wird geprüft, ob k positiv und ungerade, n positiv und k kleiner als 2^n ist. Anschließend berechnet das Werkzeug die erforderliche modulare Potenz exakt. Eine erfolgreiche Kongruenz beweist die Primzahleigenschaft; ein erfolgloser Zeuge bleibt ergebnisoffen, sofern er keinen Faktor offenlegt.

Geben Sie eine echte Proth-Zahl und einen Zeugen ein

Eine Proth-Zahl besitzt genau die Form N = k × 2^n + 1. Dabei ist k eine positive ungerade ganze Zahl, n eine positive ganze Zahl und k strikt kleiner als 2^n. Jede dieser Bedingungen ist erforderlich. Der Rechner nimmt k und den Zeugen als Dezimaltext entgegen, damit große Werte exakt bleiben und nicht durch Gleitkommaarithmetik gerundet werden. Geben Sie n als ganze Zahl zwischen 1 und 10,000 ein. Das Werkzeug bildet N selbst, statt die Zahl zusätzlich abzufragen. So kann die angegebene Zahl nicht von ihren definierenden Parametern abweichen. Außerdem muss der Zeuge strikt zwischen 1 und N liegen. Bei geradem k, einem nicht positiven Wert oder k größer oder gleich 2^n wird die Eingabe als Nicht-Proth-Form zurückgewiesen; ein Satz wird nicht außerhalb seiner Voraussetzungen angewandt. Zahl, Exponent, Zeuge und Rest erscheinen bei Bedarf als Dezimalzeichenfolgen. Dadurch können Sie die Rechnung prüfen und die Werte verlustfrei in ein anderes Werkzeug für exakte Arithmetik übernehmen.

Verstehen Sie die Aussage der Kongruenz

Für eine gültige Proth-Zahl N besagt der Satz: N ist prim, wenn eine ganze Zahl a existiert, für die a^((N−1)/2) kongruent zu −1 modulo N ist. Der eingegebene Zeuge übernimmt die Rolle von a. Der Rechner bestimmt die modulare Potenz durch wiederholtes Quadrieren, ohne zuvor die riesige gewöhnliche Potenz aufzubauen. In der Ausgabe ist `residue` der kleinste nicht negative Rest. `passes_test` ist genau dann true, wenn dieser N−1 entspricht, also der modularen Darstellung von −1. Dann ist `prime_proven` true und das Urteil lautet `prime`. Unter den bereits geprüften Proth-Bedingungen ist dies ein deterministischer Beweis und keine bloße Wahrscheinlichkeitsaussage. Die Antwort enthält den exakten Exponenten (N−1)/2, sodass Sie die Kongruenz unabhängig nachvollziehen können. Der Algorithmus verwendet ausschließlich ganzzahlige Operationen, wählt keine zufälligen Zeugen und fragt weder Tabellen noch entfernte Dienste ab. Dieselbe Eingabe liefert deshalb stets dasselbe Ergebnis und legt alle wesentlichen Werte des Satzes offen.

Deuten Sie einen erfolglosen Zeugen korrekt

Wenn ein Zeuge nicht −1 ergibt, ist damit allein noch nicht bewiesen, dass die Zahl zusammengesetzt ist. Es bedeutet lediglich, dass dieser bestimmte Zeuge die hinreichende Bedingung des Satzes von Proth nicht erfüllt. Deshalb meldet der Rechner `inconclusive` statt `composite`, wenn der Rest abweicht und der Zeuge zu N teilerfremd ist. Sie können anschließend einen anderen mathematisch gewählten Zeugen oder ein weiteres deterministisches Primzahlverfahren einsetzen. Eine nützliche Ausnahme gibt es: Vor der Auswertung der Kongruenz berechnet das Werkzeug den größten gemeinsamen Teiler von Zeuge und N. Ist dieser Wert ein echter Faktor, lautet das eindeutige Ergebnis `composite`, und der Faktor wird ausgegeben. Diese Trennung verhindert, dass ein einseitiger Satz fälschlich als zweiseitiger Test behandelt wird. Auch automatisierte Abläufe bleiben dadurch korrekt: Akzeptieren Sie `prime` als Beweis, verwerfen Sie `composite` bei gefundenem Faktor und leiten Sie `inconclusive` an einen weiteren Test weiter, statt es unbemerkt als endgültigen Fehlschlag zu werten.