ON THE PERIODS OF GENERALIZED FIBONACCI RECURRENCES

We give a simple condition for a linear recurrence (mod 2w) of degree r to have the maximal possible period 2w-1(2r - 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 (mod 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.