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