5.4.3 Inversive Generators
We call LCGs and MRGs linear generators because they are defined by the linear modular polynomials [5.10] and [5.16]. As we have seen, such generators may suffer from poor lattice structures or strong correlations between pseudorandom numbers separated by large lags. Such problems can be avoided with nonlinear generators, an interesting category of which uses modular inversion to generate pseudorandom numbers.
We say that an integer 
, 0 ≤ < η, is the inverse of an integer b (mod η) if
- b = 1 (mod η) for b ≠ 0, and
- = 0 for b = 0.
If η is prime, the modular inverse is uniquely defined for any integer b. Modular inverses can be calculated using Fermat’s little theorem. This states that, if η is prime, and 0 < b < η,16 then
[5.19]
From this, it follows that the modular inverse of b is given by
[5.20]
The integer bη–2 can be calculated by multiplying b by itself η – 2 times, but for large η, it is worth simplifying this calculation. With the square and multiply method, we calculate bη–2 by calculating each quantity b, b2, b4, b8, … , 
, where 2α is the largest power of 2 for which 2α ≤ η – 1. With repeated squaring, all terms are obtained with just α multiplications. Then bη–2 is obtained by multiplying certain of the terms together. For example, b45 can be obtained as the product of b, b4, b8, and b32.
A form of inversive pseudorandom number generator, first proposed by Eichenauer and Lehn (1986), is the inversive congruential generator (ICG):
[5.21]
[5.22]
ICGs have been investigated for η a power of 2 or η a prime. The latter case performs best. In particular, ICGs with prime η yield pseudorandom numbers that have no lattice structures. Also, for prime η, ICGs can have periods as large as η. A simple ICG with period η is
[5.23]
A different form of inversive generator is the explicit inversive congruential generator (EICG) proposed by Eichenauer-Herrmann (1993) as
[5.24]
[5.25]
where η is prime, a is an integer, 0 < a < η, and k0 is a seed value. EICGs exhibit no lattice structures and always have period η. Also, jumping ahead to a specific point in a sequence of EICG numbers is as easy as advancing to another seed value. An example of an EICG is
[5.26]
Inversive generators, both ICGs and EICGs, are attractive because most forms exhibit no lattice structures. They do exhibit certain nonlinear patterns, but these are less likely to bias an application. Also, full-period inversive generators tend to be insensitive to choice of parameters. By comparison, with linear generators, it is necessary to carefully choose parameters to ensure good statistical properties.
A drawback of inversive generators is computational inefficiency. Because they must perform modular inversion, they tend to run more slowly than linear generators. For this reason, practitioners may reserve inversive generators for validating analyses performed with more traditional linear generators. Every generator has empirical tests it will fail. For this reason, it is a good idea to occasionally verify Monte Carlo results obtained using one generator by performing the same analysis with a second generator that has very different properties. The nonlinear properties of inversive generators make them excellent tools for verifying results obtained with linear generators.