On the Periods of Generalized Fibonacci Recurrences

We give a simple condition for a linear recurrence <!-- MATH $\pmod {2^w}$ --> of degree r to have the maximal possible period <!-- MATH ${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 and of degree 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.