MONTE CARLO TECHNIQUES, widely used in computer simulations of physical systems, entail the wholesale generation of random numbers. A new study by scientists at the University of Georgia (Alan Ferrenberg, 404-542-8460) shows that even the most advanced random-number generators are biased under certain circumstances (A.M. Ferrenberg et al., 7 Dec. Physical Review Letters). Using one state-of-the-art program, the Marsaglia-Zeman random-number generator, Ferrenberg discovered that a simulated performance of the two-dimensional Ising model (which models the behavior of a plane of neighboring spins) did not agree with the results when calculated exactly by mathematical methods. He traced the discrepancy to the random- number generator. Other generators tried had differing faults. (Science News, 19 & 26 Dec.)
Can someone get the paper(s) and/or talk to the researcher? Does he have any programs he can throw into the pot for generating or testing random numbers? John
Here's a list of references from the end of Rueppel's _Stream_Chiphers_ that seem to be relevant to random number generation: J. Bernasconi and C.G. Gunther, "Analysis of a nonlinear feedforward logic for binary sequence generators," BBC Tech. Rep., 1985 T. Beth and F. Piper, "The stop-and-go generator," in Lecture Notes in Computer Science 109; Advances in Cryptology: Proc. Eurocrypt '84, T. Beth, N. Cot, and I. Ingemarsson, Eds., Paris, France, April 9-11, 1984, pp. 88-92. Berlin: Springer-Verlag, 1985. M. Blum and S. Micali, "How to generate cryptographically strong sequences of pseudo-random bits," SIAM J. Comput., vol. 13, pp. 850-864, 1984 L. Blum, M. Blum , and M. Shub, "A simple unpredictable pseudo-random number generator," SIAM J. Comput., vol. 15, pp. 364-383, 1986. J.O. Bruer, "On pseudo random sequences as crypto generators," in Proc. Int Zurich Seminar on Digital communication, Switzerland, 1984. L. Brynielsson, "On the linear complexity of combined shift regiser sequences," in Lecture Notes in Computer Science 219; Advances in Cryptology: Proc. Eurocrypt '85, F. Pichler, Ed., Linz, Austria, April 1985, pp. 156-166. Berlin: Springer-Verlag, 1986. J. Gait, "A new nonlinear pseudorandom number generator," IEEE Trans. Software Eng., vols. S E3, no. 5, pp. 359-363, Sept. 1977. O. Goldreich, S. Goldwasser, and S. Micali, "How to construct random functions," J. ACM, vol. 33, no. 4, pp. 792-807, 1986. D. Gollman, "Pseudo random properties of cascade connections of clock controlled shift registers," in Lecture Notes in Computer Science 209; Advances in Cryptology: Proc. Eurocrypt '84, T. Beth, N. Cot, and I. Ingermasson, Eds., Paris, France, April 9-11, 1984, pp. 93-98. Berlin: Springer-Verlag, 1985. B. Kaliski, A pseudo random bit generator based on elliptic logarithms, M. Sc. thesis, Massachusetts Institute of Technology, 1987. E. L. Key, "An analysis of the structure and complexity of nonlinear binary sequence generators," IEEE Trans. Inform. Theory, vol. IT-22, no. 6, pp. 732-763, Nov. 1976. M. Luby and C. Rackoff, "How to construct pseudorandom permutations from pseudorandom functions," SIAM J. Comput. vol. 17, pp. 373-386, 1988. J.L. Massey, A. Gubser, A. Fischer, P. Hochstrasser, B. Huber, and R. Sutter, "A self-synchronizing digital scrambler for cryptographic protection of data," in Proceedings of International Zurich Seminar, March, 1984. J.L. Massey and R.A. Rueppel, "Linear ciphers and random sequence generators with multiple clocks," in Lecture Notes in Computer Science 209; Advances in Cryptology: Proc. Eurocrypt '84, T. Beth. N. Cot, and I. Ingermasson, Eds., Paris, France, April 9-11, 1984, pp. 74-87. Berlin: Springer-Verlag, 1985. U. Maurer and J. L. Massey, "Perfect local randomness in pseudo-random sequences," in Lecture Notes in Computer Science 435; Advances in Cryptology: Proc. Crypto'89, G. Brassard, Ed., Santa Barbara, CA, Aug. 20-24. 1989, pp. 110-112. Berlin: Springer-Verlag, 1990. U. Maurer, "A provable-secure strongly-randomized cipher," in Lecture Notes in Computer Science 473; Advances in Cryptology: Proc. Eurocrypt'90, I. Damgard, Ed., Aarhus, Denmark, May 21-24. 1990, pp. 361-373. Berlin: Springer-Verlag. S. Micali and C.P. Schnorr, "Efficient, perfect random number generators," preprint, Massachusetts Institute of Technology, University of Frankfurt, 1988. R.A. Rueppel and O. Stafflebach, "Products of sequences with maximum linear complexity," IEEE Trans. Inform. Theory, vol. IT-33, no.1, pp. 124-131, Jan. 1987. A. Shamir, "On the generation of cryptographically strong pseudo-random sequences," 8th Int. Colloquim on Automata, Languages, and Programming, Lecture Notes in Computer Science 62, Springer Verlag, 1981. Y. Zheng, T. Matsumoto, and H. Imai, "Impossibility and optimality results on constructing pseudorandom permutations," in Lecture Notes in Computer Science 434; Advances in Cryptology; PRoc. Eurocrypt'89, J.-J. Quisquater and J. Vandewalle, Eds., Houthalen, Belgium, April 10-23, 1989, pp. 412-422. Berlin: Springer-Verlag, 1990. -- Yanek Martinson mthvax.cs.miami.edu!safe0!yanek uunet!medexam!yanek this address preferred -->> yanek@novavax.nova.edu <<-- this address preferred Phone (305) 765-6300 daytime FAX: (305) 765-6708 1321 N 65 Way/Hollywood (305) 963-1931 evenings (305) 981-9812 Florida, 33024-5819
Can someone get the paper(s) and/or talk to the researcher?
got it! peter ------- Forwarded Message Date: Tue, 12 Jan 1993 14:14:39 -0500 From: amf@csp2.csp.uga.edu (Alan Ferrenberg) To: honey@citi.umich.edu Subject: Re: Phys. Rev. Let. paper Dear Dr. Honeyman, A postscript version of the paper is available on our anonymous ftp site (csp2.csp.uga.edu) in the /pub/documents/amf1 directory as rng.ps. Alan Ferrenberg PS: We are just beginning this ftp site, but have already collected a number of (hopefully) interesting preprints from several authors here, as well as from Japan and Israel. Please feel free to browse through the selection of papers, to upload any articles you feel might be interesting to simulational physicists and to spread the word about this new service. ------- End of Forwarded Message
participants (3)
-
gnu＠cygnus.com -
peter honeyman -
yanek＠novavax.nova.edu