Der Begriff klingt geradezu absurd: eine illegale Primzahl. Und doch haben Zahlen in der Vergangenheit bereits zu erschreckend vielen juristischen Streitigkeiten geführt. Eines der ältesten und bekanntesten Beispiele ist die »Indiana-Pi-Bill«: Der Arzt und Hobbymathematiker Edward J. Goodwin war 1892 davon überzeugt, eine Methode gefunden zu haben, um aus einem Kreis ein Quadrat mit gleichem Flächeninhalt zu konstruieren – nur mit Lineal und Zirkel bewaffnet. Blöd nur, dass Ferdinand von Lindemann bereits 1882 bewiesen hatte, dass dies unmöglich ist.

Aus Goodwins Ansatz folgte unter anderem, dass Pi den Wert von exakt 3,2 hätte. Neben seinen schrägen Rechenkünsten war Goodwin wohl gut darin, andere Personen auf seine Seite zu ziehen. Denn er überzeugte 1897 den damaligen Vorsitzenden des Repräsentantenhauses von Indiana, einen Gesetzesentwurf einzureichen, um seine »neue mathematische Wahrheit« per Gesetz einzuführen. Im Gegenzug dürfe der Staat Indiana Goodwins Ergebnisse, die er unter Urheberrecht gestellt hatte, kostenfrei verwenden. Unglaublicherweise stimmten alle Abgeordneten für den Entwurf, der sodann an den Senat von Indiana ging. Dank der Intervention des Mathematikers Clarence Abiathar Waldo, der zufälligerweise an diesem Tag an der Sitzung teilnahm, konnte die Abstimmung aber glücklicherweise auf unbestimmte Zeit vertagt werden.

Damit wurde nur knapp verhindert, dass ein US-amerikanischer Bundesstaat per Gesetz den Wert von Pi auf 3,2 festlegt. Doch tatsächlich gibt es auch Beispiele aus jüngerer Vergangenheit, in der sich die Justiz für Zahlen interessierte – und einige sogar als illegal einstufte: Man durfte sie weder abdrucken, noch verbreiten.

Den Kopierschutz von DVDs umgehen

1996 entwickelten die Technologiekonzerne Matsushita und Toshiba ein Verschlüsselungssystem ​​Content Scramble System (CSS), das DVD-Inhalte schützen sollte. Damit wollte man verhindern, dass DVDs ohne Genehmigung kopiert und verbreitet werden. Doch wie sich herausstellte, war CSS sehr einfach zu knacken. Tatsächlich umfasst der »DeCSS«-Code, der die Verschlüsselung außer Kraft setzt, nur wenige Zeilen (inzwischen darf man ihn abdrucken):

Als die ersten DeCSS-Programme online erschienen, leitete die DVD Copy Control Association, die CSS lizensiert hatte, sofort rechtliche Schritte ein – und erhielt Recht: Denn das Verbreiten von Betriebsgeheimnissen (und als solches zählt die Verschlüsselung) ist strafbar. Und das hat weit reichende Folgen. Denn ein Computer übersetzt einen Programmcode in eine Folge von Einsen und Nullen, was nichts anderes als eine binäre Zahl ist. Laut dem Gesetz war also die Verbreitung einer Zahl plötzlich illegal.

Das blieb kein Einzelfall. 2007 veröffentlichte ein Hacker einen Schlüssel des Kopierschutzes Advanced Access Content System (AACS), der sich auf HD-DVDs und Blu-ray-Discs befindet. Das Veröffentlichen der dazugehörigen Zahl (in Dezimaldarstellung lautet sie: 13.256.278.887.989.457.651.018.865.901.401.704.640) war in den USA illegal.

Der PS3-Hack sorgt für Furore

Eines der wohl aufsehenerregendsten Ereignisse dieser Art fand jedoch 2011 statt, als Sony den Hacker George Hotz und die Gruppierung »fail0verflow« verklagte, weil sie die Kopierschutzsysteme der Spielkonsole PlayStation 3 erfolgreich ausgehebelt hatten und ihre Methode online veröffentlichten. Damit war man in der Lage, die teuren Spiele zu vervielfältigen.

Das Technologieunternehmen reagierte prompt und drohte, jeden zu verklagen, der den Hack weiterverbreiten würde. Doch dann schoss es sich selbst ins Aus: Die fiktive Sony-Werbefigur »Kevin Butler« veröffentlichte den illegalen Schlüssel über seinen Twitter-Account. Das Ganze war wohl ein Versehen. Ein User hatte den Sicherheitsschlüssel mit der Provokation »come at me« an Sony geschickt; der Verwalter des Kevin-Butler-Accounts wusste aber offensichtlich nicht, worum es sich handelte. Er reagierte mit der ergänzenden Zeile »Lemme guess… you sank my battleship?« und teilte damit den ursprünglichen Tweet samt Schlüssel mit allen Followern.

Auf der Suche nach einem unanfechtbaren Veröffentlichungsgrund

Aber zurück zum DeCSS-Fall, der es ermöglichte, den Kopierschutz von DVDs zu umgehen. Tatsächlich ist er nicht nur aus juristischer Sicht spannend, sondern auch aus mathematischer: Denn er hat eine aus Sicht der Zahlentheorie interessante Größe hervorgebracht.

Nach Publikwerden des Urteils empörten sich zahlreiche Personen darüber. Ein Rechtsstaat konnte doch nicht ernsthaft das Abdrucken eines so einfachen Programmcodes – von etwas mehr als 20 Zeilen – verbieten. Aber wie sich herausstellte, gab es ein Schlupfloch: Wenn man eine Textpassage oder eine Zahl aus einem Grund veröffentlicht, der vorrangig einem anderen Zweck dient, als den Kopierschutz zu umgehen, dann ist es legal. Einige Schlaumeier druckten den Quelltext von DeCSS daher auf T-Shirts, da dieses ja den vorrangigen Zweck habe, getragen zu werden – doch das sah die Justiz nicht als legitim an.

Phil Carmody war da schon etwas erfinderischer. Der Mathematiker hatte sich in der Vergangenheit häufig mit Zahlen beschäftigt. Er versuchte, möglichst große Primzahlen zu erzeugen. Solche braucht man zum Beispiel in der modernen Kryptografie. Diese basiert nämlich auf so genannten Falltürfunktionen: Abbildungen, die zwar einfach auszuführen sind, aber extrem schwer umzukehren – es sei denn, man besitzt Zusatzinformationen, eine so genannte Falltür. Und große Primzahlen eignen sich prima, um derartige Funktionen zu konstruieren. Man kann sie einfach miteinander multiplizieren, während es extrem schwierig ist, die Primteiler einer Zahl ohne Zusatzinformationen zu bestimmen.

Nun wollte Carmody im Jahr 2001 sein Forschungsinteresse aber nicht nutzen, um eine Verschlüsselung zu erzeugen – im Gegenteil: Er wollte eine bisher unbekannte, bemerkenswerte Primzahl schaffen, in welcher der DeCSS-Code enthalten ist. Wenn die Primzahl tatsächlich eine wichtige Eigenschaft erfüllte, etwa besonders groß war, dann konnte kein Gericht mehr entscheiden, dass man sie nicht veröffentlichen dürfe. Somit wäre DeCSS von allen legal einsehbar – zumindest im Erscheinungsbild der Primzahl.

Carmody musste also einen Weg finden, den DeCSS-Code in einer Primzahl zu verstecken. Zunächst übersetzte er dazu den Quelltext in eine Binärfolge. Diese entspricht höchstwahrscheinlich keiner Primzahl – und selbst wenn: Vermutlich besäße sie keine Eigenschaft, die es rechtfertigen würde, sie zu veröffentlichen. Daher verwendete er das Datenkompressionsprogramm »gunzip«, das lange Bitfolgen durch kürzere ersetzt. Wenn man die komprimierte Version wieder in die Software eingibt, erhält man den Originaltext, in diesem Fall den DeCSS-Code. Aber viel wichtiger, wenn man ans Ende der komprimierten Zeichenkette acht Nullen setzt, ignoriert »gunzip« alle nachfolgenden Zeichen bei der Dekompression. Sprich: Man kann an den komprimierten Text alle möglichen weiteren Ziffernfolgen hängen. Solange sie durch acht Nullen vom Rest separiert sind, ändert sich das Ergebnis nicht.

Wie findet man heraus, ob p eine Primzahl ist?

Also fügte Carmody die entsprechende Anzahl an Nullen hinter die komprimierte Fassung des DeCSS-Codes und musste nun versuchen, durch weitere angehängte Ziffern eine Primzahl zu erzeugen. Dabei kam ihm eine überraschende Tatsache zugute: Es ist zwar so gut wie unmöglich, die Primteiler einer großen Zahl effizient zu bestimmen. Hingegen erweist es sich als erstaunlich einfach, zu bestimmen, ob eine große Zahl eine Primzahl ist oder nicht.

Dafür gibt es gleich mehrere Verfahren, wobei eines der ältesten auf dem kleinen fermatschen Satz beruht, den der Gelehrte Pierre de Fermat 1640 in einen Brief an einen Freund beschrieb: Falls p eine Primzahl ist und a eine beliebige ganze Zahl, dann ist a^p−1−1 durch p teilbar. Ähnlich wie beim großen fermatschen Satz gab der Mathematiker auch in diesem Fall keinen Beweis an, sondern schrieb stattdessen nur: »Ich würde dir ja einen Beweis mitschicken, wenn ich nicht befürchten würde, deine Aufmerksamkeit zu überstrapazieren.«

Glücklicherweise ließ ein Nachweis aber nicht allzu lange auf sich warten (im Gegensatz zum großen fermatschen Satz, den erst Andrew Wiles 1995 knacken konnte). Gottfried Wilhelm Leibniz fand bereits 1683 eine Lösung, die er jedoch nicht veröffentlichte. Damit war belegt, dass für jede Primzahl der kleine fermatsche Satz gilt. Wenn man also zwei beliebige natürliche Zahlen a und p wählt und sich herausstellt, dass a^p−1−1 nicht durch p teilbar ist, dann ist p keine Primzahl. Aber aufgepasst! Die Umkehrung trifft nicht zwangsläufig zu: Nur weil a^p−1−1 durch p teilbar ist, muss p nicht zwangsweise eine Primzahl sein.

Zahlen p, die den kleinen fermatschen Satz erfüllen und keine Primzahl sind, heißen Pseudoprimzahlen. Wie sich herausstellt, gibt es unendlich viele davon – aber sie sind dennoch extrem selten; viel seltener als gewöhnliche Primzahlen.

Hat man also einen Anfangsverdacht, dass p eine Primzahl sein könnte, sollte man testen, ob sie den kleinen fermatschen Satz erfüllt. Falls nein, weiß man mit Sicherheit, dass p keine Primzahl ist, zum Beispiel: für a = 2 und p = 9 ist 2⁸−1 = 255 nicht durch 9 teilbar. Und tatsächlich ist 9, wie wir wissen, keine Primzahl. Wenn p den kleinen fermatschen Satz hingegen erfüllt, stehen die Chancen gut, dass p wirklich eine Primzahl ist – aber sicher ist es nicht. Man muss den Kandidaten daher weiterer Prüfungen unterziehen.

Dafür kann man andere Methoden wie den ​​Solovay-Strassen-Test oder Miller-Rabin-Test verwenden, die dem kleinen fermatschen Satz ähneln. Allerdings erhöhen auch diese nur die Wahrscheinlichkeit dafür, dass p eine Primzahl ist – können das jedoch nicht mit Sicherheit beweisen. Dennoch greift man häufig auf diese Ansätze zurück, da sie nicht allzu viel Rechenzeit in Anspruch nehmen. Auf diese Weise lassen sich schnell zahlreiche Primzahlkandidaten ausräumen.

Es gibt aber auch Verfahren, die eindeutig angeben, ob p Teiler über die Eins und sich selbst hinaus besitzt. Ein verbreitetes Beispiel dafür ist die 2002 entwickelte AKS-Methode, benannt nach den indischen Informatikern Manindra Agrawal, Neeraj Kayal und Nitin Saxena. Wenn man den Verdacht hat, p könnte eine Primzahl sein, bildet man das Polynom: (x−1)^p−(x^p−1), multipliziert alle Terme aus und betrachtet die dabei entstehenden Koeffizienten (also die Zahlen, die als Faktoren von x im Polynom auftreten). Wenn alle Koeffizienten durch p teilbar sind, ist p mit Sicherheit eine Primzahl. Kann man die Koeffizienten hingegen nicht faktorisieren, besitzt p neben 1 und sich selbst zwangsweise weitere Teiler. Zum Beispiel ergibt sich für p = 3: (x−1)³−(x³−1) = x³−3x² +3x−1−(x³−1) = −3x² +3x. Die beiden übrig gebliebenen Koeffizienten, 3 und −3, sind jeweils durch p = 3 teilbar. Somit ist 3 eine Primzahl.

Unter den Top-20-Primzahlen befindet sich eine illegale Zahl

Um aus dem DeCSS-Code eine Primzahl zu erzeugen, nutzte Carmody eine Kombination aus verschiedenen Verfahren. Zunächst hängte er an die komprimierte DeCSS-Version acht Nullen und ergänzte diese Zahl um weitere Ziffern. Das Ergebnis unterzog er Primzahltests: Angefangen mit den schnelleren Verfahren wie dem kleinen fermatschen Satz bis hin zu einem Test, der ebenso präzise ist wie die AKS-Methode, allerdings etwas schneller: dem elliptischen Kurven-Primzahltest (kurz: ECPP). So gelangte er schließlich zu einer Primzahl, die in Dezimalschreibweise 1401 Ziffern besitzt – und erzeugte so die erste illegale Primzahl.

Doch ganz zufrieden war Carmody nicht: Denn außer der Eigenschaft, dass sie illegal war, besaß diese Zahl keine Besonderheit. Sie war nicht groß genug, um herauszustechen. Daher suchte er nach einer größeren Primzahl, die es unter den Top-20 ECPP-Zahlen schaffen sollte. Diese Sammlung enthält die 20 größten Primzahlen, die durch einen ECPP-Test gefunden wurden. Damit gäbe es eine stichhaltige wissenschaftliche Rechtfertigung, den DeCSS-Code zu veröffentlichen. Die US-amerikanische Justiz müsste der Begründung zwangsweise nachgeben.

Also wiederholte Carmody seine Suche, aber dieses Mal hängte er mehr Nullen und andere Zahlen an den DeCSS-Code an. Und nach einiger Rechenzeit gelang es ihm schließlich, eine Primzahl mit 1905 Ziffern zu finden – die bis dahin zehntgrößte Primzahl, die durch ein ECPP-Verfahren gefunden wurde. Damit landete sie wie geplant in der Top-20-Liste – und Carmody hatte einen unanfechtbaren Veröffentlichungsgrund gefunden. Nun kann jeder die von ihm entdeckte Primzahl durch das »gunzip«-Programm laufen lassen, und erhält den DeCSS-Code. Und zwar ganz legal.

Was ist euer Lieblingsmathetheorem? Schreibt es gerne in die Kommentare – und vielleicht ist es schon bald das Thema dieser Kolumne!