8
\$\begingroup\$

An illegal prime is a prime number which encodes information that is illegal to possess - specifically, in one case, a gzip file of the source code of DeCSS, a piece of software to decrypt copy-protected DVDs.

Your task has two phases:

  1. Build a source file that implements DeCSS in as few bytes as possible. This can be done in any language.

  2. Compress this source file (using your favourite compression algorithm), and iterate through possible files that decompress to the same thing (using Dirichlet's theorem if it helps) until primality is reached.

As actually proving primality may take way too much computing power, it will be enough for the second part to pass a "probable prime" test (e.g. Miller-Rabin) to a probability of less than 2-100.

The person with the smallest probable prime wins.

Improve this question
\$\endgroup\$
12
  • \$\begingroup\$ You may need to use open("out.gz", 'wb') instead. \$\endgroup\$
    – Joe Z.
    Commented Aug 16, 2013 at 5:10
  • 1
    \$\begingroup\$ You said almost exactly what we should do. Where's the fun in just following orders? \$\endgroup\$
    – ugoren
    Commented Aug 16, 2013 at 7:00
  • \$\begingroup\$ DeCSS is sufficient of a challenge in itself that I proposed it in the Sandbox, although no-one seems interested. But it's sufficiently non-trivial to verify that it needs a good test suite. As for Dirichlet's theorem: what does that have to do with files which compress to the same thing? How many compression file formats have infinite arithmetic sequences which decompress to the same thing? \$\endgroup\$
    – Peter Taylor
    Commented Aug 16, 2013 at 7:20
  • 2
    \$\begingroup\$ @PeterTaylor: According to the Wikipedia entry (which is where I got that info in the first place), adding trailing null characters to a gzip file will result in the same code being produced upon decompression. Given that you have a valid gzip file, Dirichlet's theorem states that eventually you'll hit upon a prime number by adding null characters to the end of it and then adding a number that's relatively prime to the whole thing. \$\endgroup\$
    – Joe Z.
    Commented Aug 16, 2013 at 12:36
  • 1
    \$\begingroup\$ GNU's implementation might fail to give an error, but if so then it's not a compliant decompressor as defined in the file format spec. As for test cases, they need to be small enough to embed in the question and shouldn't infringe anyone's copyright. \$\endgroup\$
    – Peter Taylor
    Commented Aug 16, 2013 at 13:03

1 Answer 1

Reset to default
4
\$\begingroup\$

Java (about 2048 bits)

14951059135011030015480908520726485619103063818476057564660360628799292628035097139943806440612109515246411930476451010075357954683100898936593739762786721583164361680031433048702186473094092210118641364347032899100220949873928633438856732508590863996147513646363328498023218161000104939462296626885931085914071985322044175133733909287366858309877885352980365735019082872958155754848273583139151810812417879417661663044291630490856568568829579704849173609110647303708828534149066778229242936297219753177569833591637704406031011600073082097633261877649625598598670707453831253888534424016277678136396605413799234576729

The code is

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

I took the liberty of renaming the lookup tables from CSSt1 ... CSSt5 to P ... T, and the method from CSSDescramble to C. I also ditched the gzip step, because it was giving a larger file than the source.

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Passes Ballie-PSW. Also, am I to understand that your favorite compression algorithm is None? ;) \$\endgroup\$
    – primo
    Commented May 15, 2014 at 9:33
  • 2
    \$\begingroup\$ @primo, my favourite compression algorithm is contextual: the one which gives the smallest result for the input data. ;) \$\endgroup\$
    – Peter Taylor
    Commented May 15, 2014 at 10:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.