# Illegale Primzahl

Die Bezeichnung illegale Primzahl wird gelegentlich im Zusammenhang mit Primzahlen verwendet, die eine Information darstellen, deren Besitz oder deren Verbreitung gesetzwidrig ist – beispielsweise ein Computerprogramm, das Kopierschutzmechanismen oder Verschlüsselungen umgeht. Zwar ist jede digitale Information als Zahl repräsentierbar, aber durch die Konstruktion von besonderen Zahlen wie großen Primzahlen kann beispielsweise die Veröffentlichung der Zahl begründet werden. Ob solche Primzahlen tatsächlich als illegal gelten, wurde bislang nicht vor Gericht verhandelt.

## Hintergrund

Seit etwa 1996 wurden kommerzielle Video-DVDs mit einer digitalen Rechteverwaltung, dem Content Scramble System (CSS), verschlüsselt, die das unautorisierte Abspielen und Kopieren verhindern soll. Auf Linux-Betriebssystemen war das Abspielen CSS-verschlüsselter Video-DVDs überhaupt nicht möglich. 1999 entwickelte eine Hackergruppe das Computerprogramm DeCSS, mit dem solche Video-DVDs dekodiert werden können, und stellte es als freie Software zur Verfügung. Es folgten Rechtsstreitigkeiten, bei denen verschiedene Richter in den USA entschieden, dass die Verbreitung dieses Programms aufgrund des Digital Millennium Copyright Act (DMCA) illegal ist.
Dies löste eine Welle der Empörung aus. Der Protest gegen die strafrechtliche Verfolgung des DeCSS-Mitautors Jon Lech Johansen und gegen das gesetzliche Verbot der Veröffentlichung des DeCSS-Codes in den USA nahm viele Formen an. Manche benutzen Steganographie, um das Programm in anderen Elementen wie Bildern oder Tönen einzubetten. Eine andere Protestreaktion war die Suche nach einer Repräsentation des illegalen Codes in einer Form, die intrinsisch archivwürdige Qualität hatte. Da die Bits, aus denen ein Computerprogramm besteht, auch eine Zahl repräsentieren, wurde der Plan gefasst, DeCSS in eine Zahl zu fassen, die eine besondere Eigenschaft hatte, die sie archivierbar und veröffentlichbar machte.
Die Primalität einer Zahl ist eine fundamentale Eigenschaft, die außerhalb des durch Gesetze geregelten Bereichs liegt. Durch Dirichlets Theorem ist garantiert, dass mit einer bestimmten Methode unendlich viele solcher Zahlen gebildet werden können. Die Primzahlen-Datenbank Prime Pages speichert die 20 größten bekannten Primzahlen verschiedener Formen. Eine dieser Formen ist der Primalitätsbeweis unter Verwendung des Elliptic Curve Primality Proving-Algorithmus (ECPP). Wenn die gefundene Zahl groß genug wäre, und mit ECPP bewiesen würde, dass sie prim ist, würde sie in der Datenbank veröffentlicht werden.

## Entdeckung

Im März 2001 konstruierte Phil Carmody eine 1401-stellige Primzahl, die den C-Quellcode von DeCSS ergibt, wenn man ihre binäre Darstellung mit gzip dekomprimiert. Damit könnte diese Primzahl in den USA als eine „illegale Primzahl“ angesehen werden.
Die Suche nach einer solchen Zahl nutzt die Tatsache aus, dass das Programm gzip alle Bytes hinter einer durch Null terminierten komprimierten Datei ignoriert. Daher kann die Datei und damit die sie repräsentierende Zahl durch Anhängen von weiteren Bytes verändert werden, ohne dass sich das auf die dekomprimierte Datei auswirkt. Basierend auf Dirichlets Theorem wurde ein Satz möglicher Primzahlen generiert, die alle den C-Code von DeCSS ergeben, wenn sie dekomprimiert wurden. Von diesen Zahlen wurden mehrere durch das Open-Source-Programm OpenPFGW als „möglicherweise prim“ identifiziert, und eine von ihnen wurde vom in der Titanix-Software implementierten ECPP-Algorithmus als prim bewiesen. Schon als sie entdeckt wurde, war diese 1401-stellige Zahl zu klein, um in der Kategorie durch ECPP gefundene Primzahlen auf einen erwähnenswerten Platz zu gelangen. Deshalb suchte Carmody nach dem gleichen Schema eine weitere Primzahl mit 1905 Stellen. Diese war zur Zeit ihrer Entdeckung die zehntgrößte Primzahl, die durch ECPP gefunden wurde.
Kurz danach fand Phil Carmody auch eine 1811-stellige Primzahl, die ohne das Programm gzip funktioniert und ein auf Linux direkt ausführbares Programm darstellt. Weitere Varianten sind eine 434 Byte lange C-Implementierung, die sich durch geeignete Wahl der Variablennamen direkt als 1045-stellige Primzahl schreiben lässt und eine Primzahl mit 914 Ziffern basierend auf siebenbittiger ASCII-Kodierung.