2 Random numbers

2.6 Maximal periods for the congruential methods

We have

        Xi+1 = aXi+c (mod m)
        Xi+2 = aXi+1+c (mod m)
            = a2Xi+c(a+1) (mod m)

Continuing in this way we obtain

        Xi+k = akXi+c(ak-1+ak-2+...+1) (mod m)
             = akXi+c(ak-1)/(a-1) (mod m)

For c=0 we have

        Xk = akX0 (mod m)

In order to simplify the analysis we choose X₀=a. We may then conclude that one requirement for maximal period is that a,a²,...,a^k (mod m) should be different for as large k as possible. This is the case if a is a so called primitive element (mod m), see Knuth.

When m is a prime then the maximal period is m-1, i.e., all numbers except zero can be generated. For non prime m the maximal period is smaller. For instance for m=100 only odd or even numbers are generated depending on if a is odd or even so an upper bound is 50. In fact the maximal period is 20, so the generator illustrated in Section 2.4 has maximal period.

For the mixed congruential method the maximal period is the largest possible, m.

Necessary conditions for maximal length of the period are known for the congruential methods. As an example we have the following theorem (Knuth):

Theorem: If m=10^e, e>=5, c=0 and X₀ is not a multiple of 2 or 5, the period of the linear congruential sequence is 5·10^e-2 if and only if a (mod 200) equals one of the following 32 values:

3, 11, 13, 19, 21, 27, 29, 37, 53, 59, 61, 67, 69, 77, 83, 
91, 109, 117, 123, 131, 133, 139, 141, 147, 163, 171, 173, 
179, 181, 187, 189, 197.