Der algorithmische Prozess, zu entscheiden, ob eine gegebene ganze Zahl prim ist, wobei entweder ein deterministisches Zertifikat der Primalität oder ein probabilistisches Urteil mit hoher Wahrscheinlichkeit geliefert wird.

Prinzip

Primalitätstests nutzen zahlentheoretische Eigenschaften, die Primzahlen von Kompositen unterscheiden (Fermats kleiner Satz, starke wahrscheinliche Prim-Bedingungen, polynomiale Identitäten, elliptische Kurveneigenschaften) und liefern entweder einen eindeutigen Beweis oder ein randomisiertes Zeugnis dafür, dass eine Zahl mit hoher Wahrscheinlichkeit prim ist.

Demonstration

Beispiele: deterministische, in Polynomialzeit arbeitende Tests wie AKS (Prüfung einer polynomialen Kongruenz), probabilistische Algorithmen wie Miller–Rabin (Testen starker wahrscheinlicher Prim-Basen) und verifizierbare Verfahren wie ECPP, das ein Prüfzertifikat erzeugt; Miller–Rabin filtert z.B. schnell Komposite, während ECPP ein explizites Zertifikat für große in der Kryptographie genutzte Primzahlen erzeugen kann.

Fehlanwendung

Sich ausschließlich auf einen Fermat-Test zu verlassen, um Primalität zu behaupten, ohne Carmichael-Zahlen oder zusammengesetzte Zeugen zu berücksichtigen; einen probabilistischen Test dort anzuwenden, wo ein deterministischer Beweis erforderlich ist; oder Tests für ungerade Zahlen auf gerade oder triviale Eingaben ohne Vorverarbeitung zu verwenden.

Konsequenz

Effiziente Primalitätstests ermöglichen die praktische Erzeugung und Validierung großer Primzahlen für kryptographische Protokolle und die rechnerische Zahlentheorie; erzeugt ein deterministisches Zertifikat, so erreicht man absolute Sicherheit, geeignet für formale Verifikation und mathematische Beweise.

Umkehrung

Die Umkehrung ist die Ganzzahlfaktorisierung: Kenntnis der vollständigen Faktorisierung entscheidet sofort über Primalität, ist aber üblicherweise algorithmisch deutlich schwerer; Primalitätstests sind oft deutlich günstiger als vollständige Faktorisierung und liefern mitunter Zertifikate ohne Faktorisieren.

Abgrenzung

Betrifft die Primalitätsentscheidung für ganze Zahlenausgaben in expliziter Darstellung; schließt verwandte, aber verschiedene Aufgaben wie Ganzzahlfaktorisierung, Primalität algebraischer Ganzheiten ohne Überführung nach Z oder Heuristiken ohne beweisbare Fehlerschranken aus, sofern diese nicht explizit probabilistisch und quantifiziert sind.

Semantische Spannung

Spannung zwischen probabilistischen Tests (schnell, mit sehr geringer Fehlerwahrscheinlichkeit) und deterministischen Beweisen (langsamer, aber sicher); ebenso zwischen der Entscheidung als Ja/Nein-Test und der Erzeugung eines verifizierbaren Zertifikats — beides dient unterschiedlichen Anwendungen und Vertrauensanforderungen.

Synthese

Primalitätstestung umfasst algorithmische Kriterien von schnellen probabilistischen Kontrollen bis hin zu langsameren deterministischen Beweisen, die entscheiden, ob eine ganze Zahl prim ist; sie balanciert Laufzeit und Gewissheit entsprechend dem Anwendungsbedarf und trennt die Entscheidungsaufgabe von der meist härteren Faktorisierungsaufgabe.