why compression doesn't perfectly even out entropy
Perry E. Metzger
perry at piermont.com
Tue Apr 16 22:24:14 PDT 1996
rick hoselton writes:
> At 10:07 AM 4/16/96 -0400, Perry E. Metzger wrote:
>
> >...Usually, random
> >sequences are non-compressable, but it is possible (though very
> >improbable) for Hamlet to appear out of a random number generator,
> >and it is of course quite compressable...
>
> But even if it came from a completely random source, it would
> still make a bad one-time pad.
No it wouldn't. There is a tiny but nonzero probability that xoring
your one time pad with your text will result in a cyphertext equal to,
say, the Bible. Big deal. If the key is really random, the
cryptanalyst has no way to tell what the underlying text was.
> In the context of "fair coin flips" the text of Hamlet is NOT compressible.
Huh?
There is only one context in which things are compressable or not --
is there a smaller representation for them.
> Because no string is more likely than any other. Any algorithm that could
> compress that string, will, on the average INCREASE the length of
> "fair coin flip" strings it tries to compress.
True enough, but the claim was that a random string has no
representation which is smaller than itself.
.pm
More information about the cypherpunks-legacy
mailing list