Faktorisierung, Primzahlproblem und Evolution

Schon seit Eratosthenes sind Algorithmen bekannt, die eine gegebene Zahl n auf ihre Eigenschaft, prim zu sein, untersuchen und sie, falls dies nicht zutrifft, faktorisieren können. Diese Verfahren - verknüpft mit den Begriffen "Sieb des Eratosthenes" oder "trial division" - sind aber sehr zeitaufwendig. Das spielt bei "kleinen" Zahlen keine zu große Rolle, bei größeren Zahlen sind die Grenzen der Durchführbarkeit aber sehr schnell erreicht. Wir werden dies an einem Beispiel deutlich machen.

Bessere und schnellere Verfahren sind deshalb vonnöten. Auch hierfür können wir die Entwicklung nicht nachzeichnen und verweisen auf das bereits erwähnte Beispiel am Ende des Vortrags. Eingehen möchte ich hier aber zuvor auf zwei andere Aspekte.

Die schnellsten Faktorisierungsmethoden stoßen bald, auch bei Zuhilfenahme der größten Computer, an ihre Grenzen. So würde man z. Zt. für die Faktorisierung einer Zahl n mit etwa 150 Dezimalstellen im ungünstigsten Fall ca. 30 Jahre Rechenzeit benötigen.

Diese Tatsache machen sich neue kryptographische Verfahren, wie etwa das von Rivest, Shamir und Adleman stammende und nach ihnen benannte RSA-Verfahren zunutze. Die Verschlüsselung einer digitalen Nachricht geschieht durch Multiplikationen modulo einer gegebenen Zahl n, die das Produkt aus zwei Primzahlen p und q ist, eine Aufgabe, die sehr schnell erledigt werden kann. Einem möglichen Codebrecher, der eine derartig codierte Nachricht entschlüsseln möchte, stehen alle notwendigen Informationen (auch die Zahl n) zur Verfügung. Er scheitert aber aus zeitlichen Gründen, da zum Decodieren die Primfaktorzerlegung n = pq bekannt sein muß.

Auch bei dem Primzahlproblem ist noch kein schneller Algorithmus bekannt, wobei "schnell" bedeutet, daß bei gegebener Zahl n die Rechenzeit, d.h. die Anzahl der Rechenschritte oder Zeiteinheiten, höchstens eine Konstante multipliziert mit einer Potenz von log n ist. Man spricht dann von einem polynomialen Algorithmus. Doch ändert sich die Lage abrupt, wenn man auf volle Gewißheit verzichtet.

Denn 1976 fand Rabin einen polynomialen Algorithmus, der mit hoher Wahrscheinlichkeit richtig entscheidet, ob eine Zahl n eine Primzahl ist.