illegal prime
(another Prime Pages' Glossary entries)
The Prime Glossary
Glossary: Prime Pages: Top 5000:
The hardware and software on this system was updated September 4th.  Please let me know of any problem you encounter. <caldwell@utm.edu>

A DVD (Digital Versatile Disk) can store much more information than a CD. For this reason they are often used to store movies. To prevent playing on an "unauthorized" machine, these movies are protected by CSS (Content Scramble System) a proprietary code licensed to DVD player manufacturers.

Soon code to unscamble DVD's appeared on the internet (DoD Speedripper was released in September 1999). The most famous of these is DeCSS ("the DeCSS") released anonymously on 6 October 1999. This code is now available in many forms (see the Gallery linked below). The shortest versions of the code takes well under 600 key strokes.

The Motion Picture Association of America recently sued to stop distribution of this code under the Digital Millennium Copyright Act. Among those named in the suit were T-Shirt producers who had printed the code on shirts. There are interesting First Amendment issues involved in this case. For example, is code a protect form of free speech? The court's Memorandum Order (linked below) provides a nice summary.

So what has this all to do with prime numbers? At first glance: nothing. But everything stored on a computer, including poems, pictures, spreadsheets and programs, are stored as a sequence of binary bits--so they are simply numbers. Phil Carmody decided to make a version of DeCSS which was a prime number.

First Carmody took the original anonymous version of the DeCSS C-code and gzip'ed it (a standard UNIX program for making files smaller).

Suppose we call the resulting number k.

By Dirichlet's theorem on primes in arithmetic progression, we know that for each fixed integer b relatively prime to k, there are infinitely many primes ak+b.

Because gzip files are null terminated (and characters after that are ignored), if we choose a to be a power of 256 larger than b, the resulting number can still be unzipped to get the original file. This means there are infinitely many prime numbers which yield the same code. Phil proved that these include:

  • k*2562+2083 and
  • k*256211+99.
At the time these were found the second was large enough to fit on the list of largest known primes (because of the method of proof).

Later Charles M. Hannum (acting on Carmody's suggestion) found a variant of his short c-code programs, for which the code itself (viewed as a number) is prime. This can be done by renaming variables, without lengthening the program. Since the ASCII characters in the code all fit in the first 128 ASCII characters, he then found another variant which is smaller, using 7-bits per character. There is clearly no end to what could be done! See the Prime Links++ (link below) to view these primes.

The bottom line: If distributing code is illegal, and these numbers contain (or are) the code, doesn't that make these number illegal? What if the number itself was executable code, would that make it an executable prime?

Related pages (outside of this work)




Chris K. Caldwell © 1999-2014 (all rights reserved)