Establishing the period of a lag-r MWC generator usually entails choosing multiplier a so that p=abr − 1 is prime. If p is a safe prime, then the order of b will be p − 1 or (p − 1)/2. Otherwise, it is likely that p − 1 will have to be factored in order to find the order of b mod p, and p = abr − 1 may be difficult to factor.
But a prime of the form p = abr + 1 will make p−1 easy to factor, so a version of multiply-with-carry that involves the order of b for a prime p = abr + 1 would reduce considerably the computational number theory required to establish the period of a MWC sequence.
Fortunately, a slight modification of the MWC procedure leads to primes of the form abr + 1. The new procedure is called complementary-multiply-with-carry (CMWC),
and the setup is the same as that for lag-r MWC: multiplier a, base b, r + 1 seeds
- x0, x1, x2, ..., xr−1, and cr − 1.
There is a slight change in the generation of a new pair (x, c):
That is, take the complement, (b−1)−x, when forming the new x.
The resulting sequence of x's produced by the CMWC RNG will have period the order of b in the multiplicative group of residues modulo abr+1, and the output x's, in reverse order, will form the base b expansion of j/(abr+1) for some 0<j<abr.
Use of lag-r CMWC makes it much easier to find periods for r's as large as 512, 1024, 2048, etc. (Making r a power of 2 makes it slightly easier (and faster) to access elements in the array containing the r most recent x's.)
Some examples: With b=232, the period of the lag-1024 CMWC
will be a232762, about 109867 for these three as: 109111 or 108798 or 108517.
With b = 232 and a = 3636507990, p = ab1359 − 1 is a safe prime, so the MWC sequence based on that a has period 3636507990243487 1013101.
With b = 232, a CMWC RNG with near record period may be based on the prime p = 15455296b42658 + 1. The order of b for that prime is 241489*21365056, about 10410928.
Read more about this topic: Multiply-with-carry