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.