Finde die kleinste illegale (wahrscheinliche) Primzahl

8

Eine illegale Primzahl ist eine Primzahl, die Informationen codiert, deren Besitz illegal ist - insbesondere in einem Fall eine gzip-Datei des Quellcodes von DeCSS , einer Software zum Entschlüsseln kopiergeschützter DVDs.

Ihre Aufgabe besteht aus zwei Phasen:

  1. Erstellen Sie eine Quelldatei, die DeCSS in möglichst wenigen Bytes implementiert. Dies kann in jeder Sprache erfolgen.

  2. Komprimieren Sie diese Quelldatei (unter Verwendung Ihres bevorzugten Komprimierungsalgorithmus) und durchlaufen Sie mögliche Dateien, die auf dieselbe Weise dekomprimiert werden (unter Verwendung des Dirichlet-Theorems, wenn dies hilfreich ist), bis die Primalität erreicht ist.

Da der tatsächliche Nachweis der Primalität viel zu viel Rechenleistung erfordert, reicht es für den zweiten Teil aus, einen " wahrscheinlichen Prim " -Test (z. B. Miller-Rabin ) mit einer Wahrscheinlichkeit von weniger als 2 bis 100 zu bestehen .

Die Person mit der kleinsten wahrscheinlichen Primzahl gewinnt.

code-challenge Joe Z.
quelle
Möglicherweise müssen Sie open("out.gz", 'wb')stattdessen verwenden.
Joe Z.
1
Sie haben fast genau gesagt, was wir tun sollen. Wo ist der Spaß daran, nur Bestellungen zu befolgen?
Ugoren
DeCSS ist eine Herausforderung an sich, die ich in der Sandbox vorgeschlagen habe , obwohl niemand interessiert zu sein scheint. Es ist jedoch nicht trivial genug, um zu überprüfen, ob eine gute Testsuite erforderlich ist . Was den Satz von Dirichlet betrifft: Was hat das mit Dateien zu tun, die auf dasselbe komprimiert werden? Wie viele Komprimierungsdateiformate haben unendlich viele arithmetische Sequenzen, die auf dieselbe Weise dekomprimiert werden?
Peter Taylor
2
@PeterTaylor: Laut Wikipedia-Eintrag (wo ich diese Informationen zuerst erhalten habe) führt das Hinzufügen von nachgestellten Nullzeichen zu einer gzip-Datei dazu, dass beim Dekomprimieren derselbe Code erzeugt wird. Vorausgesetzt, Sie haben eine gültige gzip-Datei, besagt der Satz von Dirichlet, dass Sie schließlich auf eine Primzahl stoßen, indem Sie am Ende Nullzeichen hinzufügen und dann eine Zahl hinzufügen, die für das Ganze relativ prim ist.
Joe Z.
1
Die Implementierung von GNU gibt möglicherweise keinen Fehler aus. In diesem Fall handelt es sich jedoch nicht um einen kompatiblen Dekomprimierer, wie in der Dateiformatspezifikation definiert. Testfälle müssen klein genug sein, um in die Frage eingebettet zu werden, und dürfen nicht das Urheberrecht von Personen verletzen.
Peter Taylor

Antworten:

4

Java (ungefähr 2048 Bit)

14951059135011030015480908520726485619103063818476057564660360628799292628035097139943806440612109515246411930476451010075357954683100898936593739762786721583164361680031433048702186473094092210118641364347032899100220949873928633438856732508590863996147513646363328498023218161000104939462296626885931085914071985322044175133733909287366858309877885352980365735019082872958155754848273583139151810812417879417661663044291630490856568568829579704849173609110647303708828534149066778229242936297219753177569833591637704406031011600073082097633261877649625598598670707453831253888534424016277678136396605413799234576729

Der Code ist

void C(int[]s,int[]k){int a=k[0]^s[84]|256,b=k[1]^s[85],c=k[2]^k[3]<<8^k[4]<<16^s[86]^s[87]<<8^s[88]<<16,d=c&7,e=0,f,i=127;for(c=c*2+8-d;++i<2048;e>>=8){e+=S[f=(c>>17^c>>14^c>>13^c>>5)&255]+T[d=Q[b]^R[a]];b=a/2;a=a&1<<8^d;c=c<<8|f;s[i]=P[s[i]]^e&255;}}//!Y

Ich habe mir erlaubt, die Nachschlagetabellen von CSSt1... CSSt5nach P... Tund die Methode von CSSDescramblenach umzubenennen C. Ich habe auch den gzip-Schritt verworfen, weil er eine größere Datei als die Quelle enthielt.

Peter Taylor
quelle
Übergibt Ballie-PSW. Soll ich auch verstehen, dass Ihr bevorzugter Komprimierungsalgorithmus ist None? ;)
Primo
2
@primo, mein bevorzugter Komprimierungsalgorithmus ist kontextbezogen: derjenige, der das kleinste Ergebnis für die Eingabedaten liefert. ;)
Peter Taylor