CYCLIC PROPERTIES OF PSEUDO-RANDOM SEQUENCES OF MERSENNE PRIME RESIDUES

In Lehmer's multiplicative congruential procedure for generating a sequence of pseudo-random numbers, the modulus may be chosen as a Mersenne prime of the form, M//p equals 2**p minus 1, and one of its primitive roots used as the constant multiplier to ensure a maximal sequence. Cyclic properties of the sequence entail perfect negative correlation between halves of the sequence and other relationships which limit the useful sequence length. A primitive root is shown to be characterized by a set of non-trivial roots of unity (mod M//p), which is used to identify a primitive root, and properties of finite rings of such roots are used to generate further primitive roots. Computer procedures to facilitate these operations are indicated and applied to production of pseudo-random n-tuples designed to overcome the restrictions on randomness of single generator n-tuples, noted in the literature.