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, 2013 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, 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\$ 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.
    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\$ Aug 16, 2013 at 13:03

1 Answer 1


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.

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