The period of the Fibonacci random number generator

AbstractSmith, Green, and Klem introduced the Fibonacci RNG in [7]. A starting vector of k integers is chosen, and new numbers are generated by the recurrence rn≡rn−1+rn−k (mod M). For a prime M and some choices of the parameter k, any non-zero initial vector υ gives a sequence with a period of Mkminus;1. However, in most cases, different initial values give rise to very different periods. This behavior was noted by the authors, but left unexplained. In this paper we review how sequences with short periods arise, and provide an algorithm that selects different starting vectors that give a maximal period