The genius of this story is that Phil Carmody found a way to just ADD BITS to the end of a zipped, illegal program to make it a large publishable prime number.
Even more brilliant is that if you convert the prime number back to binary (trivial) and unzip it, you get the illegal program. That is amazing.
----------------------------------------
For the curious:
Let "k" be your illegal program zipped in binary, interpreted as a number.
Carmody created a buffer of zeroed-out bytes to the right of "k" to allow for a
free space to search for prime numbers without tampering with the illegal bits
on the left that he still wanted intact. The unzip program will ignore
everything after it anyway (either because of null terminating zeros or because
the file size listed in the header would ignore it).
(illegal bytes) (zero buffer)
| |
v v
|---------------------------||--------------------------------|
kkkkkkkkkkkkkkkkkkkkkkkkkkkkk0000000000000000000000000000000000
He created this "zero buffer" of size "n" bytes by multiplying k by 256^n. You
already know that multiplying a base-10 number by 10^n adds "n" zeros to the
right. Multiplying a base-2 (binary) number by 2^n similarly adds "n" zeros to
the right. This is what "bit-shifting" is. So, multiplying a binary number
by 2^(8n) will add increments of 8 zeros (a zero byte) to the right of the
number. And if you know your rules, 2^(8n) = (2^8)^n = 256^n.
Then, he modified the bits in this zero buffer to make the whole thing a
prime number.
(illegal bytes) (left-over zero buffer) (prime-making bytes)
| | |
v v v
|---------------------------||---------------------------||---|
kkkkkkkkkkkkkkkkkkkkkkkkkkkkk00000000000000000000000000000bbbbb
He didn't do this directly of course. We know from a popular theorem that
there are an infinite number of values of "n" that make (k * n + b) a prime
number, as long as "k" and "b" don't share any factors. He presumed with
high probability that (k * 256^n + b) would hit on that infinite space of
primes, and he was right. He found values of "n" and "b" to match his
illegal "k" value to create a prime.
To relate the equation to the visualization above: "k" is the illegal bytes
in the beginning. "n" is the size of the zero buffer. "b" is the prime-making
bytes.
I'm sorry, but how exactly is this "amazing"? That you can find some bits to append to a number such that it becomes prime is rather obvious, given that there are an infinite number of primes and (probabilistic) primality tests are readily available. As other have pointed out, this is no more interesting than the fact that adding a "1" bit yields an odd number.
And what's the point? Yes, illegal information can be encoded as bits, those bits interpreted as numbers, and then you can apply transformations to those numbers. So what?
The point is that certain large prime numbers (of certain forms) are curated and published in a catalogue because they are notable (in and of themselves). The process you dismiss as trivial allowed Carmody to encode the illegal program as such a prime, and hence have it independently published in said catalogue, where it belongs entirely independently of whether it happens to turn into the illegal program when run through gunzip.
> That you can find some bits to append to a number such that it becomes prime is rather obvious, given that there are an infinite number of primes
That isn't obvious to me because I learned a long time ago about the strange nature of infinity. The infinite space of primes has infinite gaping holes that may very well swallow all numbers of a given form.
But I posted the question to the Math Stack Exchange, and it seems to be correct:
TL;DR:
The genius of this story is that Phil Carmody found a way to just ADD BITS to the end of a zipped, illegal program to make it a large publishable prime number. Even more brilliant is that if you convert the prime number back to binary (trivial) and unzip it, you get the illegal program. That is amazing.
----------------------------------------