6 ms·

Someone explain for us normals.

cml 13y ago
Roughly: 1. The letters and punctuation which comprise a computer program in human-readable form can be translated into a string of numbers. 2. That list of numbers can be looked at as if it were one really large number instead of a list of smaller ones. 3. By being a bit clever about how the original program text was translated into numbers, the resulting very-large-number was made to be prime, i.e. not evenly divisible by any numbers other than itself and one. Prime numbers hold a special place in the hearts of many mathematicians. 4. The social implication of all this is that what would have been illegal (rightly or wrongly) in the form of a computer program entered the public record instead in the form of a large number with mathematical significance.
undershirt 13y ago
---------------------------------------- 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. ---------------------------------------- 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.
- VMG 13y ago
  Thanks a lot. Why isn't this in the WP article?
- edolstra 13y ago
  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?
  - homeomorphic 13y ago
    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.
  - undershirt 13y ago
    > 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: Proof: http://math.stackexchange.com/questions/531043/can-you-make-any-number-prime-by-adding-some-digits-to-the-right http://math.stackexchange.com/questions/531043/can-you-make-...
- traviscj 13y ago
  VMG is right. You should definitely add this to the Wikipedia page! Great stuff.

cml 13y ago

Roughly: 1. The letters and punctuation which comprise a computer program in human-readable form can be translated into a string of numbers. 2. That list of numbers can be looked at as if it were one really large number instead of a list of smaller ones. 3. By being a bit clever about how the original program text was translated into numbers, the resulting very-large-number was made to be prime, i.e. not evenly divisible by any numbers other than itself and one. Prime numbers hold a special place in the hearts of many mathematicians. 4. The social implication of all this is that what would have been illegal (rightly or wrongly) in the form of a computer program entered the public record instead in the form of a large number with mathematical significance.

undershirt 13y ago

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

VMG 13y ago
Thanks a lot. Why isn't this in the WP article?
edolstra 13y ago
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?
- homeomorphic 13y ago
  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.
- undershirt 13y ago
  > 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: Proof: http://math.stackexchange.com/questions/531043/can-you-make-any-number-prime-by-adding-some-digits-to-the-right http://math.stackexchange.com/questions/531043/can-you-make-...
traviscj 13y ago
VMG is right. You should definitely add this to the Wikipedia page! Great stuff.