Aufwand: O (log e) , d.h. proportional zur Anzahl der Dezimalstellen.
Algorithmus von Euklid zur Bestimmung des ggt :
Bestimme
ggt((n), d ) und stelle den auftretenden Rest als
Linearkombination von
(n) und d dar.
Beispiel:
Wähle 500 Bit lange ungerade Zahl x .
Teste, ob x, x + 2, x + 4, x + 6,... Primzahl ist.
Sei (x) die Anzahl der Primzahlen unterhalb von x . Es gilt:
(x)
Dichte
mittlerer Abstand
ln x
Also zeigt sich Erfolg beim Testen ungerader Zahlen der Größe
n = 2500 nach etwa
= 86 Versuchen.
Komplexitätsklassen für die Erkennung von Primzahlen:
L
:
es gibt Algorithmus A , der angesetzt auf
die Frage, ob x
L , nach
polynomialer Zeit mit ja oder nein anhält und folgende Gewähr
für die Antwort gilt:
Antwort: ja x ist zusammengesetzt.
Antwort: nein x ist höchstwahrscheinlich prim.
Bei 50 Versuchen Fehler
.
Satz von Rabin:
Sei n = 2k · q + 1 eine Primzahl, x < n
Beispiel:
Sei
n = 97 = 25 · 3 + 1 , sei x = 2.
Definition eines Zeugen:
Sei n = 2k · q + 1 .
Eine Zahl x < n heißt Zeuge für die Zusammengesetztheit von n
Satz von Rabin:
Ist n zusammengesetzt, so gibt es mindestens
n 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:
()50
10- 30