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: