Guaranteeing the period of linear recurring sequences (mod 2e)
A.D. Barnard, J.R. Silvester, W.G. Chambers · IEE Proceedings E Computers and Digital Techniques · 1993
Linear congruential recurrence relations modulo 2e are a very obvious way of producing pseudorandom integer sequences on digital signal processors. The maximum value possible for the period of such a sequence generated by an nth-order relation is (2n−l)2e−1. Such a relation can be specified by an nth-degree feedback polynomial f(x) with e-bit coefficients. Necessary conditions for the period to be maximal are that at least one of the initialising values should be odd and that f(x) (mod 2) should be a primitive nth-degree polynomial. These conditions are not sufficient, and there is an extra condition needed on f(x) (mod 4). This condition is here expressed in a form simple enough to verify that large classes of polynomials will give the maximum period. For example (subject to f(x) (mod 2) being primitive) f(x) can be any pentanomial with odd coefficients and degree n>5, or any trinomial with odd coefficients and odd degree n. Other large classes of suitable polynomials are described. In many cases we may determine by inspection whether f(x) will give the maximal period. These results make it simple, for example, to set up quite distinct recurrence relations to act as independent pseudorandom number generators.