Path: illuminati.io.com!uunet!spool.mu.edu!bloom-beacon.mit.edu!pad-thai.cam.
+     ov.com!deep-fried-beagle.cam.ov.com!not-for-mail
From: don@cam.ov.com (Donald T. Davis)
Newsgroups: sci.crypt

Subject: Re: Maurer's Universal Test
Date: 1 Nov 1994 19:33:28 -0500
Organization: OpenVision Technologies, Inc.
Lines: 35
Message-ID: <396moo$28m@deep-fried-beagle.cam.ov.com>
References: 
NNTP-Posting-Host: deep-fried-beagle.cam.ov.com

Steve Allen writes:
>  How universal is Ueli Maurer's Universal Statistical Test For
>Random Bit Generators?
>  Is there a complementary test or set of tests that can give
>analysis that his test can't?
>  A related question: If I run Maurer's Test with wordsize of 16,
>can I gain any insight from running it with wordsize <16?
>
it's universal in the sense that it's an entropy estimator,
and entropy is fundamental in information theory.
in principle, a perfect entropy measurement gives you the real
thing you want to know, which correlation and other statistical
tests only hint at: how much variation does the signal really
contain?

however, an entropy estimate is necessarily a very imperfect
measure, because the longer the strings that the estimator
takes into account, the more sensitive the estimator is to
long-term correlation. so, maurer's estimator is actually
just a performance improvement over a more naive entropy
estimate. to improve his algorithm's performance more, you
should:

   feed lots of data into it, as much as you can get, until
       the estimate stabilizes (as inverse sqrt of #words).
   use as long a wordsize as your memory can manage (virtual
       memory will slow things down greatly), 
   optimize your memory use, by carefully compessing obvious
       redundancy out of your input string.
   get more memory cards.

running the estimator with shorter wordsizes is not useful,
because the longer wordsizes capture all short-term redundancies.

                                                -don davis, boston