**Complementary-multiply-with-carry Generators**

Establishing the period of a lag-*r* MWC generator usually entails choosing multiplier *a* so that *p*=*ab**r* − 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* = *ab**r* − 1 may be difficult to factor.

But a prime of the form *p* = *ab**r* + 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* = *ab**r* + 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 *ab**r* + 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

*x*_{0},*x*_{1},*x*_{2}, ...,*x*_{r−1}, and*c*_{r − 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 *ab**r*+1, and the output *x'*s, in reverse order, will form the base *b* expansion of *j*/(*ab**r*+1) for some 0<*j*<*ab**r*.

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 *a*232762, about 109867 for these three *a*s: 109111 or 108798 or 108517.

With *b* = 232 and *a* = 3636507990, *p* = *ab*1359 − 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* = 15455296*b*42658 + 1. The order of *b* for that prime is 241489*21365056, about 10410928.

Read more about this topic: Multiply-with-carry