Illegal prime

As illegal prime number is called a prime number that can be converted in a known manner in an illegal or illegitimate document. Typically, these documents are source code for programs that circumvent copy protection mechanisms or encryptions and for example, by the DMCA are illegal.

History

In March 2001, Phil Carmody found a 1401 - digit prime number that gives the C source code of the computer program DeCSS, when you decompress their binary representation with gzip. A U.S. court has declared the United States the distribution of DeCSS in accordance with the DMCA illegal. Thus, also this prime could be considered itself as an " illegal prime number " in the United States. However, this has not yet negotiated even in the U.S. court. The number itself is not illegal, of course, but no more than the application of the resulting program in the United States. By Dirichlet's theorem guarantees that there are infinitely many such numbers.

The question arises for all source code and binary programs, as can be in principle compress any string and is a prime number or not.

Various other representations of the DeCSS source code using steganography to embed the program in other elements such as images or sounds.

Background

The protest against the prosecution of Jon Lech Johansen DeCSS co-author and the legal prohibition of the publication of the DeCSS code in the U.S. took many forms. One of them was the representation of illegal code in a form that had intrinsic quality archival value. Since the bits that make up a computer program that also represent a number, the plan was adopted, the DeCSS code to put into a figure that had a special property that they can be archived and made ​​publishable. The primality of a number is a fundamental property that is outside of the regulated area by laws.

The large prime numbers database of the Prime Pages saves the 20 largest known primes of various forms; one of them is the primality proof using the Elliptic Curve Primality Proving algorithm ( ECPP ). If the number found would be big enough, and it was proven with ECPP that she's prim, they would be published.

Discovery

In the "illegal" prime one uses the fact that the program gzip all bytes after a terminated by zero compressed file ignored. Based on a set of possible prime numbers was generated, all of which resulted in the C code of DeCSS, if they have been decompressed. From these figures, several were "possibly prime " identified by the OpenPFGW open source program as, and one of them was proved by Titanix implemented in the software ECPP algorithm as prim. Even as it was discovered these 1401 - digit number was too small to go in the category by ECPP found primes to a notable place. Therefore Carmody was looking for the same scheme another prime with 1905 points. This was the time of their discovery, the tenth largest prime number that was found by ECPP.

Shortly thereafter, Phil Carmody also found a direct " executable " prime number that works gzip without the program.