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
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

59

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

A current view of random number generators

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

34

Thoughts on pseudorandom number generators

31

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