compressing randomly-generated numbers

Travis H. solinym at
Wed Aug 9 23:44:19 EDT 2006


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?

I recall talking to a CS prof once who said that LZW compression was
"optimal", which seemed and still seems really odd to me because
optimal compression would generate a null output file.  So surely he
meant asymptotically optimal, or e-close to optimal, or something like
that... anyone know?

Obviously I will avoid any fixed-content headers and "magic numbers"
by using a "raw" implementation of the algorithm, not reusing, say,
gzip.  Plus, I will be running as though the RNG was providing me with
an infinitely long string, not reading everything into memory and
trying to compress.

It seems as though the Burroughs-Wheeler Transform (bzip2 et. al.)
gets the best compression of the standard utilities... is it suitable
for infinite length strings?  Is there anything better?
"If you're not part of the solution, you're part of the precipitate."
Unix "guru" for rent or hire -><-
GPG fingerprint: 9D3F 395A DAC5 5CCC 9066  151D 0A6B 4098 0C55 1484

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at

More information about the cryptography mailing list