Is Knuth's _AoCP_ still the authority on PRNG?

geeman at best.com geeman at best.com
Tue Sep 3 22:53:23 PDT 1996


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+ at gs160.sp.cs.cmu.edu[SMTP:eli+ at gs160.sp.cs.cmu.edu]
Sent: 	Tuesday, September 03, 1996 7:54 PM
To: 	coderpunks at 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+ at cs.cmu.edu









More information about the cypherpunks-legacy mailing list