## 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, - 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, - 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, - 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, - 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, - 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, - 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**

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

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

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

*Ganzzahlige Potenzreihen und linear rekurrente Zahlenfolgen*, Issai Schur Gesammelte Abhandlungen, Band 3, Springer-Verlag, Berlin, 1973, pp. 400-421.

*Algebra*, Vol. 1, Chapter 7 (English transl. by Fred Blum, 5th ed.), Ungar, New York, 1953.

*On primitive trinomials*$\pmod 2$, Inform. and Control

**13**(1968), 541-554. Also part II,

*ibid*.

**14**(1969), 566-569.

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