thumb|alt=A visualization of the algorithm.

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:

: <math>x_0 = \text{seed},</math>

: <math>x_{i+1} = \begin{cases}

(ax_i^{-1} + c) \bmod q & \text{if } x_i \ne 0, \\

c & \text{if } x_i = 0.

\end{cases}

</math>

Such a generator is denoted symbolically as and is said to be an ICG with parameters q, a, c and seed seed.

Period

The sequence <math>(x_n)_{n\geq 0}</math> must have <math>x_i = x_j</math> after finitely many steps, and since the next element depends only on its direct predecessor, also <math>x_{i+1} = x_{j+1}</math> 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 <math>f(x) = x^2 - cx - a \in \mathbb F_q[x]</math> (polynomial ring over <math>\mathbb F_q</math>) is primitive. This is not a necessary condition; there are choices of q, a and c for which <math>f(x)</math> 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.

  • Inversive Generators at the University of Salzburg.