Multiply-with-carry - Complementary-multiply-with-carry Generators

Complementary-multiply-with-carry Generators

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