On Aug 9, 2006, at 8:44 PM, Travis H. wrote:
Hey,
I was mulling over some old emails about randomly-generated numbers
and realized that if I had an imperfectly random source (something
less than 100% unpredictable), that compressing the output would
compress it to the point where it was nearly so. Would there be any
reason to choose one algorithm over another for this application?
This is neither correct nor a good idea.
Taking almost random information and compressing it will lead to less
random results.
Specifically, I will give the general LZW case and then go to the BZ2
case.
1) For LZW (even ignoring the magic numbers), if a byte does not
match anything in the dictionary (it starts with a dictionary of all
0s, so the probability of a match on the first byte is low) then that
byte will get a header of a 0 bit. That byte now becomes 9 bits. The
next byte will have a dictionary of the previous byte and all zeros.
The chance of a match will still be small and putting that into the
dictionary will be a 9 bit field with 0s. So in the first 2 bytes, I
can almost guarantee I know where 2 zero bits are.
2) BZ2 transforms the data and then uses LZW. See 1)....
The correct way to "improve" almost random data is to process it with
a hash like function with compression.
Jim
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
