{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T00:28:01Z","timestamp":1771979281621,"version":"3.50.1"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2006,3,1]],"date-time":"2006-03-01T00:00:00Z","timestamp":1141171200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2006,3]]},"abstract":"<jats:p>Fast uniform random number generators with extremely long periods have been defined and implemented based on linear recurrences modulo 2. The twisted GFSR and the Mersenne twister are famous recent examples. Besides the period length, the statistical quality of these generators is usually assessed via their equidistribution properties. The huge-period generators proposed so far are not quite optimal in this respect. In this article, we propose new generators of that form with better equidistribution and \u201cbit-mixing\u201d properties for equivalent period length and speed. The state of our new generators evolves in a more chaotic way than for the Mersenne twister. We illustrate how this can reduce the impact of persistent dependencies among successive output values, which can be observed in certain parts of the period of gigantic generators such as the Mersenne twister.<\/jats:p>","DOI":"10.1145\/1132973.1132974","type":"journal-article","created":{"date-parts":[[2006,7,25]],"date-time":"2006-07-25T14:14:26Z","timestamp":1153836866000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":182,"title":["Improved long-period generators based on linear recurrences modulo 2"],"prefix":"10.1145","volume":"32","author":[{"given":"Fran\u00e7ois","family":"Panneton","sequence":"first","affiliation":[{"name":"Universit\u00e9 de Montr\u00e9al, Montr\u00e9al, Canada"}]},{"given":"Pierre","family":"L'Ecuyer","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Montr\u00e9al, Montr\u00e9al, Canada"}]},{"given":"Makoto","family":"Matsumoto","sequence":"additional","affiliation":[{"name":"Hiroshima University, Hiroshima, Japan"}]}],"member":"320","published-online":{"date-parts":[[2006,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1090\/S0025-5718-1970-0276200-X","article-title":"Factoring polynomials over large finite fields","volume":"24","author":"Berlekamp E. R.","year":"1970","unstructured":"Berlekamp , E. R. 1970 . Factoring polynomials over large finite fields . Math. Comput. 24 , 713 -- 735 . Berlekamp, E. R. 1970. Factoring polynomials over large finite fields. Math. Comput. 24, 713--735.","journal-title":"Math. Comput."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Brent R. P. Larvala S. and Zimmermann P. 2003. A fast algorithm for testing reducibility of trinomials mod 2 and some new primitive trinomials of degree 3021377. Math. Comput. 72 243 1443--1452. 10.1090\/S0025-5718-02-01478-3   Brent R. P. Larvala S. and Zimmermann P. 2003. A fast algorithm for testing reducibility of trinomials mod 2 and some new primitive trinomials of degree 3021377. Math. Comput. 72 243 1443--1452. 10.1090\/S0025-5718-02-01478-3","DOI":"10.1090\/S0025-5718-02-01478-3"},{"key":"e_1_2_1_3_1","unstructured":"Chabaud F. and Lercier R. 2000. A toolbox for fast computation in finite extension over finite rings. Software User's Guide. See http:\/\/zenfact.sourceforge.net\/.  Chabaud F. and Lercier R. 2000. A toolbox for fast computation in finite extension over finite rings. Software User's Guide. See http:\/\/zenfact.sourceforge.net\/."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","first-page":"883","DOI":"10.1007\/BF01029989","article-title":"The hierarchy of correlations in random binary sequences","volume":"63","author":"Compagner A.","year":"1991","unstructured":"Compagner , A. 1991 . The hierarchy of correlations in random binary sequences . J. Stat. Phy. 63 , 883 -- 896 . Compagner, A. 1991. The hierarchy of correlations in random binary sequences. J. Stat. Phy. 63, 883--896.","journal-title":"J. Stat. Phy."},{"key":"e_1_2_1_5_1","unstructured":"Couture R. and L'Ecuyer P. 2000. Lattice computations for random numbers. Math. Comput. 69 230 757--765. 10.1090\/S0025-5718-99-01112-6   Couture R. and L'Ecuyer P. 2000. Lattice computations for random numbers. Math. Comput. 69 230 757--765. 10.1090\/S0025-5718-99-01112-6"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/358150.358159"},{"key":"e_1_2_1_8_1","volume-title":"Seminumerical Algorithms","author":"Knuth D. E.","unstructured":"Knuth , D. E. 1998. The Art of Computer Programming , vol. 2 : Seminumerical Algorithms , 3 rd ed. Addison-Wesley , Reading, Mass . Knuth, D. E. 1998. The Art of Computer Programming, vol. 2: Seminumerical Algorithms, 3rd ed. Addison-Wesley, Reading, Mass.","edition":"3"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/BF02136827","article-title":"Uniform random number generation","volume":"53","author":"L'Ecuyer P.","year":"1994","unstructured":"L'Ecuyer , P. 1994 . Uniform random number generation . Ann. Oper. Res. 53 , 77 -- 120 . L'Ecuyer, P. 1994. Uniform random number generation. Ann. Oper. Res. 53, 77--120.","journal-title":"Ann. Oper. Res."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"L'Ecuyer P. 1996. Maximally equidistributed combined Tausworthe generators. Math. Comput. 65 213 203--213. 10.1090\/S0025-5718-96-00696-5   L'Ecuyer P. 1996. Maximally equidistributed combined Tausworthe generators. Math. Comput. 65 213 203--213. 10.1090\/S0025-5718-96-00696-5","DOI":"10.1090\/S0025-5718-96-00696-5"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.47.1.159"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"L'Ecuyer P. 1999b. Tables of maximally equidistributed combined LFSR generators. Math. Comput. 68 225 261--269. 10.1090\/S0025-5718-99-01039-X   L'Ecuyer P. 1999b. Tables of maximally equidistributed combined LFSR generators. Math. Comput. 68 225 261--269. 10.1090\/S0025-5718-99-01039-X","DOI":"10.1090\/S0025-5718-99-01039-X"},{"key":"e_1_2_1_13_1","volume-title":"Handbook of Computational Statistics, J. E. Gentle et al., eds","author":"L'Ecuyer P.","unstructured":"L'Ecuyer , P. 2004. Random number generation . In Handbook of Computational Statistics, J. E. Gentle et al., eds . Springer Verlag , Berlin , 35--70. L'Ecuyer, P. 2004. Random number generation. In Handbook of Computational Statistics, J. E. Gentle et al., eds. Springer Verlag, Berlin, 35--70."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"L'Ecuyer P. and Panneton F. 2002. Construction of equidistributed generators based on linear recurrences modulo 2. In Monte Carlo and Quasi-Monte Carlo Methods 2000 K.-T. Fang et al. eds. Springer Verlag Berlin 318--330.   L'Ecuyer P. and Panneton F. 2002. Construction of equidistributed generators based on linear recurrences modulo 2. In Monte Carlo and Quasi-Monte Carlo Methods 2000 K.-T. Fang et al. eds. Springer Verlag Berlin 318--330.","DOI":"10.1007\/978-3-642-56046-0_21"},{"key":"e_1_2_1_15_1","unstructured":"L'Ecuyer P. and Simard R. 2002. TestU01: A Software Library in ANSI C for Empirical Testing of Random Number Generators. Software User's Guide. http:\/\/www.iro.umontreal.ca\/~lecuyer. 10.1145\/1268776.1268777   L'Ecuyer P. and Simard R. 2002. TestU01: A Software Library in ANSI C for Empirical Testing of Random Number Generators. Software User's Guide. http:\/\/www.iro.umontreal.ca\/~lecuyer. 10.1145\/1268776.1268777"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1109\/TIT.1968.1054188","article-title":"An analysis of the pseudo-randomness properties of subsequences of long m-sequences","volume":"4","author":"Lindholm J. H.","year":"1968","unstructured":"Lindholm , J. H. 1968 . An analysis of the pseudo-randomness properties of subsequences of long m-sequences . IEEE Trans. Inf. Theor. IT-14 , 4 , 569 -- 576 . Lindholm, J. H. 1968. An analysis of the pseudo-randomness properties of subsequences of long m-sequences. IEEE Trans. Inf. Theor. IT-14, 4, 569--576.","journal-title":"IEEE Trans. Inf. Theor. IT-14"},{"key":"e_1_2_1_17_1","volume-title":"Sixteenth Symposium on the Interface. Elsevier Science Publishers, North-Holland","author":"Marsaglia G.","year":"1985","unstructured":"Marsaglia , G. 1985 . A current view of random number generators. In Computer Science and Statistics , Sixteenth Symposium on the Interface. Elsevier Science Publishers, North-Holland , Amsterdam, 3--10. Marsaglia, G. 1985. A current view of random number generators. In Computer Science and Statistics, Sixteenth Symposium on the Interface. Elsevier Science Publishers, North-Holland, Amsterdam, 3--10."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/189443.189445"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/232807.232815"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/272991.272995"},{"key":"e_1_2_1_21_1","series-title":"SIAM CBMS-NSF Regional Conference Series in Applied Mathematics","volume-title":"Random Number Generation and Quasi-Monte Carlo Methods","author":"Niederreiter H.","unstructured":"Niederreiter , H. 1992. Random Number Generation and Quasi-Monte Carlo Methods . SIAM CBMS-NSF Regional Conference Series in Applied Mathematics , vol. 63 . SIAM , Philadelphia . Niederreiter, H. 1992. Random Number Generation and Quasi-Monte Carlo Methods. SIAM CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63. SIAM, Philadelphia."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/369534.369540"},{"key":"e_1_2_1_24_1","volume-title":"Monte Carlo and Quasi-Monte Carlo Methods","author":"Panneton F.","year":"2002","unstructured":"Panneton , F. and L'Ecuyer , P. 2004. Random number generators based on linear recurrences in F2w . In Monte Carlo and Quasi-Monte Carlo Methods 2002 , H. Niederreiter, ed. Springer Verlag , Berlin, 367--378. Panneton, F. and L'Ecuyer, P. 2004. Random number generators based on linear recurrences in F2w. In Monte Carlo and Quasi-Monte Carlo Methods 2002, H. Niederreiter, ed. Springer Verlag, Berlin, 367--378."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 1998 IEEE International Symposium on Information Theory","author":"Rieke A.","unstructured":"Rieke , A. , Sadeghi , A.-R. , and Poguntke , W . 1998. On primitivity tests for polynomials . In Proceedings of the 1998 IEEE International Symposium on Information Theory . Cambridge, Mass. Rieke, A., Sadeghi, A.-R., and Poguntke, W. 1998. On primitivity tests for polynomials. In Proceedings of the 1998 IEEE International Symposium on Information Theory. Cambridge, Mass."},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","first-page":"656","DOI":"10.1002\/j.1538-7305.1949.tb00928.x","article-title":"Communication theory of secrecy systems","volume":"28","author":"Shannon C. E.","year":"1949","unstructured":"Shannon , C. E. 1949 . Communication theory of secrecy systems . Bell Syst. Tech. J. 28 , 656 -- 715 . Shannon, C. E. 1949. Communication theory of secrecy systems. Bell Syst. Tech. J. 28, 656--715.","journal-title":"Bell Syst. Tech. J."},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1090\/S0025-5718-1965-0184406-1","article-title":"Random numbers generated by linear recurrence modulo two","volume":"19","author":"Tausworthe R. C.","year":"1965","unstructured":"Tausworthe , R. C. 1965 . Random numbers generated by linear recurrence modulo two . Math. Comput. 19 , 201 -- 209 . Tausworthe, R. C. 1965. Random numbers generated by linear recurrence modulo two. Math. Comput. 19, 201--209.","journal-title":"Math. Comput."},{"key":"e_1_2_1_28_1","volume-title":"Uniform Random Numbers: Theory and Practice","author":"Tezuka S.","unstructured":"Tezuka , S. 1995. Uniform Random Numbers: Theory and Practice . Kluwer Academic , Norwell, Mass . Tezuka, S. 1995. Uniform Random Numbers: Theory and Practice. Kluwer Academic, Norwell, Mass."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/116890.116892"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/321765.321778"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1090\/S0025-5718-1993-1155576-0","article-title":"On the use of reducible polynomials as random number generators","volume":"60","author":"Wang D.","year":"1993","unstructured":"Wang , D. and Compagner , A. 1993 . On the use of reducible polynomials as random number generators . Math. Comput. 60 , 363 -- 374 . Wang, D. and Compagner, A. 1993. On the use of reducible polynomials as random number generators. Math. Comput. 60, 363--374.","journal-title":"Math. Comput."}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132973.1132974","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1132973.1132974","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:06:13Z","timestamp":1750259173000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132973.1132974"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,3]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,3]]}},"alternative-id":["10.1145\/1132973.1132974"],"URL":"https:\/\/doi.org\/10.1145\/1132973.1132974","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,3]]},"assertion":[{"value":"2006-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}