On the periods of generalized Fibonacci recurrences
HTML articles powered by AMS MathViewer
- by Richard P. Brent PDF
- Math. Comp. 63 (1994), 389-401 Request permission
Abstract:
We give a simple condition for a linear recurrence $\pmod {2^w}$ of degree r to have the maximal possible period ${2^{w - 1}}({2^r} - 1)$. It follows that the period is maximal in the cases of interest for pseudorandom number generation, i.e., for three-term linear recurrences defined by trinomials which are primitive $\pmod 2$ and of degree $r > 2$. We consider the enumeration of certain exceptional polynomials which do not give maximal period, and list all such polynomials of degree less than 15.References
- Stuart L. Anderson, Random number generators on vector supercomputers and other advanced architectures, SIAM Rev. 32 (1990), no.Β 2, 221β251. MR 1056053, DOI 10.1137/1032044 R. P. Brent, On the periods of generalized Fibonacci recurrences, Technical Report TR-CS-92-03, Computer Sciences Laboratory, Australian National University, Canberra, March 1992. β, Uniform random number generators for supercomputers, Proc. Fifth Australian Supercomputer Conference, Melbourne, Dec. 1992, pp. 95-104. A. M. Ferrenberg, D. P. Landau, and Y. J. Wong, Monte Carlo simulations: Hidden errors from "good" random number generators, Phys. Rev. Lett. 69 (1992), 3382-3384.
- 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
- Bert F. Green Jr., J. E. Keith Smith, and Laura Klem, Empirical tests of an additive random number generator, J. Assoc. Comput. Mach. 6 (1959), 527β537. MR 107957, DOI 10.1145/320998.321006
- 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
- E. V. Krishnamurthy, Error-free polynomial matrix computations, Texts and Monographs in Computer Science, Springer-Verlag, New York, 1985. MR 811639, DOI 10.1007/978-1-4612-5118-7
- H. T. Kung, On computing reciprocals of power series, Numer. Math. 22 (1974), 341β348. MR 351045, DOI 10.1007/BF01436917
- Yoshiharu Kurita and Makoto Matsumoto, Primitive $t$-nomials $(t=3,5)$ over $\textrm {GF}(2)$ whose degree is a Mersenne exponent $\le 44497$, Math. Comp. 56 (1991), no.Β 194, 817β821. MR 1068813, DOI 10.1090/S0025-5718-1991-1068813-6 G. Marsaglia, A current view of random number generators, Computer Science and Statistics: The Interface (edited by L. Billard), Elsevier Science Publishers B. V. (North-Holland), 1985, 3-10.
- George Marsaglia and Liang-Huei Tsay, Matrices and the structure of random number sequences, Linear Algebra Appl. 67 (1985), 147β156. MR 787372, DOI 10.1016/0024-3795(85)90192-2 J. F. Reiser, Analysis of additive random number generators, Ph. D. thesis, Department of Computer Science, Stanford University, Stanford, CA, 1977. Also Technical Report STAN-CS-77-601.
- Eugene R. Rodemich and Howard Rumsey Jr., Primitive trinomials of high degree, Math. Comp. 22 (1968), 863β865. MR 238813, DOI 10.1090/S0025-5718-1968-0238813-1 I. Schur, Ganzzahlige Potenzreihen und linear rekurrente Zahlenfolgen, Issai Schur Gesammelte Abhandlungen, Band 3, Springer-Verlag, Berlin, 1973, pp. 400-421.
- Wayne Stahnke, Primitive binary polynomials, Math. Comp. 27 (1973), 977β980. MR 327722, DOI 10.1090/S0025-5718-1973-0327722-7
- Robert C. Tausworthe, Random numbers generated by linear recurrence modulo two, Math. Comp. 19 (1965), 201β209. MR 184406, DOI 10.1090/S0025-5718-1965-0184406-1 B. L. van der Waerden, Algebra, Vol. 1, Chapter 7 (English transl. by Fred Blum, 5th ed.), Ungar, New York, 1953.
- Morgan Ward, The arithmetical theory of linear recurring series, Trans. Amer. Math. Soc. 35 (1933), no.Β 3, 600β628. MR 1501705, DOI 10.1090/S0002-9947-1933-1501705-4
- E. J. Watson, Primitive polynomials $(\textrm {mod}\ 2)$, Math. Comp. 16 (1962), 368β369. MR 148256, DOI 10.1090/S0025-5718-1962-0148256-1
- Hans Zassenhaus, On Hensel factorization. I, J. Number Theory 1 (1969), 291β311. MR 242793, DOI 10.1016/0022-314X(69)90047-X N. Zierler and J. Brillhart, On primitive trinomials $\pmod 2$, Inform. and Control 13 (1968), 541-554. Also part II, ibid. 14 (1969), 566-569.
- Neal Zierler, Primitive trinomials whose degree is a Mersenne exponent, Information and Control 15 (1969), 67β69. MR 244205
- Neal Zierler, On $x^{n}+x+1$ over $\textrm {GF}(2)$, Information and Control 16 (1970), 502β505. MR 271072
Additional Information
- © Copyright 1994 American Mathematical Society
- Journal: Math. Comp. 63 (1994), 389-401
- MSC: Primary 11B37; Secondary 11B39
- DOI: https://doi.org/10.1090/S0025-5718-1994-1216256-7
- MathSciNet review: 1216256