Problems with "high quality" random number generators, FYI

[gnu at cygnus.com]

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 at uunet.UU.NET (Dean Schulze)
Subject: Problems with "high quality" random number generators
To: na.digest at surfer.EPM.ORNL.GOV
Cc: numeric-interest at validgh.com
Message-Id: <9304032004.AA06752 at 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