Nicht e-mal mit x malnehmen, denn Aufwand wäre O(2500), sondern:
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