Pocklington-Primzahltest

Das Pocklington–Lehmer-Kriterium macht aus einer partiellen Faktorisierung von n minus eins ein strenges Primzahlzertifikat. Anders als reine Probedivision oder eine einzelne Fermat-Kongruenz genügt es, genügend von n−1 zu faktorisieren, sodass der faktorisierte Teil F die Bedingung F im Quadrat mindestens n erfüllt, plus einen kurzen modularen Zeugen für jede Primzahl, die F teilt. Studierende, Krypto-Tutoren und Zahlentheorie-Notebooks nutzen diesen Pocklington-Primzahltest, um kleine und mittlere Primzahlen zu beweisen, ohne bis zur Quadratwurzel von n zu sieben. Sie liefern den Kandidaten n und die Primzahlen, deren Produkt F ist; die Engine prüft die Größenbedingung, sucht oder verifiziert Basen a und liefert ein strukturiertes Zertifikat oder einen klaren Fehler, wenn der faktorisierte Teil zu klein ist.

Was das Pocklington–Lehmer-Kriterium besagt

Schreiben Sie n minus eins als Produkt F mal R, wobei F vollständig in Primzahlen zerlegt ist, die Sie bereits kennen, und R der verbleibende Kofaktor ist.

Der klassische Satz von Pocklington lautet: Wenn F groß genug ist, dass F im Quadrat mindestens n ist, und für jede Primzahl q, die F teilt, eine ganzzahlige Basis a existiert, sodass a hoch n minus eins kongruent eins modulo n ist und der größte gemeinsame Teiler von a hoch (n minus eins) geteilt durch q, minus eins, mit n gleich eins ist, dann ist n prim.

Anschaulich erzwingen diese beiden modularen Bedingungen, dass die multiplikative Ordnung von a modulo n ein Vielfaches von q für jede solche Primzahl ist, also ein Vielfaches von F; zusammen mit F größer als die Wurzel von n kann kein zusammengesetztes n einen echten Teiler auf die übliche Weise verbergen. Das ist stärker als der kleine Satz von Fermat allein, der nur einen einzigen Potenzrest prüft und von Pseudoprimzahlen getäuscht werden kann.

Es ist auch sparsamer als die vollständige Faktorisierung von n oder Probedivision bis sqrt(n), wenn Sie bereits viele Faktoren von n−1 kennen—zum Beispiel wenn n eine Proth-Zahl, eine Safeprime-Konstruktion oder eine Übungszahl ist, die so gebaut ist, dass n−1 leicht faktorisiert.

Klassenzimmerbeweise, Krypto-Demos und Automatisierung

Zahlentheorie-Kurse nutzen einen Pocklington-Primzahltest, damit Lernende Primzahlen wie einunddreißig, einundsechzig oder siebenundneunzig zertifizieren, nachdem sie n−1 von Hand faktorisiert haben, statt nur einen undurchsichtigen is-prime-Knopf zu drücken. Wettbewerbs-Tools erzeugen Kandidaten mit glattem n−1, speisen die bekannten Faktoren in diesen Endpunkt und speichern die zurückgegebenen Zeugen als kurzes Beweisobjekt neben dem Lösungsschlüssel. Kryptografie-Notebooks, die Spielzeug-Safeprimes bauen oder zeigen, wie sich Primzahlzertifikate von probabilistischen Miller–Rabin-Runden unterscheiden, können goldene Zertifikate für feste n und factors festnageln, ohne modulare Exponentiation in jeder Sprache neu zu implementieren.

Bibliotheksautoren mit Property-Tests behaupten, dass certified true impliziert, dass ihre eigene Primzahlroutine auf demselben n übereinstimmt, und dass unzureichendes F stets den dokumentierten Fehler „Teil zu klein“ auslöst. Wenn Sie nur einen winzigen Ausschnitt von n−1 faktorisiert haben, faktorisieren Sie zuerst mehr oder nutzen Sie einen allgemeinen Primzahlprüfer; diese Landing bleibt der Suchintention Pocklington–Lehmer gewidmet, damit SEO, Beispiele und Antwortform fokussiert bleiben.