##  [Primalitätstest](/de/node/62907) 

 Definition

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

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

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

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

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

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

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

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

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.