Wie kann man feststellen, ob eine sehr große natürliche Zahl mit vielleicht 100 Dezimalstellen eine Primzahl ist? Und wenn nicht, wie kann man ihre Teiler finden? Es ist ein elementarer Satz der Zahlentheorie, daß jede natürliche Zahl in eindeutiger Weise in Primfaktoren zerlegbar ist. In der Praxis ist eine solche Zerlegung jedoch mühsam, denn im wesentlichen ist die gegebene Zahl n der Reihe nach durch jeden denkbaren Primfaktor zu teilen und festzustellen, ob die Division aufgeht. Hat man einen solchen Faktor p gefunden, so gilt n=pm, wobei m das Ergebnis der Division ist. Man notiere sich p für später und versuche nun, m in Faktoren zu zerlegen. Da m kleiner ist als n, ist diese Aufgabe einfacher als die ursprüngliche. Entweder kann man von m wieder einen Primfaktor abspalten und das Ergebnis der Division weiter zerlegen, oder m ist eine Primzahl, womit die Faktorisierungsaufgabe erledigt ist. Der Aufwand für dieses Zahlenzerhacken in gleichsam atomare Bestandteile – vor allem das Durchprobieren – wächst mit zunehmender Größe enorm an. Man kann daher das Produkt zweier sehr großer Primzahlen öffentlich bekanntgeben und trotzdem darauf vertrauen, daß niemand in angemessener Zeit die Faktoren finden wird. Darauf basiert das Prinzip der Kryptographie mit veröffentlichtem Schlüssel (vergleiche „Die Mathematik neuer Verschlüsselungssysteme“ von Martin E. Hellmann, Spektrum der Wissenschaft, Oktober 1979, Seite 92). Trotz dieser prinzipiellen Schwierigkeit hat ein Spiel namens „Minimum“, bei dem es – mit gewissen Abwandlungen – darum geht, große Zahlen um die Wette zu faktorisieren, einen gewissen Reiz. Zusammen mit einigen Freunden habe ich es mir im April 1983 in München ausgedacht; hier wird erstmals darüber berichtet. Zu Beginn wird eine große natürliche Zahl ausgelost. Anfänger wählen zweckmäßig eine zehnstellige Zahl; für Durchschnittsspieler sind 20, für Spitzenspieler 40 bis 60 Stellen angemessen. Jeder Spieler versucht nun, für sich allein und nur mit Bleistift und Papier, von der ausgelosten Zahl aus mit einer Folge spezieller Rechenschritte die Zahl 2 zu erreichen. Als Bedenkzeit kann man je nach Spielstärke eine bis vier Stunden vereinbaren. Wer die Zeit überscheitet oder sich verrechnet, bekommt eine Anzahl von Strafpunkten, die um 2 geringer ist als die letzte erreichte beziehungsweise die letzte richtige Zwischenzahl. Welche Rechenschritte sind erlaubt? Man darf erstens die Zahl in zwei Faktoren (deren keiner eine Primzahl sein muß) zerlegen, den kleineren der beiden Faktoren abspalten und mit dem anderen weiterrechnen. Anders ausgedrückt: Man darf die Zahl n durch eine Zahl dividieren, die Teiler von n und höchstens so groß wie die Wurzel aus n ist. (Wenn einer der Faktoren größer ist als , dann muß der andere kleiner sein, sonst wäre ihr Produkt, das ja n sein soll, größer als .) Mit dem Ergebnis der Division ist weiterzurechnen. Damit das Spiel nicht in das beschriebene endlose Probieren ausartet, gibt es zweitens die Möglichkeit, unterwegs die jeweils erreichte Zahl ein wenig abzufälschen: Man darf, statt zu dividieren, 1 addieren oder subtrahieren. Wer etwa im Verlauf der Rechnung bei 129 angelangt ist, tut gut daran, 1 zu subtrahieren, denn 128 ist eine Zweierpotenz und daher durch eine Folge von Divisionen durch 2 leicht bis auf die Zielzahl zu reduzieren. Allerdings kostet jede Fälschung einen Punkt (sagen wir einen Groschen), während Divisionen gewissermaßen kostenlos sind. Das Ziel des Spiels besteht also nicht darin, in möglichst wenig Rechenschritten bis zur 2 zu gelangen, sondern mit möglichst wenig Fälschungen. Der Spieler mit der niedrigsten Punktzahl hat gewonnen (Bild 1). Offensichtlich kann das Spiel auch unentschieden ausgehen. Was ist eine geschickte Spieltaktik? Man will die jeweils vorliegende Zahl möglichst schnell (und mit möglichst wenig Rechenaufwand) klein machen, ohne allzuviel fälschen zu müssen. Nun sieht man zwar auf den ersten Blick, ob eine Zahl durch 2 oder durch 5 teilbar ist; auch die Teilbarkeit durch 3 ist über die Quersummenregel einfach festzustellen. Trotzdem ist es nicht unbedingt sinnvoll, zunächst durch kleine Faktoren zu dividieren: Wer 992, so oft es geht, durch 2 teilt, landet nach 5 Schritten bei 31; das ist aber eine Primzahl, so daß eine Fälschung unvermeidlich ist. Hätte man jedoch 992 im ersten Schritt durch 31 dividiert, wäre das Ergebnis 32 gewesen, was als Zweierpotenz fälschungsfrei auf 2 zu reduzieren ist. Die Division durch 31 ist für die Zahl 992 gerade noch erlaubt, denn 31 ist kleiner als (ungefähr 31,5). Teilt man jedoch ein einziges Mal durch 2, hat man sich diesen Lösungsweg verbaut, denn (ungefähr 22,3) ist nicht mehr größer als 31. Es scheint daher sinnvoll, in jedem Schritt durch den größten noch erlaubten Primfaktor zu dividieren. Das stimmt jedoch nicht immer; wer 57 durch 3 dividiert, muß hinterher noch mindestens zweimal fälschen, während er nach Subtraktion von 1 durch reines Dividieren zum Ziel kommt. Es ist auch geschickter, 4693 zunächst durch 13 statt durch die (ebenfalls zulässige) 19 zu dividieren. Und wer würde wohl einer Zahl wie 4294967297 auf den ersten Blick ansehen, daß nicht die Division durch 641, sondern die Subtraktion von 1 mit dem Ergebnis die Strategie der Wahl ist?

Der Preis einer Zahl

Das läßt sich noch etwas genauer fassen. Man denke sich einen optimalen Spieler, das heißt einen, der nie mehr Fälschungen begeht als unbedingt erforderlich, und vergleiche dann jeden denkbaren Spielzug mit dem dieses Spielers. „Den“ optimalen Spieler gibt es allerdings nicht, da sehr häufig verschiedene, gleich teure Wege zum Ziel existieren. Aber man kann für jede Zahl n die Anzahl P(n) der mindestens nötigen Fälschungen definieren und im Prinzip auch ausrechnen (Bild 2). P(n) ist sozusagen der Preis, der für die Reduktion von n mindestens zu zahlen ist. (Die Matematiker sprechen nicht vom Preis, sondern vom Wert einer Zahl.) Eine Division ist dann ein guter Spielzug, wenn das Ergebnis den gleichen Preis hat wie die Ausgangszahl, eine Fälschung nur dann, wenn sie den Preis um 1 vermindert, denn sie verursacht ja Kosten in Höhe von einem Punkt. Entsprechend kann man schlechte Züge nach den Mehrkosten klassifizieren, die sie verursachen. Die Division 36:2 beispielsweise ist ein einfacher Fehler, denn P(36)=0, aber P(18)=1. Gleiches gilt für 6–1, denn P(6)=P(5)=1, so daß das Fälschen nichts eingebracht hat. Ein Doppelfehler ist zum Beispiel 20–1, und 73023488 durch die Zweierpotenz zu dividieren ist sogar ein Dreifachfehler. Eine Analyse des Spielverlaufs in Bild 1 zeigt, daß die beiden ersten Züge von A und der erste Zug von B jeweils einfache Fehler waren. Man kann auch, etwa mit einem Computerprogramm, während des Spielverlaufs aus dem Preis der bisher erreichten Zahlen und der Anzahl der bisher begangenen Fälschungen den Spielstand beider Spieler bestimmen.

Die Theorie der billigen und der teuren Zahlen

„Minimum“ wirft einige interessante Fragen auf. Üblicherweise teilt man die natürlichen Zahlen in Primzahlen und zusammengesetzte ein. Hier geht es um eine Einteilung nach dem Preis, in leicht (ohne Fälschung) und weniger leicht reduzierbare Zahlen. Ähnlich wie bei den Primzahlen folgt ihre Verteilung zwar einigen Regeln, es bleibt jedoch ein er-hebliches Maß an Undurchschaubarkeit. Welches sind die Zahlen, die nichts kosten? Man muß durch eine Folge von Divisionen bei der 2 landen, also muß jede Nullpreiszahl gerade sein. Außerdem darf keine der Divisionen im Laufe des Spiels gegen die Wurzelbedingung verstoßen: In jedem Schritt muß der größte in der Zahl enthaltene Primfaktor abspaltbar sein, darf also nicht größer sein als das Produkt aller anderen Faktoren. Wenn man eine Zahl n in Gedanken in Primfaktoren zerlegt und diese in aufsteigender Reihenfolge notiert, dann läuft diese Bedingung darauf hinaus, daß jeder Primfaktor nicht größer sein darf als das Produkt der links von ihm stehenden Primfaktoren: für alle k zwischen 2 und r. Jede Zahl, die diese beiden Bedingungen erfüllt, ist eine Nullpreiszahl. Daraus folgt unter anderem, daß für eine Nullpreiszahl sein muß (sonst wäre sie nicht gerade); außerdem gilt und deshalb , sofern der zweite Primfaktor überhaupt vorhanden ist. Jede Nullpreiszahl außer der Zwei selbst ist also ein Vielfaches von 4. Während die Primzahlen so etwas sind wie die muffigen, ungeselligen, regellosen Einzelgänger im Reich der natürlichen Zahlen, sind die Nullpreiszahlen deren genaues Gegenteil: Sie setzen ihrer Zerlegung in Primfaktoren nicht nur erheblich weniger Widerstand entgegen, sondern diese Faktoren verhalten sich auch noch gesittet in dem Sinne, daß der Anstieg von einem zum nächsten nicht maßlos hoch ist. Außerdem sind Nullpreiszahlen sehr leicht zu konstruieren, denn im Gegensatz zu den Primzahlen zählen sie unendlich viele ihrer Vielfachen zu ihresgleichen. Insbesondere gibt es unendlich viele Nullpreiszahlen: Jede Zweierpotenz ist eine. Von den Primzahlen weiß man zwar ebenfalls, daß es unendlich viele gibt; aber unter den sehr großen Zahlen sind sie immer dünner gesät. Unter den vielstelligen Zahlen ist also nahezu jede zusammengesetzt. Nehmen unter ihnen auch die Nullpreiszahlen überhand? Wir haben mit einem Computerprogramm den Preis sämtlicher Zahlen bis 107 bestimmt. Einige unserer Verfahren ähneln dem Sieb des Eratosthenes für die Auslese von Primzahlen (Spektrum der Wissenschaft, September 1988, Seite 8). Die Auszählung (Bild 3) ergibt, daß der Anteil der Nullpreiszahlen von 33 Prozent unter den Zahlen bis 10 auf klägliche 4 Prozent unter den Zahlen bis 107 immer weiter absinkt, je größere Zahlen man in die Statistik einbezieht. Der Anteil der Zahlen, die einen Groschen kosten, steigt zunächst an und fällt wieder ab; bei den teureren Zahlen ist ein Ende des Anstiegs noch nicht abzusehen. Die große Preisliste liefert noch einige weitere Auskünfte. Bis 107 liegt die größte Lücke zwischen zwei Nullpreiszahlen mit einer Länge von 204 zwischen 9248904 und 9249108; die längste ununterbrochene Kette aus Eingroschenzahlen reicht von 9424801 bis 9424828; für zwei Groschen findet sich die längste Kette zwischen 2824266 und 2824282, für drei Groschen zwischen 1593385 und 1593388. Es gibt bis 10 exp7 nur die drei Viergroschenzahlen 3976733, 8053483 und 9942523. Man kann beliebig lange Ketten aus Eingroschenzahlen angeben: Für haben alle Zahlen zwischen n!+1 und n!+n diese Eigenschaft. (n!, gesprochen n-Fakultät, ist das Produkt aller natürlichen Zahlen von 1 bis n.) Einige weitere Aufschlüsse erhält man, wenn man den Verlauf der Funktion P(n) betrachtet, die für jede natürliche Zahl n deren Preis angibt. Sie kann nicht allzu große Sprünge machen: Die Preise zweier aufeinanderfolgender Zahlen unterscheiden sich um höchstens 1. Ist beispielsweise n eine Zweigroschenzahl, so kann man n+1 für einen Groschen zunächst in n verwandeln und dann der optimalen Strategie für n folgen. So kostet die Reduktion von n+1 drei Groschen; also kann n+1 höchstens eine Dreigroschenzahl sein. Je größer die Zahl n wird, desto mühsamer wird zwar die Rechenarbeit zum Reduzieren; andererseits wächst jedoch die Anzahl der möglichen Züge enorm an, so daß es auch mehr Strategien gibt. Wenn n nicht schon selbst eine Nullpreiszahl ist, kann man sich – zumindest in Gedanken – ihre sämtlichen Teiler anschauen. Die meisten von ihnen werden durch eine Folge von Divisionen unter Beachtung der Wurzelbedingung kostenfrei erreichbar sein. Es genügt, wenn einer dieser zahlreichen Teiler eine Nullpreiszahl zum Nachbarn hat, und schon ist n eine Eingroschenzahl. Man kann auch unendlich viele solcher Zahlen angeben: Jede Potenz von 3 kostet einen Groschen, denn man kann sie in einer Folge von Divisionen durch 3 bis auf 3 reduzieren und dann 1 subtrahieren. Billiger geht es nicht, denn jede Dreierpotenz ist ungerade. Die Anzahl der Zweigroschenzahlen ist ebenfalls unendlich; aber diese Tatsache ist nicht mehr ganz so offensichtlich. Man zeigt zunächst, daß jede Primzahl n (außer 5 selbst), die bei der Division durch 24 den Rest 5 läßt, mindestens zwei Groschen kostet. (Nach dem Satz aus der Zahlentheorie über die arithmetische Primzahlprogression gibt es unendlich viele Primzahlen mit dieser Eigenschaft.) Da n eine Primzahl ist, muß der erste Spielzug bereits eine Fälschung sein. Die daraus hervorgehende Zahl läßt bei der Division durch 24 den Rest 4 oder 6; und Zahlen dieser Art (außer der 4 selbst) können keine Nullpreiszahlen sein. Ist nämlich bei Division durch 24 der Rest 6, so ist die Zahl nicht durch 4 teilbar und schon deswegen keine Nullpreiszahl; ist der Rest dagegen 4, dann weiß man, daß die Zahl weder durch 8 noch durch 3 teilbar ist. Also ist in der Primfaktorzerlegung der nächste Faktor nach 2¥2 weder 2 noch 3, also größer als 4, was der Bedingung über den Anstieg der Primfaktoren widerspricht. Wenn daher eine Primzahl der Form 24k+5 vorliegt, muß man für die erste Fälschung einen Groschen und für den Rest der Reduktion noch mindestens ei-nen weiteren ausgeben. Daraus folgt, daß es unendlich viele Zahlen zum Preise von mindestens zwei Groschen gibt. Könnte es sein, daß unter diesen nur endlich viele genau zwei Groschen kosten und alle anderen teurer sind? Nein; denn dann gäbe es einerseits unendlich viele teure (drei Groschen und mehr) Zahlen; andererseits wissen wir schon, daß es unendlich viele billige (einen Groschen oder gar nichts) gibt. Dann muß es auch unendlich oft vorkommen, daß zwischen zwei billigen Zahlen eine teure liegt oder umgekehrt. Da sich aber der Preis von einer Zahl zur nächsten nur um höchstens einen Groschen ändern kann, muß es jedesmal zwischendurch auch eine Zweigroschenzahl geben. Damit ist zwar gezeigt, daß es unendlich viele Zweigroschenzahlen gibt, aber nicht, wie man sie findet – ein typischer Fall für einen nicht-konstruktiven Existenzbeweis.

Offene Fragen

Bei der Suche nach weiteren Eigenschaften der Preisfunktion gerät man sehr schnell in unwegsames Gelände. Wir haben versucht, uns den 1896 bewiesenen Satz über die asymptotische Häufigkeit der Primzahlen zunutze zu machen: Der Anteil der Primzahlen unter den ersten n natürlichen Zahlen ist ungefähr gleich 1/log(n), wobei mit „log“ der natürliche Logarithmus gemeint ist. Die Übereinstimmung ist um so besser, je größer n ist. Salopp gesagt: Die Primzahlen werden auf die Dauer immer seltener, aber sehr langsam. Aus diesem Satz haben wir Vermutungen für den Anteil der billigen Zahlen bis zu einer gewissen Zahl n hergeleitet, die zwar durch unsere Computerauszählung gestützt werden, aber bislang nicht bewiesen sind. Danach wäre eine sehr große, zufällig herausgegriffene Zahl mit extrem hoher Wahrscheinlichkeit eine Zweigroschenzahl, der Anteil aller anderen Zahlen dagegen wäre verschwindend gering. Es ist auch nicht klar, ob es überhaupt beliebig teure Zahlen gibt. Man weiß gerade noch, daß die kleinste unter den Zahlen, die einen vorgegebenen Preis haben, eine Primzahl sein muß. Wäre sie nämlich zusammengesetzt, könnte man einen (zum Beispiel den kleinsten) Faktor abspalten und erhielte eine Zahl, die mindestens so teuer ist; das widerspricht der Voraussetzung, daß die ursprüngliche Zahl die kleinste zu diesem Preis sein soll. Die kleinste Eingroschenzahl ist 3; für die nächsten Preisstufen sind die kleinsten Vertreter 19, 173 und 3976733. Wir vermuten die kleinste Fünfgroschenzahl in der Größenordnung von und die kleinste Sechsgroschenzahl bei . Wir glauben auch, daß es zu jedem Preis eine Zahl gibt; es ist jedoch durchaus denkbar, daß keine Zahl teurer als beispielsweise sieben Groschen ist. Die kleinste Fünfgroschenzahl (wenn es sie gibt) ist als Primzahl insbesondere ungerade; sie muß von zwei Viergroschenzahlen flankiert sein, die dann ihrerseits gerade sind. Teilt man beide durch 2, so ergeben sich zwei unmittelbar benachbarte Viergroschenzahlen (denn Division durch 2 macht eine Zahl nicht billiger). Da diese aber schon sehr dünn gesät sind, ist es sehr unwahrscheinlich, auch noch zwei benachbarte zu finden; und wenn man die verdoppelt, muß dazwischen noch keine Primzahl liegen. Man darf nicht nur auf das Ergebnis der verschiedenen Vermutungen gespannt sein – darunter etlicher, die in diesem Rahmen nicht diskutiert werden können –, sondern auch darauf, wieviel Zeit bis zu einer Antwort vergehen wird. Die Größenordnung von , in der wir die kleinste Fünfgroschenzahl vermuten, ist mit einem Supercomputer und extrem effizienten Algorithmen bereits am Rande des Erreichbaren.


Aus: Spektrum der Wissenschaft 4 / 1993, Seite 11
© Spektrum der Wissenschaft Verlagsgesellschaft mbH