Das Ergebnis N=p·q dieser Multiplikation wird für
jedermann zugänglich gemacht. Mit ihm lassen sich Nachrichten chiffrieren.
Um den codierten Text zu entziffern, muß der Empfänger jedoch
die beiden Faktoren p und q kennen. Für einen Unbefugten ist es unmöglich,
sie zu ermitteln. Genauer, hat N=p·q ca. 300 Dezimalstellen und
sind die Primzahlen p und q bekannt, läßt sich die Decodierung
in weniger als einer Sekunde vornehmen. Um eine 300-stellige Zahl N zu
faktorisieren, wäre (im ungünstigsten Fall) mit den derzeit schnellsten
Rechnern mehr Zeit notwendig als das Universums alt ist.
Um Primzahl-Kandidaten für das RSA-Verfahren zu finden, reicht
der erwähnte Miller-Rabin-Test völlig aus. Zahlen mit 200 bis
300 Dezimalstellen werden zufällig ausgewählt und können
- falls sie den probabilistischen Test ca. 20-mal "erfolgreich" bestanden
haben - als Faktoren des öffentlichen Schlüssels verwendet werden.
Worauf beruht die Schnelligkeit unserer Primzahltests? Die Ausführung
der Primzahltests benötigt nur Multiplikationen und Divisionen. Die
Division kann auf die Multiplikation zurückgeführt werden, indem
man die Newton-Approximation zur Berechnung der Reziproken benutzt.
Damit hängt die Geschwindigkeit der Primzahltests nur von der |
Schnelligkeit der Multiplikationen ab.
In einem Projekt "Massiv parallele Rechner in der Computational Number
Theory" entwickelten und implementierten wir Algorithmen für das schnelle
Rechnen für sehr große Zahlen mit bis zu einer Milliarde Binärstellen.
Hierbei stellte sich heraus, daß die Multiplikation, wie wir sie
in der Schule kennengelernt haben, nur für Zahlen mit weniger als
100 Binärstellen optimal ist (jeweils abhängig von der Hardware).
Ein einfacher algebraischer Trick ist die Grundlage für die rekursive
Methode von Karatsuba, die für Zahlen bis zu 10000 Binärstellen
weitaus besser ist. Für noch größere Zahlen sind komplexere
Methoden, die auf der Fast-Fourier-Transformation (FFT) beruhen,
den anderen Verfahren überlegen. Eine Möglichkeit ist die Gleitkomma-FFT,
eine andere die schnelle Multiplikation in Restklassenringen modulo Fermatzahlen,
die mit den Namen Schönhage und Strassen verknüpft ist. Welche
schneller ist, hängt auch hier jeweils von der Hardware ab. In einem
direkten Vergleich, d.h. bezogen auf dieselbe Hardware, mit der bisher
bezüglich schnellen Rechnens mit sehr großen Zahlen weltweit
führenden Arbeitsgruppe von Schönhage (vgl. [
5] ) erzielten wir eine ca. 6,5-fache Geschwindigkeitsverbesserung
für Zahlen mit etwas mehr als 33000 Binärstellen. (Daten für
größere Zahlen liegen in [ 5]
nicht vor.) |