Path: news.io.com!news.fc.net!news3.net99.net!news.cais.net!ringer.cs.utsa. + edu!swrinde!howland.reston.ans.net!news.sprintlink.net!wizard.pn.com! + mozo.cc.purdue.edu!not-for-mail From: hrubin@b.stat.purdue.edu (Herman Rubin) Newsgroups: comp.arch.arithmetic Subject: Re: Psuedo Random Numbers Date: 8 Oct 1995 13:05:24 -0500 Organization: Purdue University Statistics Department Lines: 57 Message-ID: <4593t4$2nm0@b.stat.purdue.edu> References: <44vm6r$1q5@bug.rahul.net>NNTP-Posting-Host: b.stat.purdue.edu 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.) The >paper is: >A Simple Unpredictable Pseudo-Random Number Generator, by L. Blum, M. >Blum, and M. Shub, SIAM Journal of Computing, Vol 15, No. 2, May 1986. >(Don't believe that the simple applies to the paper, it is very dense >and hard to work through, but worth it.) If this is the paper I think it is, the generator is far too slow to be of much use, unless one needs fantastically good pseudo-random numbers, and can afford the cost. Now this might not be the paper I am thinking of, but the one I have in mind uses two large primes congruent to 3 mod 4, and at each stage squares the seed modulo the product, and outputs the least significant bit. This is a lot of work for ONE bit. There is an earlier RSA baed PRNG, by Shamir. This one also uses the product n of two primes, and two seeds. Each seed is raised to a different exponent (Shamir uses the two conjugate keys, but presumably more can be done), and the output is the sum mod n. This was criticized as not giving bits, although I find this criticism unacceptable, as it is easy to get random bits from random integers between 0 and n-1. This has comparable cost per bit. > Also, it is not clear whether you want an integer generator or a >floating point generator. The ADAR components contain both. They have >a period of 562,085,314,430,582 (the product of 26 bit and 27 bit >special primes). The floating generator can produce all representable >values between 0.5 and 1.0 on most floating point implementations. >(Yes, it produces exactly as many values less than 0.5, but the nature >of floating point is such that there are a lot more representable >values in that range.) The integer generator is based on the same >generator, but maps to a (presumably 32-bit) integer type. The period is essentially unimprtant. A Tausworthe generator like x[n] = x[n-460] + x[n-607] has period 2^(s-1)*(2^607 -1), where s is the word length; this is in integer arithmetic. This class of procedures are now known to have drawbacks. Since even on badly designed computers, converting integer to floating is relatively simple, the fact that integer procedures presumably give a random bit stream (or should try to do a good job of it) means that they should be the general input. -- Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399 hrubin@stat.purdue.edu Phone: (317)494-6054 FAX: (317)494-0558