On the periods of generalized Fibonacci recurrences

Abstract

We give a simple condition for a linear recurrence (mod 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 pseudo-random number generation, i.e. for 3-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.

13 pages. An old Technical Report, submitted for archival purposes. For further details, see http://wwwmaths.anu.edu.au/~brent/pub/pub133.html