Haben wir für eine gegebene Zahl N durch den Miller-Rabin-Test erfahren, daß N wahrscheinlich prim ist, wie können wir darüber Sicherheit erlangen? Es bieten sich zwei Kandidaten für derartige deterministische Tests an: Der eine beruht auf der Theorie der Kreisteilungskörper, der andere benutzt tiefliegende Eigenschaften elliptischer Kurven. Bei den bis heute zur Verfügung stehenden Computern und Implementationen können sie für Zahlen im Bereich von 2000 bis 3000 Dezimalstellen eingesetzt werden.

Wie schnell bzw. wie aufwendig sind diese Verfahren? Der vage Begriff "schnell" läßt sich im Rahmen der Komplexitätstheorie präziser fassen: Eine Methode heißt schnell, wenn sie polynomiale Laufzeit besitzt, d.h. bei großen Zahlen N wird die Laufzeit höchstens mit einer vorgegebenen Konstanten multipliziert, wenn man die Anzahl der Ziffern von N verdoppelt.

Die erwähnte Kreisteilungskörpermethode besitzt keine polynomiale Laufzeit, trotzdem ist die bisher implementierte Version für nicht allzu große Zahlen schnell genug; es können mit ihr Zahlen mit ca. 3000 Dezimalstellen getestet werden.

Wir entwickeln ein Test-Programm, das auf der Theorie der elliptischen

Kurven beruht und polynomiale Laufzeit besitzt.

Heuristsische Überlegungen zeigen, daß die Implementation eine Laufzeit o(n⁴) für n-bit Zahlen haben wird. Dadurch werden wir in die Lage versetzt, Zahlen mit bis zu 6000 Dezimalstellen zu testen.

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.

Viel schwieriger als das Primzahltest-Problem ist es, eine Zahl N in ihre Primfaktoren zu zerlegen. Es gibt (noch) kein Faktorisierungsverfahren mit polynomialer Laufzeit. Diese Tatsache macht man sich in der Kryptographie -mit öffentlichem Schlüssel- zunutze. Überall dort in der elektronischen Datenübertragung, wo Vertraulichkeit unabdingbar ist oder die Urheberschaft eindeutig nachweisbar sein soll, kommen derartige Methoden zum Tragen. Eine der bekanntesten ist das nach Rivest, Shamir und Adleman benannte RSA-Verfahren, das als öffentlichen Schlüssel das Produkt zweier großer Primzahlen p und q verwendet.