comp.arch.arithmetic #1306 (2 more) Path: news.io.com!news.fc.net!news3.net99.net!news.cais.net!ringer.cs.utsa. + edu!swrinde!howland.reston.ans.net!newsfeed.internetmci.com!news. + mathworks.com!tank.news.pipex.net!pipex!lyra.csx.cam.ac.uk!nmm1 From: nmm1@cus.cam.ac.uk (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$fik@lyra.csx.cam.ac.uk> References: <44vm6r$1q5@bug.rahul.net>NNTP-Posting-Host: bootes.cus.cam.ac.uk In article , Robert I. Eachus wrote: >In article <44vm6r$1q5@bug.rahul.net> Matthew Carlson write s: > > > 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. Email: nmm1@cam.ac.uk Tel.: +44 1223 334761 Fax: +44 1223 334679