An approach to nonlinear congruential methods of generating uniform pseudorandom numbers in the interval [0,1) is the Inversive congruential generator with prime modulus.
A generalization for arbitrary composite moduli
with arbitrary distinct primes
with gcd (a,m) = 1 a generalized inversive congruential sequence
denotes the number of positive integers less than m which are relatively prime to m. Let take m = 15 =
is not maximum.
The result below shows that these sequences are closely related to the following inversive congruential sequence with prime moduli.
be a sequence of elements of
be defined as above.
Then This theorem shows that an implementation of Generalized Inversive Congruential Generator is possible, where exact integer computations have to be performed only in
Proof: First, observe that
which will be shown on induction on
Then straightforward calculations and Fermat's Theorem yield which implies the desired result.
Generalized Inversive Congruential Pseudorandom Numbers are well equidistributed in one dimension.
A reliable theoretical approach for assessing their statistical independence properties is based on the discrepancy of s-tuples of pseudorandom numbers.
of Generalized Inversive Congruential Pseudorandom Numbers for
Higher bound Lower bound: For a fixed number r of prime factors of m, Theorem 2 shows that
for any Generalized Inversive Congruential Sequence.
In this case Theorem 3 implies that there exist Generalized Inversive Congruential Generators having a discrepancy
which is at least of the order of magnitude
However, if m is composed only of small primes, then r can be of an order of magnitude
ϵ
ϵ > 0
[1] Therefore, one obtains in the general case
2 + ϵ
ϵ > 0
, similar arguments imply that in the general case the lower bound in Theorem 3 is at least of the order of magnitude
It is this range of magnitudes where one also finds the discrepancy of m independent and uniformly distributed random points which almost always has the order of magnitude
according to the law of the iterated logarithm for discrepancies.
[2] In this sense, Generalized Inversive Congruential Pseudo-random Numbers model true random numbers very closely.