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