At 06:26 PM 8/24/00 -0400, Tim May wrote:
>At 3:08 PM -0400 8/24/00, Marcel Popescu wrote:
>>
>>Speaking of which - does anybody have any hints on how to determine the
>>entropy of an input string? [Needed in Yarrow, and so far I don't know how
>>to do it - my implementation multiplies the length of the input string (in
>>bits) with a constant, which is way too "crude".]
>
>
>Easy method: run the string through a standard compression algorithm,
>e.g., Lempel-Ziv. To the extent it compresses, it's not random,
>i.e., it has less entropy per bit than a random string would have.
You could also use Shannon's formula directly to compute informational
quantity. This might work better for short strings.
More appropriate for testing RNG outputs: Ueli Maurer has a
compression-like algorithm which is sensitive to the order of symbols, not
just their frequency, but it needs too much data. The Diehard suite of
tests requires even more, and is the most thorough.
>
>
>There is no general method for determining the entropy of a string.
>To see this, imagine some apparently random string of apparently
>great entropy. A program might much on this N bit string and report
>that there are "0.99N" bits of entropy. Then a person comes along and
>says "No, that apparently random string is actually just the sequence
>of digits on page 42 of the RAND Corporation's "A Million Random
>Digits" book."
>
>In other words, one cannot say that there is not some _compression_
>(shorter description) of a string of bits.
>
>Despite this, a rough measure of the _apparent_ entropy is to run the
>string, or image, or whatever, through a compressor.
>
>
>--Tim May
>
>--
>---------:---------:---------:---------:---------:---------:---------:----
>Timothy C. May | Crypto Anarchy: encryption, digital money,
>ComSec 3DES: 831-728-0152 | anonymous networks, digital pseudonyms, zero
>W.A.S.T.E.: Corralitos, CA | knowledge, reputations, information markets,
>"Cyphernomicon" | black markets, collapse of governments.
>
>
>
