Effizienz des RSA-Verfahrens

Die Effizienz stützt sich auf folgende Überlegungen:

a)

Potenziere mod n

Nicht e-mal mit x malnehmen, denn Aufwand wäre O(2⁵⁰⁰), sondern:

Aufwand: O (log e), d.h. proportional zur Anzahl der Dezimalstellen.

b)

Bestimme e : = d^-1

Algorithmus von Euklid zur Bestimmung des ggt:

Bestimme ggt((n), d ) und stelle den auftretenden Rest als Linearkombination von (n) und d dar.

Beispiel:

c)

Konstruktion einer großen Primzahl

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 = 2⁵⁰⁰ 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 = 2^{k .}q + 1 eine Primzahl, x < n

1): x^q 1 mod n oder
2): x^{q^.2ⁱ} - 1 mod n für ein i {0, ..., k - 1}

Beispiel:

Sei n = 97 = 2^{5 .}3 + 1, sei x = 2.

Definition eines Zeugen:

Sei n = 2^{k .}q + 1.

Eine Zahl x < n heißt Zeuge für die Zusammengesetztheit von n

1): ggt(x, n) 1 oder
2): x^q 1 mod n und x^{q^.2ⁱ} - 1 für alle i {0,..., k - 1}

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: ()⁵⁰ 10^-30