On the Periods of Generalized Fibonacci Recurrences
Richard P. Brent · Mathematics of Computation · 1994
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.