Nicht -mal mit malnehmen, denn Aufwand wäre , sondern:
Aufwand: , d.h. proportional zur Anzahl der Dezimalstellen.
Algorithmus von Euklid zur Bestimmung des :
Bestimme und stelle den auftretenden Rest als Linearkombination von und dar.
Beispiel:
Wähle 500 Bit lange ungerade Zahl .
Teste, ob Primzahl ist.
Sei die Anzahl der Primzahlen unterhalb von . Es gilt:
Dichte
mittlerer Abstand
Also zeigt sich Erfolg beim Testen ungerader Zahlen der Größe nach etwa Versuchen.
Komplexitätsklassen für die Erkennung von Primzahlen:
es gibt Algorithmus , der angesetzt auf die Frage, ob , nach polynomialer Zeit mit ja oder nein anhält und folgende Gewähr für die Antwort gilt:
Antwort: ja ist zusammengesetzt.
Antwort: nein ist höchstwahrscheinlich prim.
Bei 50 Versuchen Fehler .
Satz von Rabin:
Sei eine Primzahl,
Beispiel:
Sei , sei = 2.
Definition eines Zeugen:
Sei .
Eine Zahl heißt Zeuge für die Zusammengesetztheit von
Satz von Rabin:
Ist zusammengesetzt, so gibt es mindestens Zeugen.
function prob-prim (n: integer): boolean z:=0; repeat z=z+1; wuerfel x; until (x ist Zeuge fuer n) OR (z=50); return (z=50)
Fehler: