Good sources of randomness are key to good cryptography. Date: 03 Apr 1993 13:04:37 -0700 (MST) From: uunet!asgard.lpl.Arizona.EDU!schulze@uunet.UU.NET (Dean Schulze) Subject: Problems with "high quality" random number generators To: na.digest@surfer.EPM.ORNL.GOV Cc: numeric-interest@validgh.com Message-Id: <9304032004.AA06752@asgard.lpl.Arizona.EDU.LPL-West> A recent Physical Review Letter [1] points out that serious problems can arise in Monte Carlo computations due to subtle correlations in "high quality" random number generators. The quality of these number generators was determined to be "good" because they passed a battery of tests for randomness. However, they produced erroneous results when used together with the Wolff algorithm for cluster-flipping in a simulation of a 2 dimensional Ising model for which the results are known. The author of this Letter, Alan M. Ferrenburg of the University of Georgia, says that an algorithm must be tested together with the random number generator being used regardless of which tests the random number generator has passed on its own. In another development, Shu Tezuka of IBM, Tokyo and Pierre L'Ecuyer of the University of Montreal have proven that the Marsaglia-Zaman random number generators are "essentially equivalent" to linear congruential methods [2]. (Linear congruential number generators produced better results in Ferrenburg's simulations than random number generation algorithms that are of higher quality, however.) [1] Alan M. Ferrenburg, D.P. Landau, and Y. Joanna Wong, "Monte Carlo simulations: Hidden errors from 'good' random number generators", Phys. Rev. Lett., 69, pp. 3382-4, 1992. [2] Science News, v142, pg. 422, 1992. ------- End of Forwarded Message