On the use of reducible polynomials as random number generators

Wang, Da Kai; Compagner, Aaldert

doi:10.1090/S0025-5718-1993-1155576-0

On the use of reducible polynomials as random number generators

Authors: Da Kai Wang and Aaldert Compagner
Journal: Math. Comp. 60 (1993), 363-374
MSC: Primary 65C10; Secondary 11K99
DOI: https://doi.org/10.1090/S0025-5718-1993-1155576-0
MathSciNet review: 1155576
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The randomness properties and the hierarchy of correlation coefficients are studied of approximate-maximum-length sequences, for which the characteristic polynomial is a product of several primitive polynomials. The randomness properties are almost the same as for maximum-length sequences characterized by a primitive polynomial with many terms and of the same degree. Reducible characteristic polynomials have acceptable figures of merit and can be of extremely high degree. Since they are also easily constructed and implemented, reducible polynomials are strong candidates for reliable random number generation, especially at the bit rates needed in large-scale Monte Carlo simulations.

[1] Debra A. André, Gary L. Mullen, and Harald Niederreiter, Figures of merit for digital multistep pseudorandom numbers, Math. Comp. 54 (1990), no. 190, 737–748. MR 1011436, https://doi.org/10.1090/S0025-5718-1990-1011436-4
[2] John Brillhart and J. L. Selfridge, Some factorizations of 2ⁿ±1 and related results, Math. Comp. 21 (1967), 87-96; corrigendum, ibid. 21 (1967), 751. MR 0224532, https://doi.org/10.1090/S0025-5718-67-99898-5
[3] Aaldert Compagner, The hierarchy of correlations in random binary sequences, J. Statist. Phys. 63 (1991), no. 5-6, 883–896. MR 1116039, https://doi.org/10.1007/BF01029989
[4] -, Definitions of randomness, Amer. J. Phys. 59 (1991), 700-705.
[5] A. Compagner and A. Hoogland, Maximum-length sequences, cellular automata, and random numbers, J. Comput. Phys. 71 (1987), no. 2, 391–428. MR 897246, https://doi.org/10.1016/0021-9991(87)90037-4
[6] Solomon W. Golomb, Shift register sequences, With portions co-authored by Lloyd R. Welch, Richard M. Goldstein, and Alfred W. Hales, Holden-Day, Inc., San Francisco, Calif.-Cambridge-Amsterdam, 1967. MR 0242575
[7] G. F. A. Hoffmann de Visme, Property of cosets and its application to the calculation of moments of binary sequences having multipliers, Electron. Lett. 7 (1971), 328–330. MR 0339892, https://doi.org/10.1049/el:19710226
[8] F. James, A review of pseudorandom number generators, Comput. Phys. Comm. 60 (1990), no. 3, 329–344. MR 1076267, https://doi.org/10.1016/0010-4655(90)90032-V
[9] Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR 633878
[10] Rudolf Lidl and Harald Niederreiter, Introduction to finite fields and their applications, Cambridge University Press, Cambridge, 1986. MR 860948
[11] G. Marsaglia, A current view of random number generators, Computer Science and Statistics (L. Billard, ed.), North-Holland, Amsterdam, 1985, pp. 3-10.
[12] G. L. Mullen and H. Niederreiter, Optimal characteristic polynomials for digital multistep pseudorandom numbers, Computing 39 (1987), no. 2, 155–163 (English, with German summary). MR 919665, https://doi.org/10.1007/BF02310104
[13] Harald Niederreiter, Recent trends in random number and random vector generation, Ann. Oper. Res. 31 (1991), no. 1-4, 323–345. Stochastic programming, Part II (Ann Arbor, MI, 1989). MR 1118905, https://doi.org/10.1007/BF02204856
[14] -, Weights of cyclic codes, Inform, and Control 34 (1977), 130-140.
[15] B. D. Ripley, Thoughts on pseudorandom number generators, J. Comput. Appl. Math. 31 (1990), 153-163.
[16] Neal Zierler, Primitive trinomials whose degree is a Mersenne exponent, Information and Control 15 (1969), 67–69. MR 0244205
[17] Neal Zierler and John Brillhart, On primitive trinomials (𝑚𝑜𝑑2), Information and Control 13 (1968), 541–554. MR 0237468