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


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.


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