Prime number test: How to generate an illegal prime number?

Phil Carmody was a bit more inventive. In the past, the mathematician had often dealt with numbers. He tried to generate prime numbers that were as large as possible. Such is needed, for example, in modern cryptography. This is based on so-called trapdoor functions: mappings that are easy to execute but extremely difficult to reverse – unless you have additional information, a so-called trapdoor. And large primes are great for constructing such functions. One can simply multiply them together, while it is extremely difficult to determine the prime divisors of a number without additional information.

In 2001, however, Carmody did not want to use his research interest to create an encryption – on the contrary: he wanted to create a previously unknown, remarkable prime number that contained the DeCSS code. If the prime number actually had an important property, such as being particularly large, then no court could decide that it should not be published. Thus, DeCSS would be legally visible to everyone – at least in the appearance of the prime number.

So Carmody had to find a way to hide the DeCSS code in a prime number. First he translated the source text into a binary sequence. This most likely does not correspond to a prime number – and even if it did: it probably would not have any property that would justify publishing it. Therefore he used the data compression program »gunzip«, which replaces long strings of bits with shorter ones. Putting the compressed version back into the software gives you the original text, in this case the DeCSS code. But more importantly, if you put eight zeros at the end of the compressed string, gunzip ignores all subsequent characters during decompression. In other words, you can attach all sorts of other digit sequences to the compressed text. As long as they are separated from the rest by eight zeros, the result does not change.

How do you find out if p is a prime number?

So Carmody added the appropriate number of zeros after the compressed version of the DeCSS code and now had to try to create a prime number by appending more digits. In doing so, he benefited from a surprising fact: it is virtually impossible to efficiently determine the prime divisors of a large number. On the other hand, it turns out to be surprisingly easy to determine whether a large number is prime or not.

There are several methods for doing this, one of the oldest being based on Fermat’s little theorem, which the scholar Pierre de Fermat described in a letter to a friend in 1640: If p is a prime number and a any integer, then a^p−1−1 through p divisible. Similar to Fermat’s big theorem, the mathematician didn’t give a proof in this case either, but instead just wrote: “I would send you a proof if I weren’t afraid of straining your attention.”

Fortunately, a proof was not long in coming (in contrast to Fermat’s big theorem, which Andrew Wiles was only able to crack in 1995). Gottfried Wilhelm Leibniz found a solution as early as 1683, but he did not publish it. This proved that Fermat’s little theorem holds for every prime number. So if you have any two natural numbers a and p chooses and turns out that a^p−1−1 not through p is divisible, then is p no prime number. But watch out! The converse is not necessarily true: just because a^p−1−1 through p is divisible, must p not necessarily be a prime number.