3 ms·
An analogy: True randomness is uncompressable. If there are patterns, which could lead to compression tricks, it's not random anymore. Primitive runs like 0000
by rurban 6y ago
An analogy: True randomness is uncompressable. If there are patterns, which could lead to compression tricks, it's not random anymore.
Primitive runs like 0000000 are compressible patterns. Other patterns similarly, like 01010101, or 00110001110011. That's why you check generators visually by printing out bitmaps, and ideally by running it through a couple of compressors. Afaik this is not yet done by the 4 most common PRNG testsuites yet, but I'm working on it.
- john_alan 6y agoSo you agree with me, uniformity is important?
- rurban 6y agoYes, but I don't like the abbrevated term that much. I prefer the Kolmogorov complexity, precisely a discrete uniform distribution. It's not only important, it's the only factor.
- Taek 6y agoA run like 0000000 is only compressible if it appears more often than it would in a fully random output. And in a fully random output, we would expect the run '0000000' to appear about once every 16 bytes. When you compress 0000000 to something smaller, you have to replace '0000000' in the plaintext with a smaller symbol in the squash text. Which means if that smaller symbol appears in the plaintext, you have to replace it with a larger symbol in the squash text. And if your smaller symbol appears more frequently than '0000000', you are going to end up with a "squash" text that is larger than the plaintext.