An
illegal prime is an illegal number which is also
prime. One of the earliest illegal prime numbers was generated in March 2001 by
Phil Carmody. Its
binary representation corresponds to a
gzip-
compressed version of the
C source code of a
computer program implementing the
DeCSS decryption algorithm, which can be used by a computer to circumvent a DVD's
copy protection. One of them was the representation of the illegal code in a form that had an
intrinsically archivable quality. Since the bits making up a computer program also represent a number, the plan was for the number to have some special property that would make it archivable and publishable (one method was to print it on a T-shirt). The
primality of a number is a fundamental property of
number theory and is therefore not dependent on legal definitions of any particular jurisdiction.
Admissible databases The large prime database of the
PrimePages website records the top 5,000 primes of any form. It also records the top 20 primes of various special forms; one of them is proof of primality using the
elliptic curve primality proving (ECPP)
algorithm. Thus, if the number were large enough and proved prime using ECPP, it would be published. (Technically, prime numbers are proven using ECPP usually because they are not of a special form that allows proof using a simpler method. PrimePages includes a note that "this Top 20 category doesn't fit with the rest and has a strong possibility of being removed in the future.") The
probable prime number database of Henri Lifchitz & Renaud Lifchitz records the top 10,000 probable primes of any form.
Methods of construction Gzip was used in Carmody's original entry because it is null-terminated. In other words, for gzipped data
k, the byte sequence
k || 0x00 ||
b for any byte sequence
b produces the same decompressed result. In numerical terms, it means any
k × 256
n +
b (
b n - 1) would produce the same decompression. This echoes the
Dirichlet's theorem on arithmetic progressions, where it is proven that for coprime integers
b and
k, there are infinitely many primes
ak +
b,
a being a natural number. Hannum later found a way to construct an illegal prime without compression. He started with a short C source file of the DeCSS algorithm and changed variable names to make the binary representation a prime number. program for deCSS. This is an illegal, executable prime. The above discusses ways to generate computer files which work functionally the same while altering bits in a way that may change their primality. Primes are found among candidate altered numbers first using a
probable prime test, then probable primes are certified using the ECPP method. == Other examples ==