GUARANTEEING THE PERIOD OF LINEAR RECURRING SEQUENCES (MOD(2E))

Linear congruential recurrence relations modulo 2e are a very obvious way of producing pseudorandom integer sequences on digital signal proc essors. The maximum value possible for the period of such a sequence g enerated by an nth-order relation is (2n - 1)2e-1. Such a relation can be specified by an nth-degree feedback polynomial f(x) with e-bit coe fficients. Necessary conditions for the period to be maximal are that at least one of the initialising values should be odd and that f(x) (m od 2) should be a primitive nth-degree polynomial. These conditions ar e 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 e xample (subject to f(x) (mod 2) being primitive) f(x) can be any penta nomial with odd coefficients and degree n > 5, or any trinomial with o dd coefficients and odd degree n. Other large classes of suitable poly nomials are described. In many cases we may determine by inspection wh ether 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.