On the periods of generalized Fibonacci recurrences
133. R. P. Brent,
On the periods of generalized Fibonacci recurrences,
Mathematics of Computation 63 (1994), 389-401.
Also Technical Report TR-CS-92-03 (March 1992, revised March 1993),
We give a simple condition for a linear recurrence
of degree r
to have the maximal possible period
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.
The result has applications to uniform random number
generators with good statistical properties and extremely
long periods .
Go to next publication
Return to Richard Brent's index page