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.

  • \$\begingroup\$ You may need to use open("out.gz", 'wb') instead. \$\endgroup\$ – Joe Z. Aug 16 '13 at 5:10
  • 1
    \$\begingroup\$ You said almost exactly what we should do. Where's the fun in just following orders? \$\endgroup\$ – ugoren Aug 16 '13 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 Aug 16 '13 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. Aug 16 '13 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 Aug 16 '13 at 13:03

Java (about 2048 bits)


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 | |
  • \$\begingroup\$ Passes Ballie-PSW. Also, am I to understand that your favorite compression algorithm is None? ;) \$\endgroup\$ – primo May 15 '14 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 May 15 '14 at 10:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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