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.
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.
----------------------------------------