[edolstra]

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]

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]

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