[amelius]

> How is it possible that a government can forbid information?

I think that intent and plausibility play the most important roles here.

Also, if the number of bits you need to describe an illegal prime is of the same order as the number of bits in the prime itself, then you have a weak case.

[John_KZ]

Yep. A prime-based compression algorithm is possible, but if you don't store the whole number, it will take forever to calculate. How are you going to describe it? Are you going to say it's the Nth prime, so go ahead and calculate all (N-1) primes to find it? That's a lot of primes. And by that point it's not any different than sharing data with any other (sane) compression algorithms. Encoding information this way is really cool, but offers no advantages.

[dorgo]

It won't work. There are 37,607,912,018 prime numbers smaller than 1,000,000,000,000. It's 11 decimal digits vs. 13. All the compression comes from the information that it is a prime number.

To point to the "Nth prime" would require almost as many digits as the prime itself. Mabe it's more efficient for very large primes, but I don't think so.

[cormacrelf]

There are a lot of easily describable primes, like the Mersenne primes. A lot of numbers can be described in fewer bits than directly. This is not always the case, but you could just keep looking for another more easily describable prime or broaden the search space to include non-destructive modifications of the data you're representing.

[mikeash]

This is just data compression. Most strings can’t be compressed, and nearly all strings can’t be compressed by more than a small amount.

[dorgo]

>nearly all strings can’t be compressed by more than a small amount.

source?

[mikeash]

https://en.m.wikipedia.org/wiki/Pigeonhole_principle

As you increase length, the number of possible strings grows exponentially. There are only a few (relatively) much smaller strings you can map to.