comp.arch.arithmetic #1306 (2 more)
+     edu!swrinde!!!news.
From: (Nick Maclaren)
Newsgroups: comp.arch.arithmetic

Subject: Re: Psuedo Random Numbers
Date: 7 Oct 1995 17:05:59 GMT
Organization: University of Cambridge, England
Lines: 75
Message-ID: <456c1n$>
References: <44vm6r$> 

In article ,
Robert I. Eachus  wrote:
>In article <44vm6r$> Matthew Carlson  write
>  > Thanks for all the responses I got with my last question. I have received 
>  > a number of 32 bit random number generators. I am wondering which one is 
>  > the best of those currently available.
>   My Blum, Blum and Shub based generator of course, but don't take my
>word for it, read the original Blum, Blum and Shub paper. :-) (The
>Blum, Blum and Shub algorithm is at least as difficult to predict as
>it is to factor the modulus.  RSA has not been proven to be quite that
>difficult, but I also don't think anyone has based an RNG on it.)

However, PLEASE remember that this paper is SERIOUSLY flawed, and the
technique is NOTHING LIKE as good as it is claimed to be.  Sorry about
the capitals, and all that, but ....

No 32-bit generator is adequate for generating more than about 3,000,000
numbers, whatever technique it uses.  See:

    N.M. Maclaren, A Limit on the Usable Length of a Pseudorandom Number
    Sequence (Journal of Statistical Computation and Simulation (1992),
    vol. 42, pp. 47-54).

The flaws in the Blum, Blum and Shub paper are that it uses a plausible
(but unproven) exponential/polynomial complexity theory result to build
its generator.  If you chase up the theory of this a bit further, you
discover that there are almost no useful indications of how to apply this
to finite generators, let alone small ones.  I believe that there is good
evidence that a 32-bit Blum, Blum and Shub generator will generate 1,000
bits safely, and I have proof that it will start to fail at 3,000,000;
this leaves a lot of leeway for mistakes :-(

>  > I also wanted something with more bits, say 64 bits or more. I
>  > noticed a 48 bit random number generator on SunOs, it is called
>  > rand48.
>   I won't call the SunOS generator junk.  It is better than that, but
>at the execution time overhead cost you should be getting something
>much better.  The best way to use it is to generate starting seeds for
>your own generator.

It fails at least one of my tests, with at least some starting values.
The only known published generators that pass all of the tests that I use
are Wichmann-Hill (Applied Statistics, AS183) and that only just, the
James et al. one (in full form) which is very slow, and MODIFICATIONS of
a couple of Marsaglia's.  All of the single-precision (32-bit) ones fail
fairly horribly, incidentally, so you must use double or better.

>   You need to select numbers which work for 64-bits read Knuth (Art
>of Computer Programming) or the Park and Miller paper in Comm. ACM
>(Random Number Generators: Good ones are Hard to Find, Comm. ACM, 31,
>10, 1192-1201).  But if you need an "extremely random" generator DON'T
>USE LCGs!  If you are interested in why, I can provide references.

Yes, but don't do it that way.  Use a composite modulus (e.g. a multiple
of 3 primes) and the coding trick used in the Wichmann-Hill generator.
I actually disagree about not using LCGs - they work perfectly well
against an unintelligent opponent (i.e. Monte-Carlo, and not cryptography)
PROVIDED that the modulus is big enough.  And big enough nowadays doesn't
mean 64 bits!

I have a couple that I use that are rather better.  If the ADAR one is
well-coded and in double precision, it should be safe for up to nearly
1,000,000,000 numbers.  However, this is a guess, for reasons mentioned
above.  Please ask me if you want code of mine.

Nick Maclaren,
University of Cambridge Computer Laboratory,
New Museums Site, Pembroke Street, Cambridge CB2 3QG, England.
Tel.:  +44 1223 334761    Fax:  +44 1223 334679