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 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 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