From: Jim choate <ravage@bga.com>
Date: Thu, 7 Jul 94 13:21:04 PDT
To: cypherpunks@toad.com
Subject: (fwd) Re: BSD random() - any good (source included)?
Message-ID: <199407072020.PAA29397@ivy.bga.com>
MIME-Version: 1.0
Content-Type: text/plain


Path: bga.com!news.sprintlink.net!hookup!ames!lll-winken.llnl.gov!noc.near.net!pad-thai.aktis.com!la-jiao.aktis.com!not-for-mail
From: don@cam.ov.com (Donald T. Davis)
Newsgroups: sci.math,sci.stat.math
Subject: Re: BSD random() - any good (source included)?
Date: 28 Jun 1994 17:52:48 -0400
Organization: OpenVision Technologies, Inc.
Lines: 65
Distribution: na
Message-ID: <2uq63g$g5c@la-jiao.aktis.com>
References: <deleydCs1L9A.2L6@netcom.com> <iFwLoc3w165w@hakatac.almanac.bc.ca> <Cs4B6w.IqE@SSD.intel.com>
NNTP-Posting-Host: la-jiao.aktis.com
Xref: bga.com sci.math:15008 sci.stat.math:1243

(George Carr) writes:
>(robert bursey) writes:
>|> deleyd@netcom.com writes:
>|> 
>|> > I did a research paper on Computer Generated Random Number Sequences in
>|> > 1991.  Included are the results of testing numerous popular generators.
>|> > The code used for testing the generators is also available if one
>|> > is so inclined to do some testing of a particular generator.  (The only
>|> > thing is a thorough test to determine the limits of the generator can
>|> > take many hours of CPU time).
>|> >
>|> > Perhaps later this week I'll post the paper and see what the response
>|> > is.  I'm always a bit apprehensive to post.  Never sure what the
>|> > response will be.  Maybe someone will think it's interesting.
>|> >
>|> > David Deley
>|> > deleyd@netcom.com
>|> 
>|> Does anybody know of a good test for randomness? I would definitely like to 
>|> know how good computer RNG's are. Post away!
>
>The classic reference is Volume 2 of Donald Knuth's The Art of Computer
>Programming, Second Edition, Seminumerical Algorithms. I highly recommend
>it to anyone wanting to know what "random" is all about.
>
>If you really need to know whether your generator is random-enough for
>your application you should expect to do your own testing and yes it will
>require many hours of your time in addition to that of your computer.
>-- 
knuth's chapter's practical results are about linear-congruential
rngs, their optimization and testing. though these rngs are still
distressingly common, nonlinear rngs are the way to go for two
burgeoning areas that consume random numbers: graphics and cryptography.
both areas are concerned with getting extremely long periods, but
cryptography is also concerned with proving unpredictability of
secure rngs. that is, knowing some outputs of an rng as applied to a
given seed, it should be impossible to deduce or predict other
outputs' values.

so, you see, the "good test for randomness" depends strongly on which
features of a random variable you want to use. if you're careful,
knuth's approach will work fine for some statistical applications,
like monte-carlo techniques. but knuth's is by no means the last
word on the subject. btw, for cryptographic purposes, the received
wisdom is that there is NO adequate test for randomness; if an rng
passes lots of tests, that's very nice, but the presumption is that
the variable's deterministic structure is simply hidden, and that
the clever-enough test was not yet applied or devised.

nevertheless, in the cryptographic field, the list of tests used
is long. typically, you design the test to probe the weaknesses of
a specific rng algorithm.  period tests, runs tests, and
substring-interarrival tests are common, and some people like
entropy estimates. one of the trusted names in the crypto-rng
literature is marsaglia; he has published extensively on the
subject of rng-testing. i don't know what the graphics literature
on rngs is like; i only know that if you want to simulate textured
surfaces, like grass, a bad rng makes a striped texture.

be forwarned: the rng literature is amazingly vast, with a low signal-
to-noise ratio. it seems that everyone thinks he can design a "good"
rng. btw, i favor hardware rngs.
					-don davis
					 openvision technologies
					 cambridge, ma