John Denker:
>There are profound theoretical reasons to believe it is impossible to
>calculate a useful lower bound on the entropy of a string without knowing
>how it was prepared. There simply *cannot* be an all-purpose statistical
>test.
Quite so. I'd like to see what Maurer's "universal" test
says about the entropy of completely predictable sequences
like the following:
(1) pi
(2) Champernowne's number (0.12345678901011121314151617181920...)
One can show that in Champernowne's number each digit of the base,
and each block of digits of any length, occurs with equal asymptotic
frequency.
One can define, if not successfully run, an actual universal test
for any preparation process simulable by a Turing machine: search
the space of all possible possible ways the string could have
been prepared on a Turing machine, i.e. all the possible programs
shorter than the string. (The lengths of programs specified
in different Turing complete languages are equivalent up to a
constant).
The entropy (Kolmogorov complexity) of the string is the length of
the shortest program (to within that constant). It's not too hard
to see that that (a) this search procedure is uncomputable, and
(b) there is no more comprehensive statistical test possible on a
Turing machine (i.e., the test defined above really is universal
for Turing machines).
One could restrict the search to programs polynomially bounded
in time and space, so that the test is computable, but then one
would still expend at least as much effort to generate
random numbers as the cryptanalyst would need to break them.
The standard reference is Li and Vitanyi, _An Introduction
to Kolmogorov Complexity and its Applications_. Online start
at http://www.cwi.nl/~paulv/kolmogorov.html.
[EMAIL PROTECTED]
http://www.best.com/~szabo/
PGP D4B9 8A17 9B90 BDFF 9699 500F 1068 E27F 6E49 C4A2
