Inversive congruential generator
Encyclopedia
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:
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.
must have 
after finitely many steps and since the next element depends only on its direct predecessor also 
etc. The maximum length that the period
T for a function modulo q can have is . If the polynomial
(polynomial ring over 
) is primitive
, then the sequence will have the maximum length.
Such polynomials are called inversive maximal period (IMP) polynomials. The sufficient condition for maximum sequence period is a proper choice of parameters a and c according to the algorithm
described in.
Eichenauer-Herrmann, Lehn, Grothe and Niederreiter have shown that inversive congruential generators have good uniformity properties, in particular with regard to lattice structure and serial correlations.
(as in
, 1 and 4 are their own inverse, 2 is the inverse of 3 and conversely).
In this example
is irreducible in 
as neither 0,1,2,3 or 4 are roots, and therefore the period is equal to .In order to show that f is primitive one should show that x is a primitive element of 
.
Let
be distinct prime integers, each 
. For each index j,1≤ j ≤ r, let 
be a sequence of elements of 
, that is periodic with period length
. In other words,
.
For each index j, 1≤ j ≤ r, we consider
where 
is the period length of the following sequence 
.
The sequence
of compound pseudorandom numbers is defined as the sum
.
The compound approach allows combining Inversive Congruential Generators, provided they have full period, in parallel generation systems.
and 
. To simplify, take 
and 
. We compute for every 1≤ j≤ 35, 
then
(we have to do the 35 different sums to obtain 0+0 and we begin the same sequence again, the period is
).
This method allows obtaining very long period and modular operations may be carried out with relatively small moduli.
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.
, can be analyzed based on the discrepancy of s-tuples of successive pseudorandom numbers with
and 
respectively.
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.
arbitrary points 
the discrepancy is defined by
,
where the supremum is extended over all subintervals
of 
, 
is 
times the number of points among
falling into J and V(J) denotes the s-dimensional volume of J.
Until now, we had sequences of integers from 0 to T-1, in order to have sequences of
, one can divide a sequences of integers by its period T.
From this definition, we can say that if the sequence
is perfectly random then its well distributed on the interval 
then 
and all points are in J so 
hence
but instead if the sequence is concentrated close to one point then the subinterval J is very small 
and 
so 
Then we have from the better and worst case:
.
and 
let 
be the set of nonzero lattice points 
with 
for 
.
Define
and
for
. For real 
the abbreviation 
is used, and 
stands for the standard inner product of 
.
and 
be integers. Let 
with 
for 
.
Then the discrepancy of the points
satisfies
arbitrary points 
satisfies
for any nonzero lattice point
, where 
denotes the number of nonzero coordinates of 
.
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 .
Pseudorandom number generator
A pseudorandom number generator , also known as a deterministic random bit generator , is an algorithm for generating a sequence of numbers that approximates the properties of random numbers...
, 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:
 seed |
|
 |
if  |
 |
if  |
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 must have after finitely many steps and since the next element depends only on its direct predecessor also etc. The maximum length that the periodPeriodic function
In mathematics, a periodic function is a function that repeats its values in regular intervals or periods. The most important examples are the trigonometric functions, which repeat over intervals of length 2π radians. Periodic functions are used throughout science to describe oscillations,...
T for a function modulo q can have is . If the polynomial
Polynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
(polynomial ring over ) is primitivePrimitive
Primitive may refer to:* Anarcho-primitivism, an anarchist critique of the origins and progress of civilization* Primitive culture, one that lacks major signs of economic development or modernity...
, then the sequence will have the maximum length.
Such polynomials are called inversive maximal period (IMP) polynomials. The sufficient condition for maximum sequence period is a proper choice of parameters a and c according to the algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
described in.
Eichenauer-Herrmann, Lehn, Grothe and Niederreiter have shown that inversive congruential generators have good uniformity properties, in particular with regard to lattice structure and serial correlations.
Example
ICG(5,2,3,1) gives the sequence:(1,0,3,2,4,1,.....)(as in
, 1 and 4 are their own inverse, 2 is the inverse of 3 and conversely).In this example
is irreducible in as neither 0,1,2,3 or 4 are roots, and therefore the period is equal to .In order to show that f is primitive one should show that x is a primitive element of .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
be distinct prime integers, each . For each index j,1≤ j ≤ r, let be a sequence of elements of , that is periodic with period length. In other words,.For each index j, 1≤ j ≤ r, we consider
where is the period length of the following sequence .The sequence
of compound pseudorandom numbers is defined as the sum.The compound approach allows combining Inversive Congruential Generators, provided they have full period, in parallel generation systems.
Example:
Let and . To simplify, take and . We compute for every 1≤ j≤ 35, then
(we have to do the 35 different sums to obtain 0+0 and we begin the same sequence again, the period is
).This method allows obtaining very long period and modular operations may be carried out with relatively small moduli.
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 bounderies
Equidistribution and statistical independence properties of the generated sequences, which are very important for their usability in a stochastic simulationStochastic process
In probability theory, a stochastic process , or sometimes random process, is the counterpart to a deterministic process...
, can be analyzed based on the discrepancy of s-tuples of successive pseudorandom numbers with
and respectively.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
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
purposes and the first aim of the Inversive congruential generator is to provide pseudorandom numbers.
Definition
For arbitrary points the discrepancy is defined by,where the supremum is extended over all subintervals
of , is times the number of points among falling into J and V(J) denotes the s-dimensional volume of J.Until now, we had sequences of integers from 0 to T-1, in order to have sequences of
, one can divide a sequences of integers by its period T.From this definition, we can say that if the sequence
is perfectly random then its well distributed on the interval then and all points are in J so hence but instead if the sequence is concentrated close to one point then the subinterval J is very small and so Then we have from the better and worst case:
.Notations
Some further notation is necessary. For integers and let be the set of nonzero lattice points with for .Define
and
for
. For real the abbreviation is used, and stands for the standard inner product of .Higher bound
Let and be integers. Let with for .Then the discrepancy of the points
satisfies-
≤ 
+ 
Lower bound
The discrepancy of arbitrary points satisfies-
≥ 
for any nonzero lattice point
, where denotes the number of nonzero coordinates of .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 .
See also
- Pseudorandom number generatorPseudorandom number generatorA pseudorandom number generator , also known as a deterministic random bit generator , is an algorithm for generating a sequence of numbers that approximates the properties of random numbers...
- List of random number generators
- Linear congruential generatorLinear congruential generatorA Linear Congruential Generator represents one of the oldest and best-known pseudorandom number generator algorithms. The theory behind them is easy to understand, and they are easily implemented and fast....
- Generalized inversive congruential pseudorandom numbersGeneralized inversive congruential pseudorandom numbersAn approach to nonlinear congruential methods of generating uniform pseudorandom numbers in the interval [0,1) is the Inversive congruential generator with prime modulus...
- Naor-Reingold Pseudorandom Function
External links
- Inversive Generators at the University of SalzburgUniversity of SalzburgThe University of Salzburg, or Paris Lodron University after its founder, the Prince Archbishop Paris Lodron, is located in the Austrian city of Salzburg, Salzburgerland, home of Mozart. It is divided into 4 faculties: catholic theology, law, humanities and natural science.Founded in 1622, it...
.