We discuss three concepts of inversive methods, inversive congruential generators, explicit-inversive congruential generators, and combinations of these algorithms.
Inversive methods may be defined even for composite moduli. In view of their outstanding performance, we shall only consider prime moduli. Elaborate theoretical analysis has shown that the composite case is of little practical interest. We refer the reader to Niederreiter (1995a) for a comprehensive survey of these results.
For a given prime number p, and for 
, let 
if c=0 and 
if 
. In other words, 
equals the number 
modulo p.
Inversive congruential generators (``ICG'') are due to Eichenauer and Lehn (1986). We have to choose the modulus p, a multiplier a, an additive term b, and an initial value 
. Then the congruence
defines an inversive congruential generator. We denote this generator by
It produces a sequence 
in the set 
Pseudorandom numbers 
in [0,1[ are obtained by the normalization
A prominent feature of the ICG with prime modulus is the absence of any lattice structure, in sharp contrast to linear congruential generators (``LCG''). In the following scatter plot, all possible points (``nonoverlapping pairs'' of consecutive pseudorandom number s) 
, 
, in a region near the point (0.5, 0.5) are shown.
Figure 1: ICG(
, 1288490188, 1, 0)
The proper choice of the parameters a and b will be discussed in Section 3. An important feature of the ICG with respect to implementation is the ``mother-son'' principle, see Section 5.
Roughly speaking, the EICG is the ``easy-going brother'' of the ICG. It is due to Eichenauer-Herrmann (1993a). As we shall see, the EICG is easier to handle in practice, for example when producing independent substreams. The cost is a slightly smaller maximal sample size, as our empirical tests have shown, see Figure 6 in Section 4.
We choose a prime number p, a multiplier 
, 
, an additive term 
, and an initial value 
in 
. Then
defines a sequence of pseudorandom number s in As before, we put := 
, , to obtain pseudorandom number s in [0,1[. We shall denote this generator by
In the definition of EICG(
), the additive term b is superfluous. It is easy to see that the two generators EICG() and EICG(
), with
produce identical output. Hence, in most of our tests, we shall put b=0.
Eichenauer-Herrmann (1993b, 1994a) has introduced a simple technique to combine inversive generators, the compound approach.
Let 
be distinct prime numbers, each 
. For each index j, 
, let 
be a sequence of elements of 
that is purely periodic with period length 
. In other words,
Let 
denote the related sequence of pseudorandom number s in [0,1[, where
A sequence 
of compound pseudorandom number s in [0,1[ is defined by the congruence
It is elementary to see that the period of the sequence equals M:= 
We shall write cICG for a compound ICG and cEICG for a compound EICG.
The compound approach allows to combine ICG and EICG, provided they have full period. This method has important advantages: we may obtain very long periods easily, modular operations may be carried out with relatively small moduli, increasing the effectiveness of our computations, and the good correlation structure of the ICG and EICG is preserved. For the latter statement, see Section 3.
We present a scatter plot of a combined ICG, c(ICG(1031,55,1,0), ICG(1033,103,1,0), ICG(2027, 66,1,0)). All possible points , , have been computed. The period of this generator is M= 2158801621.
Figure 2: A Combined ICG with Three Components