Inversive congruential generator

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 is

x₀=seed

x_i+1 ≡ (ax_i^-1 + c) mod q if x_i≠0 where 0<x_i<q and q prime.

x_i+1=c if x_i=0

Such a generator is denoted symbolically as ICG(q,a,c,seed) and is said to be ICG with parameter q,a,c and seed.

Example:

The ICG(5,2,3,1) gives the sequence:(1,0,3,2,4,1,.....) (as in $\in \mathbb {F} _{5}$, 1 and 4 are their own inverse, 2 is the inverse of 3 and conversely).

For the sequence (x_n)_n≥0 ,its periods length T is maximum if T=q.If the polynomial f(x)=x²-cx-a $\in \mathbb {F} _{q}[x]$(polynomial ring over $\in \mathbb {F} _{q}$) is primitive then sequences have the maximum length.
In our example f(x)=x²-3x-2 is irreducible in $\in \mathbb {F} _{5}[x]$ as neither 0,1,2,3 or 4 are root of it and the period of our sequence is maximum equals to q=5.In order to show that f is primitive one should show that x is a primitive element of $\in \mathbb {F} _{5}[x]/(f)$.
Such polynomial are called IMP polynomial (for Inversive Maximal Period).The sufficient condition for maximum sequence period is a proper choice of parameter a and c according to the algorithm described in .
Eichenauer,Lehn,Grothe and Niederreiter have shown that the inversive congruential generator have good uniformity properties,in particular with regard to lattice structure and serial correlations.

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 p₁,...,p_r be distinct prime integers,each p_j ≥ 5.For each index j,1≤ j ≤ r,let (x_n)_n≥0 be a sequence of elements of $\in \mathbb {F} _{p_{j}}$, that is periodic with period length p_j.In other words,{x_n^(j) | 0 ≤ n ≤ p_j}=$\in \mathbb {F} _{p_{j}}$.
For each index j, 1≤ j ≤ r, we consider T_j=T/p_j where T=p₁*...*p_r is the period length of the following sequence (x_n)_n≥0.
The sequence (x_n)_n≥0 of compound pseudorandom numbers is defined as the sum

x_n=T₁x_n⁽¹⁾+T₂ x_n⁽²⁾+... +T_rx_n^(r) mod T.

The compound approach allows combining Inversive Congruential Generators, provided they have full period, in parallel generation systems.

Example:

Let p₁=5 and p₂ =7 (r =2).To simplify, let take (x_n⁽¹⁾)_n≥0 = (0,1,2,3,4,...) and (x_n⁽²⁾)_n≥0 =(0,1,2,3,4,5,6,...).We compute for every 1≤ j≤ 35, x_j=7x_j⁽¹⁾+5x_j⁽²⁾ mod 35

then (x_n)_n≥0=(0, 12, 24, 1, 13, 25, 2, 14, 26, 3, 15, 27, 4, 16, 28, 5, 17, 29, 6, 18, 30, 7, 19, 31, 8, 20, 32, 9, 21, 33, 10, 22, 34, 11, 23)
(we have to do the 35 different sums to obtain 0+0 and rebegin the same sequence again,the period is well $5\times 7=35\,$).
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 steady and simple way of parameter choice,based on the Chou algorithm .It guarantees maximum period length.
Thirdly,compound approach gives the same properties of produced sequences as single inversive generators .Compound Inversive Generator allow obtaining period length significantly greater than obtained by a single Inversive Congruential Generator.They seem to be designed fo application with multiprocessor parallel hardware platforms.

There exists an algorithm which allows designing compound generator 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 with each generator is associated 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 polynomial is the most efficient approach to find parameters for Inversive Congruential Generator with maximum period length.

Discrepancy and results

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 s=1 and s=2 respectively.

Definition

For N arbitrary points t₁,...,t_N-1 ∈ [0,1)^s the discrepancy is defined by

D_N(t₁,...,t_N-1)=sup_J |F_N(J) – V(J)|,

where the supremum is extended over all subintervals J of [0,1)^s , F_N (J) is N^-1 times the number of points among t₁,...,t_N-1 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 [0,1)^s, one can divide its sequences of integers by the period T.
From this definition, we can say that if the sequence t₁,...,t_N-1 is perfectly random then its well distributed on the interval J=[0,1)^s then V(J)=1 and all points are in J so F_N(J)=N/N=1 hence D_N(t₁,...,t_N-1)=0 but instead if the sequence is concentrated close to one point then the subinterval J is very small V(j)≈0 and F_N(j)≈N/N≈1 so D_N(t₁,...,t_N-1)=1.
Then we have from the better and worst case: 0≤ D_N(t₁,...,t_N-1) ≤ 1

First Results

Some further notation is necessary. For integers k ≥1 and q ≥2 let C_k(q) be the set of nonzero lattice points (h₁,...,h_k) ∈ Z^k with -q/2< h_j< q/2 for 1≤ j ≤ k.

Define

$r(h,q)={\begin{cases}q\sin(\pi |h|/q)&{\text{for }}h\in C_{1}(q)\\1&{\text{for }}h=0\end{cases}}$

and

$r(\mathbf {h} ,q)=\prod _{j=1}^{k}r(h_{j},q)$

for h=(h₁,...,h_k) ∈ C_k(q).For real t the abbreviation e(t)=exp(2π*it)is used, and u•v stands for the standard inner product of u,v in R^k

Theorem 1

Let N ≥1 and q ≥2 be integers. Let t_n = y_n/q ∈ [0,1)^k with y_n ∈ {0,1,...q-1}^k for 0≤ n< N.

Then the discrepancy of the points t₀ ,..., t_N-1 satisfies

$D_{N}(\mathbf {t} _{0},\mathbf {t} _{1}...,\mathbf {t} _{N-1})$ ≤ ${\frac {k}{q}}$ + ${\frac {1}{N}}$ $\sum _{h\in \mathbb {C} _{k}(q)}$${\frac {1}{r(\mathbf {h} ,q)}}{\Bigg |}\sum _{n=0}^{N-1}e(\mathbf {h} \cdot \mathbf {t} _{n}){\Bigg |}$

Theorem 2

The discrepancy of N arbitrary points t₁,...,t_N-1 ∈ [0,1)^k satisfies

$D_{N}(\mathbf {t} _{0},\mathbf {t} _{1}...,\mathbf {t} _{N-1})$ ≥ ${\frac {\pi }{2N((\pi +1)^{l}-1)\prod _{j=1}^{k}max(1,h_{j})}}{\Bigg |}\sum _{n=0}^{N-1}e(\mathbf {h} \cdot \mathbf {t} _{n}){\Bigg |}$

for any nonzero lattice point h=(h₁,...,h_k) ∈ Z^k where l denotes the number of nonzero coordinates of h.

These two theorem show that the CIG is not perfect as 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 as one can see.

There exists also theorems which bound the average value of the discrepancy for Compound Inversive Generator and also ones which denumber values such that the discrepancy is bounded by some value depending on the parameters.For more details see the clear paper .

See also

• Pseudorandom number generator
• List of random number generators
• Linear congruential generator
• Generalized Inversive Congruential Pseudorandom Numbers
• Naor-Reingold Pseudorandom Function

External links

• Inversive Generators at the University of Salzburg.