[35463] in cryptography@c2.net mail archive
RE: compressing randomly-generated numbers
daemon@ATHENA.MIT.EDU (Jeremy Hansen)
Fri Aug 11 18:16:42 2006
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Thu, 10 Aug 2006 21:36:25 -0400
From: "Jeremy Hansen" <jhansen@rairtech.com>
To: "Travis H." <solinym@gmail.com>,
"Cryptography" <cryptography@metzdowd.com>
> I was mulling over some old emails about randomly-generated=20
> numbers and realized that if I had an imperfectly random=20
> source (something less than 100% unpredictable), that=20
> compressing the output would compress it to the point where=20
> it was nearly so. Would there be any reason to choose one=20
> algorithm over another for this application?
I see where you're coming from, but take an imperfectly random source
and apply a deterministic function to it, and if I recall correctly, you
still have a imperfectly random output. It would be better to use
something like Von Neumann's unbiasing algorithm (or any of the newer
improvements) to strip out the non-randomness.
=20
> I recall talking to a CS prof once who said that LZW=20
> compression was "optimal", which seemed and still seems=20
> really odd to me because optimal compression would generate a=20
> null output file. So surely he meant asymptotically optimal,=20
> or e-close to optimal, or something like that... anyone know?
He probably meant optimal in the information theoretic sense. If that
was the case, then no, optimal compression will not yield a null-length
output -- it will give you the minimum length output that could
represent your input from among all inputs. Or maybe he didn't ;)
Regards,
Jeremy Hansen, MS, CISSP
Director of Security
RAIR Technologies
Any views or opinions presented in this email are solely those of the
author and do not=20
necessarily represent those of RAIR Technologies, Inc. The individual
author will be
personally liable for any damages or other liability arising from this
email.=20
RAIR Technologies * Brookfield, WI * 262-780-6000 =20
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
