On the periods of generalized Fibonacci recurrences

Brent, Richard P.

doi:10.1090/S0025-5718-1994-1216256-7

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

On the periods of generalized Fibonacci recurrences

Uniform random number generators for supercomputers

Monte Carlo simulations

Hidden errors from "good" random number generators

69

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

A current view of random number generators

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

Analysis of additive random number generators

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

Ganzzahlige Potenzreihen und linear rekurrente Zahlenfolgen

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

Algebra

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

On primitive trinomials

13

ibid

14

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