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.)