Inversive congruential generators are a type of nonlinear congruential pseudorandom number generator, which use the modular multiplicative inverse (if it exists) to generate the next number in a sequence. The standard formula for an inversive congruential generator, modulo some prime q is:
Such a generator is denoted symbolically as and is said to be an ICG with parameters q, a, c and seed seed.
The sequence must have after finitely many steps, and since the next element depends only on its direct predecessor, also etc. The maximum possible period for the modulus q is q itself, i.e. the sequence includes every value from 0 to q − 1 before repeating.
A sufficient condition for the sequence to have the maximum possible period is to choose a and c such that the polynomial (polynomial ring over ) is primitive. This is not a necessary condition; there are choices of q, a and c for which is not primitive, but the sequence nevertheless has a period of q. Any polynomial, primitive or not, that leads to a maximal-period sequence is called an inversive maximal-period (IMP) polynomial. Chou describes an algorithm for choosing the parameters a and c to get such polynomials.
Eichenauer-Herrmann, Lehn, Grothe and Niederreiter have shown that inversive congruential generators have good uniformity properties, in particular with regard to lattice structure and serial correlations.
ICG(5, 2, 3, 1) gives the sequence 1, 0, 3, 2, 4, 1, 0, 3, 4, 2, 1, 0, ...
In this example, is irreducible in , as none of 0, 1, 2, 3 or 4 is a root. It can also be verified that x is a primitive element of and hence f is primitive.
The construction of a compound inversive generator (CIG) relies on combining two or more inversive congruential generators according to the method described below.
Let be distinct prime integers, each . For each index j, 1 ≤ j ≤ r, let be a sequence of elements of periodic with period length
In other words, .
For each index j, 1 ≤ j ≤ r, we consider , where is the period length of the following sequence .
