Newsgroups: sci.crypt Path: cactus.org!news.dell.com!swrinde!howland.reston.ans.net!ix.netcom.com! + netcom.com!netcom11!mjohnson From: mjohnson@netcom11.netcom.com (Mark Johnson) Subject: Re: Maurer's Universal Test In-Reply-To: stevalln@dorsai.org's message of Mon, 31 Oct 1994 15:04:02 GMT Message-ID:Sender: mjohnson@netcom.com (Mark Johnson) Organization: Netcom, where Usenet costs only 19 dollars a month References: Date: Tue, 1 Nov 1994 14:45:45 GMT Lines: 50 In article stevalln@dorsai.org (Steve Allen) writes: > > How universal is Ueli Maurer's Universal Statistical Test For > Random Bit Generators? > Regrettably, Maurer's test does not reject the infamous RANDU algorithm. This algorithm is singled out for special scorn and abuse in Knuth's Volume 2 (section 3.3.4, page 104 of the 2nd edition): " ... its very name RANDU is enough to bring dismay into the eyes and stomachs of many computer scientists. ... the generator fails most three dimensional criteria for randomness and it should never have been used." The RANDU algorithm is a linear congruential, defined thus X[n+1] = (65539 * X[n]) mod 2^31 Maurer's test doesn't reject RANDU because of a regrettable deficiency in modern computers: they're just not big enough and fast enough to run his testing program. His problem can be found at the top of page 416 ("A Universal Statistical Test for Random Bit Generators", proceedings of Crypto 90, pp. 409-420). "The test can be implemented by using a table (denoted below as TAB) of size 2^L that stores for each L-bit block the time index of its most recent occurrence." Unfortunately for Maurer, RANDU has L=31, so he's building and using an array of 2^31 elements. The third for-loop of his test algorithm, ("for n:= ...") performs a total of 10000 * (2^L) iterations. This takes a long time :-). Equally unfortunately, other generators (e.g. the Marsaglia generator posted here less than a week ago) use L=250 or more. Maurer's test seems best adapted for inspecting the output of _physical_ random number generators ... things that contain nuclear scintillation counters and 1/f differentiators and radio receivers tuned between channels and Zener diodes and other random physical phenomena. Software generators, even extremely well-known examples of BAD random numbers, can easily cheat Maurer and obtain a passing grade they obviously don't deserve.