"Illegale" Primzahl?

  • Allgemein

  • HotPi
  • 382 Aufrufe 0 Antworten

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • "Illegale" Primzahl?

    Zahlen, bitte! 48565...29443 – eine "illegale" Primzahl?
    heise online 11.10.2016 13:37 Uhr Volker Zota

    Zahlen können zig Eigenschaften haben. Sie sind beispielsweise gerade, ungerade, defizient, befreundet, superperfekt, reell, irrational ... aber können sie auch illegal sein, nur weil sie zu einem bestimmten Zweck konstruiert wurden?

    Primzahlen spielten bei "Zahlen, bitte!" ja schon das ein oder andere Mal eine Rolle. Diesmal ist die Primzahl 1401 Stellen lang:

    48565078965739782930984189469428613770744208735135 79240196520736 68698513401047237446968797439926117510973777701027 44752804905883 13840375497099879096539552270117121570259746669932 40226834596619 60603485174249773584685188556745702571254749996482 19418465571008 41190862597169479707991520048667099759235960613207 25973797993618 86063169144735883002453369727818139147979555133999 49394882899846 91783610018259789010316019618350343448956870538452 08538045842415 65482488933380474758711283395989685223254460840897 11197712769412 07958624405471613210050064598201769617718094781136 22002723448272 24932325954723468800292777649790614812984042834572 01463489685471 69082354737835661972186224969431622716663939055430 24156473292485 52489912257394665486271404821171381243882177176029 84125524464744 50558346281448833563190272531959043928387376407391 68912579240550 15620889787163375999107887084908159097548019285768 45198859630532 38234905580920329996032344711407760198471635311617 13078576084862 23637028357010496125956818467859653331007701799161 46744725492728 33486916000647585917462781212690073518309241530106 30289329566584 36620008004767789679843820907976198594936463093805 86336721469695 97502796877120572499666698056145338207412031593377 03099491527469 18356593762102220068126798273445760938020304479122 77498091795593 83871210005887666892584487004707725524970604446521 27130404321182 61010359118647666296385849508744849737347686142088 0529443

    Sie ist mathematisch an sich uninteressant, wirft aber eine interessante Frage auf: Kann eine Zahl illegal sein? Interpretiert man die Zahl nämlich als Binärdatei, ergibt sich daraus ein gzip-Datenstrom, der sich entpackt in den CSSdescramble-Quellcode verwandelt. Da dieser gemäß dem US-amerikanischen Digital Millennium Copyright Act (DMCA) verboten ist, müsste also auch die Primzahl selbst illegal sein, oder doch nicht? Diese Frage ist nie gerichtlich geklärt worden, trotzdem gilt die obige Zahlenfolge als vermeintlich erste "illegale Primzahl".

    Die erste "illegale Primzahl"
    Tatsächlich ist niemand zufällig über die pikante Eigenschaft der Zahl gestolpert. Der passionierte Primzahljäger Phil Carmody hat sie bewusst so konstruiert. Die Idee dazu kam ihm im Zusammenhang mit der damals hitzig geführten Debatte des DVD-Prozesses rund um den geknackten Kopierschutz CSS (Content Scramble System). Während andere den Quellcode der DeCSS-Routine in Grafiken und Videos versteckten, wollte Carmody ihn in Form einer Primzahl darstellen, um aufzuzeigen, dass pure Information an sich nicht illegal sein kann.

    Falls langjährige Leser jetzt das Gefühl haben, ein Déjà-vu zu erleben, dann liegen sie richtig. Tatsächlich haben wir in der Meldung "Primzahl entschlüsselt DVD" schon im Jahr 2001 über besagte Primzahl geschrieben, wussten damals aber logischerweise noch nicht, dass sie ein hervorragender Kandidat für das 15 Jahre später eingeführte "Zahlen, bitte!" sein würde.

    Rezept für illegale Primzahlen
    Doch wie hat Carmody das überhaupt angestellt? Der Anfang ist klar: Er komprimpierte den CSSdescramble-Quellcode mit gzip. Das Ergebnis interpretierte er als eine 563 Bytes lange Zahl (im Folgenden k genannt). Danach suchte er nach einer Primzahl, deren erste 563 Bytes damit übereinstimmten. Das könnte man für ein unmögliches Unterfangen halten, doch tatsächlich gibt es nach Dirichlets Primzahlsatz sogar unendlich viele davon, man muss sie nur finden. Da gzip-Dateien nullterminiert sind, lässt sich auch die größere Primzahl mit gunzip dekodieren, der überflüssige Rest nach Byte 563 wird als Datenmüll verworfen ("trailing garbage ignored").

    Ursprünglich wollte Carmody nur ein Byte an die Zahl anhängen, um daraus eine Primzahl zu machen. Das klappt aber nicht.
    Also versuchte er es mit zwei Byte: 65536 × k + n und testete alle ungeraden n zwischen 1 und 65535 mit der Software OpenPFGW auf Primzahlkandidaten (Probable Prime). Diese fütterte wiederum den "Elliptic Curve Primality Proving"-Algorithmus Titanix (heute Primo) von Marcel Martin. Für n = 2083 ergab sich dann die 1401-stellige "illegale Primzahl". Sie ist auf den Prime Pages in der Kategorie "Prime Curios!" verewigt.

    Carmody hatte jedoch ein größeres Ziel: Er wollte eine Primzahl konstruieren, die als eine zu dem Zeitpunkte größten bekannten Primzahlen auf den Prime Pages archiviert werden sollte. Doch dazu brauchte sie weit mehr Stellen. Also wiederholte er die geschilderte Prozedur für größere Zahlen der Form 256(156+m) × k + n wobei er n zwischen den ungeraden Zahlen 1 und 255 sowie m zwischen 0 und 300 variierte. Et voilà: n = 99 und m = 55 lieferten das gewünschte Ergebnis einer 1905-stelligen Primzahl, die es ins Archiv der damals größten Primzahlen schaffte.

    Andere "illegale Primzahlen"
    Wie bereits erwähnt, gibt es nicht nur die von Carmody gefundene Primzahldarstellung des DeCSS-Algorithmus, sondern prinzipiell unendlich viele. Außerdem hat Charles M. Hannum nicht nur die mit 434 Bytes kürzeste C-Implementierung der CSS-Routine entwickelt, sondern konnte diese durch geschickte Wahl der Variablennamen in ASCII-Form (8 Bit) direkt als 1045-stellige Primzahl schreiben, ohne auf gzip zurückgreifen zu müssen:

    20740164606530179036774724675343445215942457052264 32338001975411781
    88084829747321620122526293264236496742367183334923 80349378044503081
    74343015540749132616221164876709167301423560691501 32223401307589934
    33016338787120597927116031729625251765158469259482 07222370869477358
    05771262151080025781772556936203965287920958634864 87778914791330243
    35680359525895180300803788668225357732609996781121 67837691175708530
    42219964814266915997834152839924893721839401442314 71165192957812509
    82205218611880062324913442462806354934547192366279 11839600160902785
    75686470595524566085024995619432953790723608275671 96220731805257986
    09793769839466737699751924542619544015493791818754 64431410391589552
    49092070430176458594507271244658837716521207653258 31889938817129518
    38461103895935581969175481011884584167128360563592 08508103189005325
    14556481782133627458289501766757475484616693926572 33390752605789842
    71246533034800589998308977723886900151456041612338 45242288044962524
    23675118235464525875971882779289237794224444133041 31543100338382572
    9204210277724614216568 215235807791512957

    Die siebenbittige ASCII-Kodierung ergibt sogar eine noch kürzere Primzahl mit 914 Ziffern. Und schließlich hat Carmody selbst noch eine als Intel-Binary ausführbare Primzahl aus Hannums Implementierung gebastelt.


    Quelle: Zahlen, bitte! 48565...29443 – eine "illegale" Primzahl? | heise online