Im Reich der Nachrichtendienste und der Spionageabwehr, der toten Briefkästen und der mikroverfilmten Raketenpläne ist die Kryptographie, die Lehre vom Ver- und Entschlüsseln geheimer Botschaften, eines der wichtigsten Werkzeuge. Zu dieser nur wenigen Experten voll zugänglichen Disziplin gehört unter anderem die Vertrautheit mit einer der Grundlagen moderner Verschlüsselungsverfahren: den Primzahlen.
Wenn Nachrichten, Computerprogramme oder wichtige Dokumente heute mit Hilfe der Verschlüsselung vor unbefugtem Lesen oder Benutzen geschützt werden sollen, so werden dabei im allgemeinen schnelle Computer eingesetzt, die auf der Basis vielstelliger Primzahlen arbeiten. Aus solchen Primzahlen wiederum lassen sich - beispielsweise durch Multiplizieren - andere Zahlen noch weitaus größerer Stellenzahl bilden.
Fermat-Zahlen als Dezimalzahlen-Monster
Mit deren Hilfe kann die eigentliche Botschaft so verunstaltet werden, daß später nur noch einer an ihren Gehalt herankommt: jener nämlich, der mindestens eine der Ausgangs-Primzahlen kennt. - Allerdings: Wer über Computer-Leistung extremer Mächtigkeit verfügt, der hat immer noch eine reelle Chance, durch Ausprobieren den richtigen Schlüssel aufzuspüren.
Bei den Versuchen der Mathematiker und Computerexperten, immer größere Zahlen auf ihre Eigenschaft, prim zu sein, abzuklopfen, stehen nun an besonders prominenter Stelle die sogenannten Fermatschen Zahlen. Bei diesen handelt es sich um Zahlen, die - im Gegensatz zu beliebigen Dezimalzahlen-Monstern mit 100 Stellen und mehr - einem ganz besonderen Bildungsgesetz unterliegen. Deshalb werden sie auch von Mathematikern mit hohem Interesse wahrgenommen.
Die Suche nach weiteren Primzahlen
Fermat-Zahlen tragen den Namen des französischen Mathematikers und Physikers Pierre de Fermat, der von 1601 bis 1665 lebte und vermutete, alle Zahlen nach seiner Formel ((2 hoch m) + 1) seien Primzahlen. "m", so die Fermatsche Setzung, müsse hierbei entweder gleich eins sein oder eine ganzzahlige positive Potenz von zwei. Beispiele: zwei, vier, acht, 16, 32, 64, etc. Beginnt man mit m = (2 hoch 0) = 1, so lauten die ersten fünf Fermat-Zahlen:
drei (m = 1),
fünf (m = 2),
17 (m = 4),
257 (m = 8) und
65537 (m = 16). In der Tat sind alle diese, wie von Fermat vermutet, Primzahlen: Sie lassen sich ohne Rest nur durch sich selber beziehungsweise durch eins teilen.
Unsicher wurde die Angelegenheit, als rund ein Jahrhundert nach Fermat der deutsche Mathematiker Leonhard Euler nachweisen konnte, daß schon die nachfolgende - siebenstellige - Fermat-Zahl nicht mehr zu den Primzahlen gehört, Fermats Vermutung also falsch ist. Doch hielt dies Mathematiker in aller Welt nicht davon ab, den Fermatschen Zahlen weiter auf der Fährte zu bleiben. Anfangs mit Papier und Bleistift, heute jedoch mit Computern der höchsten Leistungsklassen, suchen sie nach einer möglichen weiteren Primzahl nach Fermats Formel.
So gelang es nach langen Mühen, 1970 für die achte Fermat-Zahl nachzuweisen, daß sie teilbar ist; und 1981 war die nächste dran: Auch sie läßt sich in Faktoren zerlegen. Doch sollte es dann nochmals neun Jahre dauern, ehe die zehnte Fermat-Zahl ihres Geheimnisses beraubt und als Nicht-Primzahl identifiziert werden konnte.
Bei dieser Zahl, die übrigens stattliche 155 Dezimalstellen umfaßt, gelang die Faktorenzerlegung erst, nachdem Mathematiker eine neuartige und speziell auf Fermat-Zahlen passende Technik der Analyse entwickelt hatten.
Die Connection Machine liefert das Gesamtbild
Zum Ziel kamen die beiden US-Wissenschaftler Arjen Lenstra und Mark Manasse erst, nachdem sie eine ganze Reihe einzelner, getrennt installierter Computer gleichzeitig mit der Faktorensuche beschäftigt hatten. Jedoch auch diese Standard-Rechner reichten allein noch nicht aus, dem Ziffernwurm aus Fermats Zahlenwelt zu Leibe zu rücken: Es bedurfte eines massiv parallelen Computers, der Connection Machine, ehe sich das Gesamtbild aus allen Teilinformationen herauskristallisiert hatte.
Dieses Bild sieht nun so aus, daß die zehnte Fermat-Zahl mit (m = 512) in drei Faktoren zu sieben, 49 und 99 Ziffern zerfällt, wobei der kleinste dieser Faktoren die Zahl 2 424 833 ist; die beiden größeren Faktoren weisen jeweils an erster und letzter Stelle eine Sieben auf.
Nachdem die Faktorenzerlegung der 155stelligen Fermat-Zahl Nummer zehn nun gelungen und sicherlich von Kryptologen aller Herren Länder mit Interesse verfolgt worden ist, können die einschlägig interessierten Mathematiker an die elfte Fermat-Zahl gehen. Diese ist - soviel ist klar - eine Zahl mit über 300 Dezimalstellen. Ansonsten umgibt sie erneut die Aura des Geheimnisvollen: Ob sie prim ist oder nicht, weiß bis heute kein Mensch.
Transatlantische Rechenoperation
Es dürfte wohl noch einige Zeit dauern, bis die Computertechnik auch dieses Monster wir sprechen hier von ((2 hoch 1024) -1) besiegt haben wird. Vorerst sehen Experten keinen Weg, diese Zahl in halbwegs überschaubarer Zeit in ihre Faktoren zu zerlegen - wenn es solche überhaupt gibt ...
Ähnlich wie beim Faktorisieren der zehnten Fermat-Zahl ein ganzes Netz von Computern koordiniert an Teilproblemen arbeitete, ehe man das Resultat hatte, knebelten auch vor rund zwei Jahren fast ein Dutzend Rechner in den USA, in Holland und in Australien 26 Tage lang gemeinsam, ehe sie herausgefunden hatten: Eine bestimme, 99stellige Zahl ist nicht prim, sondern das Produkt einer 41stelligen und einer 60stelligen Primzahl. Dabei wurde übrigens nach einer Methode vorgegangen, die Carl Pomerance 1981 an der Universität Georgia in Athens vorgestellt hatte, und die als "Quadratisches Sieb" bekannt wurde. Pomerance ging indirekt vor: Er suchte nicht unmittelbar nach den Faktoren der fraglichen Zahl; statt dessen versuchte er, ausgewählte kleinere Zahlen zu zerlegen.
Spezialrechner für Faktorenzerlegung
Doch nicht allein mit algorithmischen Innovationen pflegen Zahlen-Freaks immer größeren Monstern zu Leibe zu rücken; auch mit speziellen Maschinen wollen Experten wie Pomerance weiterkommen. Er arbeitet an einem Spezialrechner für die Faktorenzerlegung, der zwar nur an die 18 000 Dollar kosten, aber relativ rasch mit 100stelligen Zahlen vorankommen soll, oder sogar mit 200stelligen, erweitert man das Spezialrechner-Konzept in die Zukunft. Diese Zahlenriesen wären um ein Milliardenfaches größer als selbst die Fermat-Zahl Nummer zehn ...