From: Peter Honeyman <honey@citi.umich.edu>
Date: Mon, 12 Apr 93 22:17:12 PDT
To: cypherpunks@toad.com
Subject: Re: Security Dynamics
Message-ID: <9304130517.AA24164@toad.com>
MIME-Version: 1.0
Content-Type: text/plain


>               I read an article about a pseudorandom number generator
> which appeared random to every test they used on it.  Then they went
> and did a monte carlo simulation of something based on that prng.
> Guess what?  It wasn't quite random enough.  Lesson: it can be *very*
> hard to determine randomness.

if this is the phys. rev. let. paper by ferenburg et al., there's a
postscript copy up for ftp in csp2.csp.uga.edu:/pub/documents/amf1/. 
i can summarize.

their simulations were based on five to ten runs, with 10^7 updates
per run.  they aren't precise about the exact number of random
numbers needed, at least not in this paper, but i assume it's in the
order of one per update, in which case 10,000 would not be enough.
more info can be gleaned from the paper in /pub/documents/adler3/.

they compared four basic rngs.

a linear congruential algorithm (cong)

	x[n] = (16807 * x[n-1]) mod 2^31-1

two different shift register algorithms (sr250 and sr1279)

	x[n] = x[n-103] xor x[n-250]
	x[n] = x[n-103] xor x[n-1279]

a subtract with carry generator algorithm (swc)

	x[n] = x[n-22] - x[n-43] - c
	if x[n] < 0 {
		x[n] += 2^32 - 5
		c = 1
	} else
		c = 0

a combined swc-Weyl generator (swcw)

	y[n] = (y[n-1] - 362436069) mod 2^32
	x[n] = (swc[n] - y[n]) mod 2^32

the authors report that the tables were initialized with some care
(i.e., with cong).  

the result reported in the phys rev let paper is that r250 gave results
that were way off (the model being simulated has an exact solution),
swc was better, but had error in the opposite direction, swcw was
better but still showed signs of bias, and cong was within error limits.
they also report that r1279 was much better than r250, but the tables
are missing from the paper, so ...

on the other hand, using every fifth value from r250 gave results
within error limits.  same with swc.  odd ...

maybe someone can comment on the particular rngs being tested here.
they don't look particularly sophisticated to me, although the authors
describe them as "ostensibly high quality rngs."  hmmm ...

looking over thir recent pubs, it doesn't look like this group (of
statistical physicists) is following up on the rng testing angle.

	peter