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