Seit einigen Jahren ist in Mathematikerkreisen bekannt, daß 1164+1) keine Primzahl ist, sondern sich als Produkt zweier kleiner Zahlen darstellen laßt. Doch bis vor wenigen Wochen blieb unklar, welches die beiden Faktoren dieser 67stelligen Zahl sind.
Das Rätsel wurde erst Ende vergangenen Jahres von Mathematikern der Sandia National Laboratories in Albuquerque, Neu-Mexiko, gelöst. Gleichzeitig wurde damit die bislang größte (nicht von vornherein durch Produktbildung erzeugte) Zahl in ihre Faktoren zerlegt. Ein Rekord, der allerdings nicht allzulange Bestand haben dürfte, denn das Sandia-Team arbeitet inzwischen mit seinem Cray-Computer bereits am nächsten Projekt: Aus welchen Faktoren wohl jene 71stellige Zahl bestehen mag, die sich ergibt,
schreibt man einfach 71 Einser nebeneinander. Womit aber natürlich nicht etwa die entsprechende Dualzahl gemeint ist, sondern die "echte", aus 71 Einsern bestehende Dezimalzahl.
Man könnte nun meinen, was die Mathematiker in Albuquerque da tun, sei doch kaum mehr als ein nutzloses Herumspielen mit teurer Hardware und hochqualifizierter Gehirnmasse. Doch weit gefehlt: Hinter all diesen Arbeiten stecken handfeste Interessen, was sich auch daran ablesen läßt, daß es tatsächlich bei Mathematikern so etwas wie eine Liste der "zehn meistgesuchten Zahlen" gibt; zehn Zahlen, zu denen auch die ominöse Einserkette gehört und von denen die Leute in Sandia bislang immerhin schon sechs "identifiziert", sprich in ihre Faktoren zerlegt, haben.
Nebenbei: Diese Arbeiten dokumentieren auch auf besonders augenfällige Weise - und vielleicht deutlicher, als die klassischen Mips- und Flops- Listen es können - den Fortschritt in der Informatik. Denn, so sagen die neumexikanischen Faktorisierer in Albuquerque, noch vor acht Jahren sei es an einem vollen Arbeitstag allenfalls möglich gewesen, eine 40stellige Problemzahl zu zerlegen.
Das Wissen um immer größere Prim- beziehungsweise eben Nicht-Primzahlen ist in den letzten Jahren zusehends bedeutender geworden - und zwar besonders unter dem in neuerer Zeit wieder intensiver diskutierten Aspekt der Datensicherheit. Datensicherheit durch Verschlüsselungstechniken beispielsweise, für deren Einsatz man solche Ziffernbandwürmer benötigt; denn viele Methoden basieren ja gerade darauf, daß es, zumindest dem gemeinen Volke, bis heute praktisch unmöglich ist, Zahlenriesen in ihre Faktoren zu gliedern. Nun, was der Mann auf der Straße nicht kann - die Leute der Sandia-Laboratorien können es inzwischen und niemand weiß genau, was sie nicht unter strenger Geheimhaltung vielleicht noch alles fertiggebracht haben. Und genau diese Fertigkeit im "Knacken" großer und größter Zahlen bewirkt natürlich, daß inzwischen Computersysteme "verwundbar" geworden sind, die noch vor vielleicht einem Jahr als praktisch völlig unzugänglich, als kryptografisch absolut sicher abgeschirmt und gepanzert galten.
Zu neuen Ufern
Der mathematische Fortschritt (und zugleich sicherheitstechnische Rückschritt) wird von Gustavus J. Simmons, einem der Sandia-Experten, auf neuartige Algorithmen zurückgeführt, die auf Arbeiten des Mathematikers Carl Pomerance von der University
of Georgia in Athens aufbauen und deren volle Darstellung hier vielleicht doch ein bißchen zu weit führen würde.
Pomerance, und in seinem Gefolge in Sandia jetzt auch seine Kollegen James A. Davis und Diane B. Holdrige, arbeiten mit einem sogenannten "quadratischen Sieb" und damit auf der Basis eines Verfahrens, das sich in der Praxis gut an die strukturellen Besonderheiten des Cray-Rechners anpassen lassen soll. Wie gut, zeigen ein paar Zahlen: Mit dem neuen A1gorithmus kann man auf der Cray eine 55stellige Zahl in weniger als vier Stunden in ihre Faktoren spalten; davor mußte das Rechenmonster an ihr mehr als 50 Stunden lang knobeln - also gut 13mal so lange.
Das aber ist noch immer nicht die ganze Geschichte. Denn der findige Davis kam bei seinen Studien noch auf ein paar weitere Tricks zur Steigerung der Effizienz des Sieb-Algorithmus und erreichte es schließlich, daß eine 58stellige Zahl, an der die Cray auch mit dem Pomerance-Algorithmus immerhin 8,8 Stunden beschäftigt war, nun binnen 1,8 Stunden nackt und zerlegt auf dem Tisch lag.
Nachdem 55- und 58stellige Zahlen glücklich "geknackt" waren, ging es schließlich an die schon eingangs erwähnte 67stellige Zahl. Doch diese Aufgabe konnte selbst auf der Cray nicht ohne Tricks gelöst werden, denn, so Davis, "mußte man dem Betriebssystem gewissermaßen ein paar Bits klauen", sonst hätte die ganze Aufgabe einfach nicht bewältigt werden können.
Jetzt allerdings wollen Davis und seine Kollegen eine größere Maschine installieren und damit dann neuen Rekorden nachjagen.
Dazu zählt beispielsweise jene Zahl, die als 71 Einser nebeneinander hinzuschreiben ist und von der man bloß weiß, daß es keine Primzahl ist. Hingegen weiß bislang kein Mensch, in welche Faktoren sie sich wohl werde zerlegen lassen.
Nicht nur in Sandia rückt man systematisch immer größeren Zahlenmonstern zu Leibe, auch an der in Purdue University in Lafayette, Indiana, sowie an der University of Georgia arbeiten Gruppen mit ähnlicher Zielsetzung. Die beiden Teams wollen sogar einen Computer speziell für die Faktorenzerlegung großer Zahlen entwickeln und hoffen ihr Kind werde dann beispielsweise eine 78stellige Zahl in rund einem Tag behandeln können. Und im Visier haben sie und andere Gruppen bereits Zahlen mit 100 Stellen: In den 90ern sollte es möglich sein, auch sie in handliche kleine Faktoren zu zerlegen ...
Spätestens dann aber werden Verschlüsselungsexperten sich wieder neue Verfahren ausdenken müssen, Nachrichten in einen unverständlichen Zahlensalat umzuwandeln.