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:
Contents
- Period
- Example
- Compound Inversive Generator
- Advantages of CIG
- Discrepancy and its boundaries
- Definition
- Notations
- Higher bound
- Lower bound
- References
Such a generator is denoted symbolically as ICG(q,a,c,seed) and is said to be an ICG with parameters q,a,c and seed seed.
Period
The sequence
Example
ICG(5,2,3,1) gives the sequence:(1,0,3,2,4,1,.....) (as in
Compound Inversive Generator
The construction of a Compound Inversive Generator (CIG) relies on combining two or more congruential inversive generators according to the method described below.
Let
For each index j, 1≤ j ≤ r, we consider
The sequence
The compound approach allows combining Inversive Congruential Generators, provided they have full period, in parallel generation systems.
Example
Let
Advantages of CIG
The CIG are accepted for practical purposes for a number of reason.
Firstly, binary sequences produced in this way are free of undesirable statistical deviations. Inversive sequences extensively tested with variety of statistical tests remain stable under the variation of parameter.
Secondly, there exists a steady and simple way of parameter choice, based on the Chou algorithm that guarantees maximum period length.
Thirdly, compound approach has the same properties as single inversive generators but it also provides period length significantly greater than obtained by a single Inversive Congruential Generator. They seem to be designed for application with multiprocessor parallel hardware platforms.
There exists an algorithm which allows designing compound generators with predictable period length, predictable linear complexity level, with excellent statistical properties of produced bit streams.
The procedure of designing this complex structure starts with defining finite field of p elements and ends with choosing the parameters a and c for each Inversive Congruential Generator being the component of the compound generator. It means that each generator is associated to a fixed IMP polynomial. Such a condition is sufficient for maximum period of each Inversive Congruential Generator and finally for maximum period of the compound generator. The construction of IMP polynomials is the most efficient approach to find parameters for Inversive Congruential Generator with maximum period length.
Discrepancy and its boundaries
Equidistribution and statistical independence properties of the generated sequences, which are very important for their usability in a stochastic simulation, can be analyzed based on the discrepancy of s-tuples of successive pseudorandom numbers with
The discrepancy computes the distance of a generator from a uniform one, a low discrepancy means that the sequence generated can be used for cryptographic purposes and the first aim of the Inversive congruential generator is to provide pseudorandom numbers.
Definition
For N arbitrary points
Until now, we had sequences of integers from 0 to
From this definition, we can say that if the sequence
Notations
Some further notation is necessary. For integers
Define
and
for
Higher bound
Let
Then the discrepancy of the points
Lower bound
The discrepancy of
for any nonzero lattice point
These two theorems show that the CIG is not perfect because the discrepancy is greater strictly than a positive value but also the CIG is not the worst generator as the discrepancy is lower than a value less than 1.
There exist also theorems which bound the average value of the discrepancy for Compound Inversive Generators and also ones which take values such that the discrepancy is bounded by some value depending on the parameters. For more details see the original paper.