From: "geeman@best.com" <geeman@best.com>
Date: Wed, 4 Sep 1996 13:53:23 +0800
To: "'cypherpunks@toad.com>
Subject: RE: Is Knuth's _AoCP_ still the authority on PRNG?
Message-ID: <01BB99D9.9A115240@geeman.vip.best.com>
MIME-Version: 1.0
Content-Type: text/plain


check out
"On the Efficient Generation of Cryptographic Confusion and Diffusion Sequences"

I may have gotten the title less than perfect.  AltaVista will find it for you if you try.

Excellent piece.


----------
From: 	eli+@gs160.sp.cs.cmu.edu[SMTP:eli+@gs160.sp.cs.cmu.edu]
Sent: 	Tuesday, September 03, 1996 7:54 PM
To: 	coderpunks@toad.com
Subject: 	Re: Is Knuth's _AoCP_ still the authority on PRNG?

Bryce writes:
>I'm reading Knuth chapter 3 on "random numbers".  Have there
>been any major advances since the publication of the second
>edition of _The Art of Computer Programming, Volume 2_ in 1981?

A much-referenced article:
Marsaglia, G. (1985). "A current view of random number generation".
In L. Billard (ed.), _Computer Science and Statistics: The Interface_.

A more recent survey, which I haven't read:
L'Ecuyer, P. (1990). "Random numbers for simulation".  CACM 87,
no. 10, 85-97.

I read the resulting _NYT_ blurb, but not the paper:
Ferrenberg et al. (1992). "Monte Carlo simulations: Hidden errors from
`good' random number generators".  Phys. Rev. Lett. 69, 3382-4.

This is from the "simulation" angle, which is where Knuth is coming
from.  For crypto you may be interested in the complexity-theoretic
approach (things like Blum-Blum-Shub), which is a whole different
field.

>Are any of the ideas advocated in chapter 3 now considered
>inadvisable?

I think the Marsaglia paper sank Knuth's recommended generator.
"Sank" is a relative term, of course.

--
   Eli Brandt
   eli+@cs.cmu.edu