From: gnu@cygnus.com
Date: Sun, 4 Apr 93 17:56:05 PDT
To: cypherpunks@toad.com
Subject: Problems with "high quality" random number generators, FYI
Message-ID: <9304050056.AA05690@cygnus.com>
MIME-Version: 1.0
Content-Type: text/plain


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