Makoto Matsumoto
Abstract
We demonstrate that a majority of modern random number generators, such as the newest version of rand.c, ranlux, and combined multiple recursive generators, have some manifest correlations in their outputs if the initial state is filled up using another linear recurrence with similar modulus. Among 58 available generators in the GNU scientific library, 40 show such defects. This is not because of the recursion, but because of carelessly chosen initialization schemes in the implementations. A good initialization scheme eliminates this phenomenon.
- Biham, E. and Shamir, A. 1991. Differential cryptanalysis of DES-like cryptosystems. J. Cryptol. 4, 1, 3--72.Google Scholar
Digital Library
- GNU. 2004. GNU scientific library version 1.6. http://www.gnu.org/software/gsl/.Google Scholar
- James, F. 1994. Ranlux: A fortran implementation of the high-quality pseudorandom number generator of Lüscher. Comput. Phys. Commun. 79, 1 (Feb.), 111--114.Google ScholarCross Ref
- Knuth, D. E. 1997. The Art of Computer Programming, vol. 2. Seminumerical Algorithms, 3rd ed. Addison-Wesley, Reading, MA. Google ScholarDigital Library
- L'Ecuyer, P. 1996. Combined multiple recursive random number generators. Oper. Res. 44, 5, 816--822.Google ScholarDigital Library
- L'Ecuyer, P. 1992. Testing random number generators. In Proceedings of the IEEE Winter Simulation Conference (Arlington VA). 305--313. Google ScholarDigital Library
- L'Ecuyer, P. 1993. A search for good multiple recursive random number genarators. ACM Trans. Model.Comput. Simul. 3, 2 (Apr.), 87--98. Google ScholarDigital Library
- L'Ecuyer, P., Simard, R., Chen, E. J., and Kelton, W. D. 2002. An object-oriented random number package with many long streams and substreams. Oper. Res. 50, 6, 1073--1075. Google ScholarDigital Library
- L'Ecuyer, P. and Andres, T. H. 1997. A random number generator based on the combination of four LCGs. Math. Comput. Simul. 44, 44, 99--107. Google ScholarDigital Library
- Lüscher, M. 1994. A portable high-quality random number generator for lattice field theory simulations. Comput. Phys. Commun. 79, 1 (Feb.), 100--110.Google ScholarCross Ref
- Mascagni, M. and Srinivasan, A. 2004. Parameterizing parallel multiplicative lagged-Fibonacci generators. Parallel Comput. 30, 7 (Jul.), 899--916.Google ScholarCross Ref
- Mascagni, M. and Srinivasan, A. 2000. Algorithm 806: SPRNG: A scalable library for pseudorandom number generation. ACM Trans. Math. Softw. 26, 3, 436--461. http://sprng.cs.fsu.edu/. Google ScholarDigital Library
- Matsui, M. 1994. Linear cryptanalysis method for DES cipher. In Proceedings of the International Workshop on Theory and Applications Advances in Cryptology (EuroCrypt) (Lofthus, Norway). Lecture Notes in Computer Science, 765. Springer. 386--397. Google ScholarDigital Library
- Matsumoto, M. and Nishimura, T. 1998. Mersenne twister: A 623-dimensionally equidistributed uniform pseudorandom number generator. ACM Trans. Model. Comput. Simul. 8, 1 (Jan.), 3--30. Google ScholarDigital Library
- Matsumoto, M. and Nishimura, T. 2003. Sum-Discrepancy test on pseudorandom number generators. Math. Comput. Simul. 62, 3--61, 431--442. Google ScholarDigital Library
- Matsumoto, M. and Nishimura, T. 2000. The dynamic creation of pseudorandom number generators. In Monte Carlo and Quasi-Monte Carlo Methods. Springer, 56--69.Google Scholar
- Tezuka, S., L'Ecuyer, P., and Couture, R. 1994. On the add-with-carry and subtract-with-borrow random number generators. ACM Trans. Model. Comput. Simul. 3, 4, 315--331. Google ScholarDigital Library
Index Terms
- Common defects in initialization of pseudorandom number generators
Recommendations
On the Structure of Inversive Pseudorandom Number Generators
Applied Algebra, Algebraic Algorithms and Error-Correcting CodesAbstractWe analyze the lattice structure and linear complexity of a new inversive pseudorandom number generator recently introduced by Niederreiter and Rivat. In particular, we introduce a new lattice test which is much stronger than its predecessors and ...
Pseudorandom number generators based on random covers for finite groups
Random covers for finite groups have been introduced in Magliveras et al. (J Cryptol 15:285---297, 2002), Lempken et al. (J Cryptol 22:62---74, 2009), and Svaba and van Trung (J Math Cryptol 4:271---315, 2010) for constructing public key cryptosystems. ...
Does Randomness in the Random Visual Cryptography Protocol Depend on the Period of Pseudorandom Number Generators?
Computer Vision and GraphicsAbstractActual randomness of the shares in the binary random visual cryptography protocol was tested with the NIST statistical test suite. Lack of randomness was noticed for a large secret image (shares 10K by 10K) in that the OverlappingTemplate test ...
Reviews
Soubhik Chakraborty
It is a well-known fact that numbers generated by an arbitrarily selected seed for a pseudorandom number generator (PRNG) may not be statistically random. This paper demonstrates that many modern random number generators have some noticeable patterns, when initial seeds are chosen through a linear recurrence. Matsumoto et al. painstakingly experiment with 58 generators and discover as many as 40 to be defective. Further investigation reveals that the unwanted patterns are caused by the wrong choice of initialization rather than recursion. Accordingly, they advise PRNG designers to use a nonsystematic choice of seeds, or supply a better initialization scheme [1,2], and to test the randomness of the n -th output x ( n , s ) corresponding to a given seed s by varying both n and s . An interesting aspect missed by Matsumoto et al. is that PRNGs generally have a cycle, which, after completion, generates the same sequence, whereas the sequence of decimals of irrational numbers, such as pi, is nonrepeating and nonterminating. Pi, in fact, has been already proposed as a random number generator and the allegation that it is “less random than we thought” has been recently refuted by Marsaglia [3]. Of course, one has to generate these decimals easily and quickly on the computer. Examining some function of pi, rather than pi itself, is a worthwhile proposition. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments