On the use of reducible polynomials as random number generators
HTML articles powered by AMS MathViewer
- by Da Kai Wang and Aaldert Compagner PDF
- Math. Comp. 60 (1993), 363-374 Request permission
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.References
- 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, DOI 10.1090/S0025-5718-1990-1011436-4
- John Brillhart and J. L. Selfridge, Some factorizations of $2^{n}\pm 1$ and related results, Math. Comp. 21 (1967), 87-96; corrigendum, ibid. 21 (1967), 751. MR 0224532, DOI 10.1090/S0025-5718-1967-0224532-3
- Aaldert Compagner, The hierarchy of correlations in random binary sequences, J. Statist. Phys. 63 (1991), no. 5-6, 883–896. MR 1116039, DOI 10.1007/BF01029989 —, Definitions of randomness, Amer. J. Phys. 59 (1991), 700-705.
- A. Compagner and A. Hoogland, Maximum-length sequences, cellular automata, and random numbers, J. Comput. Phys. 71 (1987), no. 2, 391–428. MR 897246, DOI 10.1016/0021-9991(87)90037-4
- Solomon W. Golomb, Shift register sequences, Holden-Day, Inc., San Francisco, Calif.-Cambridge-Amsterdam, 1967. With portions co-authored by Lloyd R. Welch, Richard M. Goldstein, and Alfred W. Hales. MR 0242575
- 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 339892, DOI 10.1049/el:19710226
- F. James, A review of pseudorandom number generators, Comput. Phys. Comm. 60 (1990), no. 3, 329–344. MR 1076267, DOI 10.1016/0010-4655(90)90032-V
- Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
- Rudolf Lidl and Harald Niederreiter, Introduction to finite fields and their applications, Cambridge University Press, Cambridge, 1986. MR 860948 G. Marsaglia, A current view of random number generators, Computer Science and Statistics (L. Billard, ed.), North-Holland, Amsterdam, 1985, pp. 3-10.
- 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, DOI 10.1007/BF02310104
- 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, DOI 10.1007/BF02204856 —, Weights of cyclic codes, Inform, and Control 34 (1977), 130-140. B. D. Ripley, Thoughts on pseudorandom number generators, J. Comput. Appl. Math. 31 (1990), 153-163.
- Neal Zierler, Primitive trinomials whose degree is a Mersenne exponent, Information and Control 15 (1969), 67–69. MR 244205
- Neal Zierler and John Brillhart, On primitive trinomials $(\textrm {mod}\ 2)$, Information and Control 13 (1968), 541–554. MR 237468
Additional Information
- © Copyright 1993 American Mathematical Society
- 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