## 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.
MR 94i:11012.
Also Technical Report TR-CS-92-03 (March 1992, revised March 1993),
13 pp.
arXiv:1004.5439v1
Abstract:
dvi (3K),
pdf (74K),
ps (25K).

Paper:
pdf (1078K).

Technical Report:
dvi (23K),
pdf (198K),
ps (83K).

## 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.
## Comments

The result has applications to uniform random number
generators with good statistical properties and extremely
long periods [132].
Go to next publication

Return to Richard Brent's index page