Die 129stellige Zahl 114 381 625 757 888 867 669 235 779 976 146 612 010 218 296 721 242 362 562 561 842 935 706 935 245 733 897 830 597 123 563 958 705 058 989 075 147 599 290 026 879 543 541 ist Produkt zweier Primzahlen. Wie lauten diese Faktoren?

Diese Frage stellte Martin Gardner den Lesern des Scientific American im August 1977 in seiner Kolumne "Mathematical Recreations". (Sie blieb den Lesern von "Spektrum der Wissenschaft", das die Kolumne unter dem Namen "Mathematische Spielereien" eindeutschte, vorenthalten, denn diese Zeitschrift wurde erst ein Jahr später gegründet.) Im Gegensatz zu den Rätseln, die Gardner sonst aufzugeben pflegte, mußte dieses ungewöhnlich lange auf eine Lösung warten: Erst mehr als 16 Jahre später, im April 1994, präsentierten Paul Leyland von der Universität Oxford, Michael Graff von der Universität von Iowa in Iowa City und Derek Atkins vom Massachusetts Institute of Technology in Cambridge die Faktoren. Sie hatten im Herbst zuvor über das Internet Teile der Aufgabe an etwa 600 Freiwillige vergeben, die dafür ihre Workstations viele Nächte durch laufen ließen. Das Programm stammte von Arjen K. Lenstra vom Zentrum Bell Communications Research in Morristown (New Jersey).

Faktorisieren – das Zerlegen von Zahlen in Primfaktoren – ist jedoch alles andere als eine belanglose Spielerei. Zwei Zahlen miteinander zu multiplizieren, auch wenn jede 65 Stellen hat, fällt nicht schwer: Mit Papier und Bleistift schafft man es mit Geduld und Disziplin vielleicht in einer Stunde, mit einem Computer ist es eine Kleinigkeit. Die Umkehrung dieser Aktion, also aus dem Produkt die Faktoren wieder herauszufinden, ist dagegen extrem aufwendig, selbst mit den schnellsten verfügbaren Rechnern.

Mathematische Operationen mit einer derartigen Asymmetrie – eine Richtung sehr leicht, die andere sehr schwer – wirken wie Falltüren: Es ist viel leichter, in das Loch hineinzufallen als wieder herauszukommen. Sie bilden die Grundlage moderner kryptographischer Systeme, die mit sogenannten Falltürfunktionen arbeiten. Verschlüsseln muß nämlich schnell gehen, aber Entschlüsseln soll praktisch unmöglich sein. Ronald Rivest vom Massachusetts Institute of Technology in Cambridge, Adi Shamir vom Weizmann-Institut in Rehovot (Israel) und Leonard Adleman von der Universität von Südkalifornien in Los Angeles hatten 1978 auf der Grundlage der Faktorisierung das nach ihren Initialen benannte RSA-Verfahren entwickelt (siehe "Die Mathematik neuer Verschlüsselungssysteme" von Martin E. Hellmann, Spektrum der Wissenschaft, Oktober 1979, Seite 92). Auch Martin Gardner hatte mit den Faktoren der genannten 129stelligen Zahl eine (Nonsense-)Nachricht verschlüsselt: "The magic words are squeamish ossifrage."

Wer mit RSA verschlüsselte Nachrichten empfangen will, wählt zwei Primzahlen p und q, also zwei natürliche Zahlen, die nur durch 1 und sich selbst teilbar sind, berechnet deren Produkt n=p×q und veröffentlicht es, hält aber die Faktoren geheim. Zum Verschlüsseln muß man lediglich das Produkt n kennen. Entschlüsseln kann dagegen nur, wer die Primfaktoren p und q weiß. Aber wenn diese mehr als 150 Dezimalstellen haben, würde es selbst mit den besten bekannten Methoden auf einer modernen Workstation mehr als 2000 Jahre dauern, n zu faktorisieren. Faktorisierungsprobleme kann man also leicht erzeugen, aber für hinreichend große Primfaktoren heutzutage nicht in vertretbarer Zeit lösen.

Wird das immer so bleiben, oder wird es einmal wirklich schnelle Faktorisierungsverfahren geben? Um das herauszufinden, veranstaltet die Firma, die RSA vertreibt, einen weltweiten Wettbewerb. Sie veröffentlicht Produkte großer Primzahlen und lobt ein Preisgeld für deren Faktorisierung aus. Die kleinste zur Zeit noch nicht zerlegte RSA-Zahl ist 21 290 246 318 258 757 547 497 882 016 271 517 497 806 703 963 277 216 278 233 383 215 381 949 984 056 495 911 366 573 853 021 918 316 783 107 387 995 317 230 889 569 230 873 441 936 471. Sie hat 140 Dezimalstellen, und für ihre Faktorisierung bekommt man vier Siebtel vom Inhalt eines Geldtopfes, der zur Zeit 10895 Dollar enthält und in den RSA alle drei Monate 1750 Dollar einzahlt. (Die restlichen drei Siebtel bleiben für den Faktorisierer der nächsthöheren RSA-Zahl im Topf.)

Die Idee, möglichst viele Interessierte mit ihrer Denk- und Rechenkapazität auf das Problem anzusetzen, ist durchaus sinnvoll: Es ist nämlich nicht beweisbar, ob Faktorisieren prinzipiell so schwer ist oder ob die Mathematiker vielleicht auf das geschickteste Verfahren nur noch nicht gekommen sind. Das gilt allgemeiner. Man kennt kein Berechnungsproblem, das drei Bedingungen zugleich erfüllt: Es ist rasch zu erzeugen, seine Lösung ist leicht zu verifizieren, und es existiert nachweislich kein schnelles Verfahren zu seiner Lösung.

So gibt es für die Sicherheit von Verschlüsselungsverfahren nur die Erfahrung, daß bisher niemand eine schnelle Methode zur Faktorisierung gefunden hat. Die Anbieter von RSA und ähnlichen Verfahren tun also gut daran, nach solchen Algorithmen zu suchen (und ihre Verfahren dagegen zu schützen), bevor ihnen Gegenspieler aus den Geheimdiensten oder der Unterwelt zuvorkommen.

Das Faktorisierungsproblem hat eine ehrwürdige Tradition. Schon in der Antike haben Mathematiker bewiesen, daß jede natürliche Zahl ein Produkt von Primzahlen ist und daß die Primzahlen, die in diesem Produkt vorkommen, bis auf die Reihenfolge eindeutig bestimmt sind. So ist zum Beispiel 12=2×2×3. Für die weitere Untersuchung der Eigenschaften natürlicher Zahlen war es wichtig, Methoden für diese Primfaktorzerlegung zu finden. Seit der Entwicklung der Computer hat dieses Gebiet enorme Fortschritte gemacht. Darüber werde ich hier berichten. Ich versuche zu erklären, wie moderne Faktorisierungsalgorithmen funktionieren und wie sie sich in der Praxis verhalten. Stellenweise gehe ich so ins Detail, daß Sie einfache Versionen auf ihrem PC ausprobieren können; im WWW steht dafür eine Programmbibliothek namens LiDIA zur Verfügung. Schließlich werde ich Bilanz ziehen und eine subjektive Antwort auf die Frage geben, ob Faktorisieren ein schweres Problem bleibt.

Fermat-Zahlen

Der französische Jurist Pierre de Fermat (1601 bis 1665), der vor allem durch seine erst kürzlich bewiesene Vermutung berühmt geworden ist, glaubte ein Rezept zur Erzeugung beliebig großer Primzahlen gefunden zu haben: Zu einer natürlichen Zahl i berechne man F_i=2⁽²ⁱ⁾+1; die Zahlen F_i heißen heute Fermat-Zahlen. Die ersten unter ihnen sind F₀=2⁽²⁰⁾+1=3, F₁=2⁽²¹⁾+1=5, F₂=2⁽²²⁾+1=17, F₃=257, F₄=65537. Man erkennt sofort, daß die ersten drei Fermat-Zahlen 3, 5 und 17 Primzahlen sind. Das gilt auch für F₃ und F₄. Doch nicht alle F_i sind Primzahlen. Der schweizerische Mathematiker Leonhard Euler (1707 bis 1783) fand 1732 bereits heraus, daß F₅=4294967297=641×670041, also zusammengesetzt ist. Erst 150 Jahre später – 1880 – stellten Landry und Le Lasseur fest, daß F₆=18446744073709551617 Produkt der Primzahlen 274177 und 67280421 310721 ist. Michael A. Morrison und John D. Brillhart (der heute an der Universität von Arizona in Tucson arbeitet) bestimmten 1970 die beiden Primfaktoren von F₇, Richard Brent und John M. Pollard von der Universität Reading (England) zerlegten 1980 die Zahl F₈ und Arjen K. Lenstra, Hendrik W. Lenstra von der Universität von Kalifornien in Berkeley sowie Mark S. Manasse vom Forschungszentrum des Computerherstellers DEC und Pollard 1990 die Zahl F₉ (Spektrum der Wissenschaft, November 1990, Seite 38). Einerseits sieht man an diesen Daten, wie schwierig das Faktorisierungsproblem ist; immerhin hat es bis 1970 gedauert, bis die 39stellige Fermat-Zahl F₇ zerlegt war. Andererseits ist die enorme Weiterentwicklung in jüngster Zeit daran zu erkennen, daß nur 20 Jahre später die 155stellige F₉ faktorisiert wurde. Lange bevor die Faktoren bekannt waren, wußte man allerdings schon, daß F₇, F₈ und F₉ keine Primzahlen sind. Man kann nämlich mit einem speziellen Test festellen, ob eine Zahl zusammengesetzt ist, ohne ihre Faktoren berechnen zu müssen (siehe "Primzahlen im Schnelltest" von Carl Pomerance, Spektrum der Wissenschaft, Februar 1983, Seite 80). Erst wenn man sich so vergewissert hat, daß sich die Mühe lohnt, wird man die aufwendige Faktorisierung in Angriff nehmen.

Ein einfacher Primzahltest

Wie findet man möglichst schnell heraus, ob beispielsweise n=58483 eine Primzahl ist? Eine Möglichkeit ist der sogenannte Fermat-Test. In seiner einfachsten Version überprüft er, ob n ein Teiler von 2^n-1-1 ist. Fermat hat nämlich bewiesen, daß dies für ungerade Primzahlen n (also alle außer 2) immer zutrifft. Zum Beispiel ist 3 ein Teiler von 2^3-1-1=3. Ist n also kein Teiler von 2^n-1-1, kann n keine Primzahl sein. Über ihre Primfaktoren weiß man dadurch aber noch nichts. Beispielsweise erhält man für das triviale Beispiel n=6 die Zahl 2⁵-1=31. Da 6 kein Teiler von 31 ist, ist 6 keine Primzahl. Das hätte man zur Not auch ohne Fermat-Test gewußt. Nehmen wir ein etwas schwierigeres Beispiel. Wenn ich den Test etwa auf 58483 anwenden will, muß ich 2⁵⁸⁴⁸²-1 berechnen und prüfen, ob das Ergebnis durch 58483 teilbar ist. Das würde auf die naive Weise extrem lange dauern; die Zahl 2⁵⁸⁴⁸²-1 hat nämlich 17604 Dezimalstellen. Statt dessen rechnet man mit Kongruenzen [=_K] (Kasten auf dieser Seite) und verwendet einen raffinierten, sehr schnellen Algorithmus: Es ist zu überprüfen, ob 58483 ein Teiler von 2⁵⁸⁴⁸²-1 ist, ob also 2⁵⁸⁴⁸² bei der Division durch 58483 den Rest 1 läßt. Diesen Rest berechnet man nun durch binäre Exponentiation. Zuerst schreibt man die Binärdarstellung des Exponenten hin: 58482=2¹⁵+2¹⁴+2¹³+2¹⁰+2⁶+2⁵+2⁴+2. Also ist 2⁵⁸⁴⁸²=2²×2⁽²⁴⁾×2⁽²⁵⁾×2⁽²⁶⁾×2⁽²¹⁰⁾×2⁽²¹³⁾×2⁽²¹⁴⁾×2⁽²¹⁵⁾. Dann berechnet man der Reihe nach die Reste von 2², 2⁴, 2⁸ und so weiter bei der Division durch 58483, indem man den jeweils vorhergehenden Rest quadriert und das Ergebnis mit Rest durch 58483 teilt (Bild 3). Jetzt braucht man nur noch die Potenzen, die in der Binärzerlegung des Exponenten vorkommen, miteinander zu multiplizieren und nach jeder Multiplikation zu reduzieren, das heißt den Rest bezüglich Division durch 58483 zu bilden. Dadurch bleiben alle Zwischenergebnisse von erträglicher Größe. Man erhält 2⁵⁸⁴⁸²=_K4×7053×34259×42237×34763×53664×5010×10893=_K11669 mod 58483. Also kann 58483 keine Primzahl sein, weil sonst das Ergebnis 1 gewesen wäre. Das Verfahren geht relativ schnell, liefert aber noch nicht die Primfaktorzerlegung von 58483.

Probedivision

Nun geht es darum, n in ein Produkt von zwei echten Teilern zu zerlegen, also solchen, die beide weder gleich 1 noch gleich n sind (die Zahlen 1 und n selbst heißen unechte Teiler von n). Zum Beispiel ist 3 ein echter Teiler von 12. Man untersucht dann, ob die Teiler Primzahlen sind. Wenn nicht, zerlegt man sie ihrerseits, und so weiter, bis alle gefundenen Teiler Primzahlen sind. Zum Beispiel ist 12=3×4. Die 3 ist eine Primzahl. Doch 4 ist zusammengesetzt und muß weiter zerlegt werden. Die Zerlegung ist 4=2×2. Die vollständige Zerlegung von 12 lautet also 12=2×2×3. Der wesentliche Schritt eines Faktorisierungsalgorithmus besteht somit darin, einen echten Teiler einer zusammengesetzten Zahl zu finden. Das nächstliegende Verfahren ist die Probedivision: Man teilt n der Reihe nach durch alle Primzahlen 2, 3, 5, 7, 11, 13, 17,..., bis eine der Divisionen aufgeht. Die Primzahlen speichert man vorher in einer Tabelle. Im Falle von n=58483 stellt man fest, daß die einundfünzigste Primzahl, nämlich 233, ein Teiler von n ist (der andere ist 251). Man muß also 51 Divisionen mit Rest durchführen, um diesen Teiler zu finden. Das ist noch zumutbar. Je größer aber der kleinste Primfaktor p von n ist, desto mehr Divisionen sind erforderlich (Bild 4), und desto größer muß die Primzahltabelle sein, mit der man arbeitet. Probedivision ist mithin nur geeignet, kleine Faktoren zu finden; für große Faktoren braucht man grundsätzlich andere Verfahren.


Elliptische Kurven

Hendrik W. Lenstra hat 1985 ein Verfahren gefunden, das mit elliptischen Kurven arbeitet. Das sind sehr interessante und nützliche mathematische Objekte. Der britische Mathematiker Andrew Wiles verwendete sie an entscheidender Stelle in seinem letztlich geglückten Beweis der Fermatschen Vermutung (Spektrum der Wissenschaft, August 1993, Seite 14). Sie werden auch für Verschlüsselungsverfahren eingesetzt – und eben zur Faktorisierung. Ähnlich wie beim Fermat-Test führt man bei dem Verfahren mit elliptischen Kurven (elliptic curve method, ECM) eine Berechnung aus, die gelingen würde, wenn n eine Primzahl wäre. Weil n aber zusammengesetzt ist – was man zum Beispiel aus einem vorangegangenen Fermat-Test weiß –, kann die Rechnung scheitern. Was bedeutet das? Im Verlauf der Berechnung muß man immer wieder den größten gemeinsamen Teiler (ggT) von n mit anderen Zahlen ausrechnen. Die Rechnung kann nur fortgesetzt werden, wenn der ggT gleich 1 ist, die beiden Zahlen also teilerfremd sind. Anderenfalls hat man einen Teiler von n gefunden und – wenn der Zufall es will – sogar einen echten. Damit ist man am Ziel. Der Zufall spielt bei dieser Methode wirklich mit. Es gibt nämlich sehr viele elliptische Kurven zur Auswahl, an denen man die Berechnungen durchführen kann (Bild 7). Man wählt sich eine nach dem Zufallsprinzip aus. Liefert sie keinen echten Teiler, probiert man die nächste aus. Lenstra konnte zeigen, daß es für jedes zusammengesetzte n Kurven gibt, die einen Teiler liefern. Wie bei der Probedivision hängt die Zeit, die man mit der ECM braucht, um einen Faktor zu finden, von dessen Größe ab. Allerdings sind Faktoren mit bis zu 30 Dezimalstellen in erträglicher Zeit aufzuspüren (Bild 5). Was ist nun eine elliptische Kurve? Zunächst tatsächlich eine Kurve, das heißt eine Menge von Punkten (x,y) in der Ebene, deren Koordinaten eine bestimmte Gleichung erfüllen. Im Falle der elliptischen Kurven ist es die Gleichung y²=x³+ax+b. Dabei müssen die Parameter a und b ganze Zahlen und derart gewählt sein, daß nicht gerade 4a³+27b²=0 ist (Bild 5). Ihrem Namen zum Trotz sind übrigens elliptische Kurven keine Ellipsen; sie haben mit ihnen nur sehr entfernt zu tun. Man spricht auch dann von einer Kurve, wenn die Punktmenge, wie in Bild 6, aus mehreren nicht zusammenhängenden Zweigen besteht. Interessant werden elliptische Kurven dadurch, daß man auf ihnen in einem abstrakten Sinne addieren kann: Zu je zwei Punkten P₁ und P₂ der Kurve findet man durch eine geometrische Konstruktion stets einen dritten, der ebenfalls auf der Kurve liegt und P₁+P₂ genannt wird. Die so definierte Addition folgt den üblichen Regeln: Sie ist assoziativ, kommutativ, es gibt ein neutrales Element, also eines, das, zu einem beliebigen Punkt addiert, diesen nicht verändert, und zu jedem Punkt ein Negatives (Inverses), so daß die Summe beider Punkte aus dem neutralen Element besteht. Eine elliptische Kurve bildet also eine kommutative Gruppe bezüglich dieser Addition. Das Inverse -P eines Kurvenpunktes P ist dessen Spiegelbild an der x-Achse. Die Summe P₁+P₂ zweier Punkte P₁ und P₂ findet man im allgemeinen, indem man die Gerade durch P₁ und P₂ zieht. Sie schneidet die Kurve in einem dritten Punkt Q. Dessen Spiegelbild -Q bezüglich der x-Achse ist die gesuchte Summe P₁+P₂ (Bild 6). In dem Sonderfall P₁=P₂ tritt an die Stelle der Geraden durch P₁ und P₂ die Tangente an die Kurve im Punkt P₁=P₂. Wenn schließlich P₁=-P₂ ist, schneidet die Gerade durch P₁ und P₂ keinen weiteren Punkt der Kurve. Man stellt sich ersatzweise vor, daß die Gerade die Kurve im Unendlichen schneidet. Darum fügt man den Punkten der Kurve noch einen weiteren hinzu, den man sich im Unendlichen denkt, nennt ihn O und setzt P₁-P₁=O. Der Punkt O ist also das Nullelement (neutrale Element) der additiven Gruppe. Die geometrische Definition der Punktaddition kann in Formeln umgesetzt werden. Wenn P₁=(x₁,y₁) und P₂=(x₂,y₂) Punkte der elliptischen Kurve sind, dann gilt ((Formel 1)) In den anderen Fällen berechnet man ((Formel 2, erster Teil)) ((Formel 2, zweiter Teil)) Diese Formeln können nun eine Art Eigenleben gewinnen. Man darf sie anwenden, ohne sich unter x und y Koordinaten von Punkten in der Ebene vorstellen zu müssen. Die Bestandteile der Formeln müssen auch nicht unbedingt, wie bisher, reelle Zahlen sein; es genügt, wenn man mit ihnen addieren, subtrahieren, multiplizieren und dividieren kann. Wir haben beim Rechnen mit Kongruenzen (Kasten auf Seite 83) schon gesehen, daß man mit Divisionsresten addieren, subtrahieren und multiplizieren kann. Genauer: Die Reste bei der Division einer ganzen Zahl durch eine natürliche Zahl n können die Werte 0, 1, 2,... , n-1 annehmen. Man rechnet mit diesen Resten so wie gewohnt; nur wenn das Ergebnis der Rechnung über den Bereich von 0 bis n-1 hinausgeht, dividiert man es durch n und nimmt den Rest. Wenn beispielsweise n=12 ist, dann ist 10+5=3 und 1-2=11, wie man es von den Uhrzeiten gewohnt ist: 5 Stunden nach 10 Uhr ist 3 Uhr, und 2 Stunden vor 1 Uhr ist 11 Uhr. Entsprechend ist 4×5=8. Nur die Division erfordert etwas mehr Aufmerksamkeit. Dividieren ist dasselbe wie Multiplizieren mit dem Kehrwert, und der Kehrwert von x ist das Element y, das die Gleichung xy=1 erfüllt. Für n=12 ist beispielsweise 5 der Kehrwert von 5, denn 5×5=25=_K1 mod 12. Aber einen Kehrwert von 4 gibt es nicht, denn 4y ist immer 4, 8 oder 0 mod 12. Insbesondere ist 4×3=0. Nur wenn n eine Primzahl ist, kann man uneingeschränkt dividieren. Der Kehrwert läßt sich mit einer Modifikation des euklidischen Algorithmus berechnen. Zu der Menge dieser Reste mit den entsprechend umdefinierten Grundrechenarten ist nun ebenfalls eine elliptische Kurve definierbar – ganz abstrakt, aber genauso wie zu den reellen Zahlen. Am einfachsten ist es, wenn der Modul n, das heißt die Zahl, bezüglich der man die Reste bildet, eine Primzahl p ist. Die Parameter a und b der Kurve müssen dann ganze Zahlen zwischen 0 und p-1 sein und die Bedingung 4a³+27b² /=_K 0 mod p erfüllen [/=_K bedeutet nicht Kongruent]. Die Kurve – die mit der landläufigen Vorstellung von einer gekrümmten Linie nichts mehr gemein hat – besteht aus allen Paaren (x, y) von ganzen Zahlen zwischen 0 und p-1, welche die Kongruenz y²=_Kx³+ax+b mod p erfüllen. Zusätzlich gibt es noch den Punkt O. Die Formeln für die Addition bleiben unverändert; man ersetzt nur alle auftretenden Zahlen durch ihre Reste bei der Division durch p. Ein Beispiel: Für p=5, a=1 und b=-1 (=_K4 mod 5) sind P₁=(1,1) und P₂=(2,2) Punkte der elliptischen Kurve. Zur Berechnung von P₃=P₁+P₂ muß man durch 2y₁=4 dividieren. Der Kehrwert von 4 ist 4, denn 4×4=16=_K1 mod 5. Also ist x₃=R(-1-2+1, 5)=3 und y₃=R(-1+1-3, 5)=2. Tatsächlich ist (3, 2) ein Punkt der Kurve. Wieder ist die Menge E(p) der Punkte auf der elliptischen Kurve modulo p eine kommutative Gruppe. Sie hat aber nur endlich viele Elemente. Ihre Anzahl liegt zwischen p-2×SQRT(p)+1 und p+2×SQRT(p)+1. Indem man alle Zahlenpaare, die überhaupt in Frage kommen, durchprobiert, findet man, daß für p=5 die genannte elliptische Kurve E(5) aus den Elementen (3,3), (3,2), (0,3), (0,2), (1,4), (1,1), (2,3), (2,2) und O besteht; sie hat also neun Elemente (Bild 7). Die Grundlage für ECM ist ein Satz des französischen Mathematikers Joseph Louis Lagrange (1736 bis 1813): Wenn man ein Element einer endlichen Gruppe so oft zu sich selbst addiert, wie die Gruppe Elemente hat, dann muß das neutrale Element dabei herauskommen. In unserem Falle: 9 mal ein Element von E(5) ist stets gleich O. (Man schreibt, wie sonst auch üblich, 2P für P+P, 3P für P+P+P und so weiter.) Ich rechne das für P=(1,1) vor. Modulo 5 ist 2P=(2,2), 4P=2×(2P)=(0,2), 8P=2×(4P)=(1,-1), schließlich 9P=8P+P=(1,-1)+(1,1)=O. Man sieht, daß es nicht nötig ist, neunmal P zu addieren. Vielmehr verwendet man denselben Trick wie bei der binären Exponentiation: Man berechnet der Reihe nach 2P, 4P, ..., 2^mP und addiert für das Endergebnis diejenigen Zweierpotenzen zusammen, die man braucht. So hält sich der Rechenaufwand auch dann in Grenzen, wenn an die Stelle der Neun sehr große Zahlen treten. Wie verwendet man nun elliptische Kurven, um Teiler zusammengesetzter Zahlen zu finden? Das will ich am Beispiel n=35 zeigen. Man wählt zuerst eine elliptische Kurve modulo n, das heißt zwei ganze Zahlen a und b mit 4a³+27b² /=_K 0 mod n, und einen Punkt auf der Kurve, also eine Lösung P=(x,y) der Kongruenz y²=_Kx³+ax+b mod n. Für n=35 wähle ich wieder a=1, b=-1, x=1 und y=1. Das ergibt zwar eine elliptische Kurve, aber man kann ihre Punkte nicht immer addieren. Nach den Formeln muß man nämlich einen Kehrwert modulo n bilden, und den gibt es nicht immer, weil n zusammengesetzt ist. Die Idee ist: Man versucht es trotzdem; die Berechnung scheitert, aber die Art des Scheiterns gibt einem die Information, die man eigentlich haben will. Man wählt sich eine natürliche Zahl k – wie, beschreibe ich unten. Im Beispiel nehme ich k=9. Den Punkt P versucht man k-mal zu sich selbst zu addieren, und zwar nach der Methode, die ich oben für E(5) beschrieben habe. Im Beispiel berechne ich das Neunfache von P=(1,1) modulo 35. Es ergibt sich 2P=(2,2), 4P=(0,22), 8P=(16,19). Will man nun 9P=8P+P=(16,-16) +(1,1) berechnen, muß man zuerst l bestimmen und dazu durch 16-1=15 mod 35 dividieren. Das geht aber nicht. Es gibt keinen Kehrwert von 15 mod 35, weil der größte gemeinsame Teiler von 15 und 35 nicht 1, sondern 5 ist. Aber bei dem Versuch, den Kehrwert zu finden, hat man mit dem euklidischen Algorithmus den echten Teiler 5 von 35 gefunden, den man eigentlich haben wollte. Die Berechnung ist nun gerade bei k=9 gescheitert, weil 5 ein Teiler von n ist und 9 die Anzahl der Elemente dieser Realisierung von E(5). Das liegt am Satz von Lagrange. Sie wäre bei jedem Vielfachen von 9 ebenfalls gescheitert. Wenn man etwa nach sechsstelligen Primfaktoren sucht, wählt man die Testzahl k so, daß sie Vielfaches möglichst vieler sechsstelliger Zahlen ist, die ihrerseits nicht allzugroße Primfaktoren haben. Dann hat man eine gute Chance, daß k ein Vielfaches der Elementeanzahl von E(p) ist (die wir nicht kennen). Indem man das k-fache eines Elements von E(n) zu berechnen versucht, testet man die Teilbarkeit von n durch alle diese Primzahlen in einem Aufwasch. Um ein geeignetes k zu finden, wählt man eine Zahl B und berechnet k als Produkt aller Primzahlpotenzen, die nicht größer als B sind. Sucht man zum Beispiel nach Faktoren mit höchstens sechs Dezimalstellen, wählt man B=147. Dann ist k=2⁷×3⁴×5³×7²×11²×13×17×19×...×139. Im allgemeinen hat ECM mit der ersten Kurve keinen Erfolg. Man probiert mehrere Kurven, das heißt mehrere Paare von Parametern a und b. Je größer B ist, desto mehr Kurven muß man durchprobieren (Bild 8). Hat ECM dann immer noch keinen Teiler gefunden, so ist man ziemlich sicher, daß die untersuchte Zahl n in der entsprechenden Größenordung auch keinen Teiler hat. Die Rechenzeit von ECM hängt also hauptsächlich von der Größe des gesuchten Primteilers und kaum von der zu faktorisierenden Zahl ab. Wenn eine Zahl mit 1000 Dezimalstellen einen 20stelligen Teiler hat, kann man ihn mit ECM finden. Andererseits wächst die Rechenzeit beträchtlich mit der Größe des kleinsten Faktors. ECM ist für Faktoren mit bis zu 30 Dezimalstellen geeignet. Der größte bisher mit diesem Verfahren gefundene Primfaktor hat 47 Dezimalstellen und wurde von Peter Montgomery am Zentrum für Mathematik und Informatik (CWI) in Amsterdam entdeckt.

Das quadratische Sieb

Für die Suche nach noch größeren Teilern einer Zahl n verwendet man ein anderes Verfahren. Die Idee ist: Man finde natürliche Zahlen X und Y mit der Eigenschaft, daß n ein Teiler von X²-Y² ist. Nach der dritten binomischen Formel ist nämlich X²-Y²=(X-Y)(X+Y). Die Zahl n muß also in (X-Y)(X+Y) aufgehen. Wenn n nicht selbst Teiler von X-Y oder X+Y ist, muß ein echter Teiler von n in X-Y und ein anderer in X+Y aufgehen. Also ist zum Beispiel der größte gemeinsame Teiler von X-Y und n größer als 1, und so einen hatte man ja gesucht. Wählt man zum Beispiel n=7429, X=227 und Y=210, so ist X²-Y²=7429. Also ist 7429 ein Teiler von X²-Y². Die Zahl 7429 ist aber kein Teiler von X-Y=17 und auch kein Teiler von X+Y=437; das geht gar nicht, sie ist ja größer als die beiden anderen Zahlen. Tatsächlich ist ggT(17,7429)=17 ein echter Teiler von 7429. Wie aber findet man X und Y? Zunächst stellt man ein lineares Gleichungssystem auf; dann bestimmt man X und Y aus den Lösungen dieses Systems. Die Anzahl der Gleichungen hängt von der Größe der zu faktorisierenden Zahl ab; für 120stellige Zahlen ergeben sich ungefähr 245000 Gleichungen für ebensoviele Unbekannte (Bild 9). Anders als bei ECM ist also die Größe der zu faktorisierenden Zahl und nicht die des gesuchten Primfaktors maßgebend für den Rechenaufwand. Man bestimmt zunächst eine Reihe von Quadratzahlen mit zwei Eigenschaften: Sie liegen in der Nähe von n, und ihre Differenz zu n ist bis auf das Vorzeichen ein Produkt kleiner Primzahlen. Für n=7429 wären geeignete Quadratzahlen 83², 87², und 88², denn die Differenzen sind sämtlich Produkte der kleinsten Primzahlen 2, 3, 5 und 7: 83²-7429 =-540 =(-1)×2²×3³×5 87²-7429 = 140 =2²×5×7 88²-7429 = 315 =3²×5×7 Die Zeilen dieser Tabelle heißen Relationen. Wenn man einige dieser Zeilen miteinander multipliziert, addieren sich die Exponenten in der Zerlegung. Ist die Summe der Exponenten jedes Primfaktors gerade, so ist das Produkt ein Quadrat. Beispielsweise ist (87²-7429)×(88²-7429)=2²×3²×5²×7²= (2×3×5×7)²=210². Um X und Y zu finden, braucht man jetzt nur noch die Regeln der Kongruenzrechnung anzuwenden. Danach gilt (87×88)2=_K(87²-7429)×(88²-7429) mod 7429. Also gilt (87×88)2=_K210² mod 7429. Hierin kann man auch noch 87×88 durch seinen Rest bei der Division durch 7429 ersetzen und erhält 227²=_K210² mod 7429, das heißt, 7429 ist ein Teiler von 227²-210². Man kann also X=227 und Y=210 wählen. Diese Werte für X und Y liefern, wie oben gezeigt, den Teiler 17 von 7429. Unter typischerweise sehr vielen Relationen sind also solche auszusuchen, die sich in der dargestellten Weise zu einem Quadrat kombinieren lassen. Zu diesem Zweck stellt man das erwähnte lineare Gleichungssytem auf. Für jede Relation gibt es eine Unbekannte, deren Wert 1 ist, wenn die Relation zur Bildung des Quadrats verwendet wird, und 0 im anderen Fall. Im Beispiel hat das System also drei Unbekannte, nämlich l₁, l₂ und l₃. Das Produkt aller Relationen, die verwendet werden, kann man dann allgemein so schreiben: (((Formel 3))) oder umgeformt unter Verwendung der Potenzgesetze: (((Formel 4))) Die Bedingung, daß dieses Produkt ein Quadrat sein soll und damit alle Exponenten gerade sein müssen, liefert das lineare Gleichungssystem l₁ =_K 0 mod 2 l₁ + l₂ + l₃ =_K 0 mod 2 l₂ + l₃ =_K 0 mod 2. Dabei ist die erste Gleichung für den Faktor -1 zuständig, die zweite für 5 und die dritte für 7. Die Exponenten zu den Faktoren 2 und 3 sind in jedem Falle gerade und benötigen deshalb keine eigene Gleichung. Das Gleichungssystem kann man mit einem üblichen Verfahren, zum Beispiel dem Gaußschen Eliminationsverfahren, lösen, wobei man modulo 2 rechnen muß. Das funktioniert, denn das Eliminationsverfahren besteht nur aus Anwendung der vier Grundrechenarten, und modulo 2 kann man immer dividieren, weil 2 eine Primzahl ist. Als Lösung erhält man l₁=0, l₂=l₃=1 und damit die oben angegebenen Werte für X und Y. Es bleibt zu klären, wie die Relationen selbst gefunden werden. Das geschieht mit Hilfe eines Siebverfahrens, dem der Algorithmus seinen Namen "Quadratisches Sieb" verdankt. Gesucht sind Quadratzahlen, die um n vermindert nur in kleine Primfaktoren zerfallen. Man legt zuerst fest, welche Primzahlen in den Relationen vorkommen dürfen. Im Beispiel sind das 2, 3, 5 und 7. Zur Behandlung des Vorzeichens nimmt man noch die Zahl -1 hinzu. Die Menge dieser Primzahlen heißt Faktorbasis. Als nächstes berechnet man Quadratzahlen, die in der Nähe von n liegen. Man bestimmt dazu die größte ganze Zahl m, die noch unterhalb von SQRT-n liegt. Im Beispiel ist m=86. Quadratzahlen in der Nähe von n sind dann zum Beispiel (m-3)² = 83², (m-2)² = 84², (m-1)²=85², m²=86², (m+1)²=87², (m+2)²=88², ..., also allgemeiner (m+u)², wobei u eine – positive oder negative – ganze Zahl ist, die klein ist im Vergleich zu m. Schließlich legt man das Siebintervall fest, also den Bereich der u, die man bearbeiten will. Die Differenzen der Quadratzahlen zu n (man nennt sie die reduzierten Quadratzahlen) schreibt man in eine Liste (Bild 10). Es sind nun diejenigen reduzierten Quadrate zu bestimmen, deren sämtliche Primfaktoren in der Faktorbasis liegen. Das könnte man mittels Probedivision machen. Schneller geht ein Siebverfahren. Um herauszufinden, welche reduzierten Quadrate durch eine Primzahl p teilbar sind, bestimmt man alle u zwischen 0 und p-1, für die (m+u)²-n durch p teilbar ist. Geht man von diesen u-Werten in Schritten der Länge p nach rechts und links durch die Liste der u, erhält man alle reduzierten Quadrate, die durch p teilbar sind. Im Beispiel ist (m+1)²-n durch 2 teilbar. Also sind auch (m-1)²-n, (m-3)²-n und (m+3)²-n gerade. (Das folgt mit einigen Umrechnungen aus der dritten binomischen Formel.) Diese Zahlen dividiert man so lange durch 2, bis sich eine ungerade Zahl ergibt. Das nennt man das Sieb mit 2, denn es hat eine Verwandtschaft mit dem Sieb des Eratosthenes, dem Standardverfahren für das Auslesen von Primzahlen. Das Sieb mit 3 funktioniert genauso: Man stellt fest, daß m²-n und (m+2)²-n durch 3 teilbar sind. Ausgehend von u=0 und u=2 geht man in Schritten der Länge 3 nach rechts und links und teilt an den entsprechenden Stellen, solange es geht, durch 3. Entsprechend siebt man mit den anderen Primzahlen der Faktorbasis (Bild 8). Überall, wo in der entstehenden Liste am Schluß eine Eins steht, kann man das entsprechende reduzierte Quadrat über der Faktorbasis zerlegen. Die Zerlegung rekonstruiert man durch Probedivision. Hier wurde nur die allereinfachste Version des quadratischen Siebs beschrieben. Die Technik selbst ist deutlich älter als der Computer: Der französische Offizier Eugène Olivier Carissan (1880 bis 1925) hat ein mechanisches Gerät gebaut, mit dem man das Aussieben mit mehreren Primzahlen auf einmal durchführen kann (Bilder 1 und 2). Um eine Zahl mit 100 Dezimalstellen zu zerlegen, muß man noch viele Verbesserungen anbringen. Faktorbasis und Siebintervall werden riesig (Bild 11). Ich gebe noch die Parameter an, die bei der Faktorisierung von RSA-120 verwendet wurden, der 120stelligen Zahl, die RSA zur Faktorisierung ausgeschrieben hatte. Arjen K. Lenstra, B. Dodson von der Lehigh University, Mark S. Manasse und Thomas Denny von der Universität Saarbrücken hatten Mitte 1993 mit der erfolgreichen Faktorisierung dieser Zahl einen Weltrekord erzielt. Die Faktorbasis enthielt 245810 Elemente, und das Gleichungssystem, das am Schluß gelöst werden mußte, hatte 245810 Unbekannte und 252222 Gleichungen. Die Berechnung hätte auf einem einzelnen Rechner etwa 50 Jahre gedauert. Auch die Faktorisierer der eingangs genannten 129stelligen Zahl haben das quadratische Sieb verwendet. Parallelisierung

Außer der Verbesserung der Algorithmen ist der gleichzeitige Einsatz vieler Rechner ein wichtiges Mittel zur Beschleunigung der Faktorisierung. Man kann entweder Parallelrechner verwenden, die aber sehr teuer sind, oder verteilte Systeme, zum Beispiel Netze von Arbeitsplatzrechnern, die ohnehin vorhanden und nachts und am Wochenende oft sehr wenig ausgelastet sind.

In Saarbrücken verwenden wir für ECM und quadratische Siebe ein Netz von 250 Workstations, die überall auf dem Campus stehen. Das System LiPS (Library for parallel systems), das in meiner Saarbrücker Arbeitsgruppe innerhalb eines Projekts des Sonderforschungsbereichs "VLSI-Entwurf und Parallelität" unter der Leitung von Thomas Setz entwickelt wird, erkennt automatisch, wenn einer der Rechner nicht von seinem Hauptnutzer gebraucht wird. Es startet dann zum Beispiel eine Faktorisierung. Will der Hauptnutzer wieder an seinem Rechner arbeiten, legt LiPS das Faktorisierungsprogramm schlafen und weckt es erst wieder auf, sobald der Rechner frei ist. LiPS ist auch dafür zuständig, Berechnungsergebnisse an den Computer zu schicken, der die Resultate auswertet (vergleiche Spektrum der Wissenschaft, Februar 1990, Seite 24).


Perspektiven

Selbst auf unserem verteilten System braucht das quadratische Sieb für die Faktorisierung einer Zahl mit 130 Dezimalstellen mehrere Wochen. Die Rechenzeit verdoppelt sich bei drei zusätzlichen Dezimalstellen. Das liegt daran, daß die reduzierten Quadrate, die gesiebt werden, etwa von der Größe SQRT-n sind. Algorithmen, die auf demselben Prinzip beruhen wie das quadratische Sieb, aber beträchtlich schneller sein sollen, müssen Relationen durch Zerlegung wesentlich kleinerer Zahlen gewinnen. Der einzige Algorithmus, der in dieser Hinsicht dem quadratischen Sieb deutlich überlegen ist, ist das Zahlkörpersieb, das John Pollard erfunden und unter anderem für die Zerlegung der Fermat-Zahl F₉ eingesetzt hat. Mit dem Zahlkörpersieb gelang am 11. April dieses Jahres in einer Gemeinschaftsanstrengung, an der auch unsere Saarbrücker Arbeitsgruppe beteiligt war, die Zerlegung einer 130stelligen Zahl, für die RSA zu diesem Zeitpunkt ein Preisgeld von etwa 6600 Dollar ausgelobt hatte: 1 807 082 088 687 404 805 951 656 164 405 905 566 278 102 516 769 401 349 170 127 021 450 056 662 540 244 048 387 341 127 590 812 303 371 781 887 966 563 182 013 214 880 557. Die Fachleute erwarten, daß ein weiterentwickeltes Zahlkörpersieb in fünf Jahren beliebige Zahlen mit 160 Dezimalstellen faktorisieren kann. Dies ist insofern bedeutsam, als die zusammengesetzten Zahlen, die zur Zeit im RSA-Kryptosystem meist verwendet werden, weniger als 160 Dezimalstellen haben. Solche RSA-Anwendungen werden also bald nicht mehr sicher sein. Ist Faktorisieren natürlicher Zahlen also ein schwieriges Problem? Zur Zeit ja. Noch kann kein Algorithmus der Welt aus dem Produkt zweier Primzahlen mit je 150 Dezimalstellen die Faktoren rekonstruieren. Vorerst bilden solche Produkte also eine gute Basis für die Sicherheit kryptographischer Verfahren. Aber wie geht es weiter? Eines stimmt gewiß nicht, was immer wieder in diesem Zusammenhang zu hören ist: Weil Mathematiker seit Jahrhunderten nach Faktorisierungsalgorithmen suchen und bislang keine wirklich schnellen gefunden haben, müsse man das Problem als schwer ansehen. Erst seit es Computer gibt, werden Algorithmen erfunden, die deren Stärken nutzen; vorher gab es nur Verfahren zur Beschleunigung von Berechnungen mit Stift und Papier. Es gibt keinen Grund anzunehmen, daß der dramatische Fortschritt der letzten zwanzig Jahre schon an seinem Ende angelangt sei. Literaturhinweise

- Factorizations and Primality Testing. Von D. M. Bressoud. Springer, Heidelberg 1989.

– A Course in Computational Algebraic Number Theory. Von H. Cohen. Springer, Heidelberg 1993.

– The Development of the Number Field Sieve. Von Arjen K. Lenstra und Hendrik W. Lenstra Jr. Springer Lecture Notes in Mathematics, Band 1554. Springer, Heidelberg 1993.

– The Book of Prime Number Records. Von P. Ribenboim. Springer, Heidelberg 1989.

– Prime Numbers and Computer Methods for Factorization. Von Hans Riesel. 2. Auflage, Birkhäuser, Basel 1994.

– Die Programmbibliotheken LiDIA und LiPS sind erhältlich über http://www.informatik.th-darmstadt.de/TI/Forschung.


Aus: Spektrum der Wissenschaft 9 / 1996, Seite 80
© Spektrum der Wissenschaft Verlagsgesellschaft mbH