Editing Inversive congruential generator

[[File:ICGexample.png|thumb|alt=A visualization of the algorithm.]]
'''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:
: <math>x_0 = \text{seed},</math>
: <math>x_{i+1} = \begin{cases}
 (ax_i^{-1} + c) \bmod q & \text{if } x_i \ne 0, \\
 c & \text{if } x_i = 0.
\end{cases}
</math>
Such a generator is denoted symbolically as {{nobr|ICG(''q'', ''a'', ''c'', ''seed'')}} and is said to be an ICG with parameters ''q'', ''a'', ''c'' and seed ''seed''.

==Period==
The sequence <math>(x_n)_{n\geq 0}</math> must have <math>x_i = x_j</math> after finitely many steps, and since the next element depends only on its direct predecessor, also <math>x_{i+1} = x_{j+1}</math> etc. The maximum possible [[periodic function|period]] for the modulus ''q'' is ''q'' itself, i.e. the sequence includes every value from 0 to ''q'' − 1 before repeating.

A sufficient condition for the sequence to have the maximum possible period is to choose ''a'' and ''c'' such that the [[polynomial]] <math>f(x) = x^2 - cx - a \in \mathbb F_q[x]</math> (polynomial ring over <math>\mathbb F_q</math>) is [[Primitive polynomial (field theory)|primitive]]. This is not a necessary condition; there are choices of ''q'', ''a'' and ''c'' for which <math>f(x)</math> is not primitive, but the sequence nevertheless has a period of ''q''. Any polynomial, primitive or not, that leads to a maximal-period sequence is called an inversive maximal-period (IMP) polynomial. Chou describes an [[algorithm]] for choosing the parameters ''a'' and ''c'' to get such polynomials.<ref name="one"/>

Eichenauer-Herrmann, Lehn, Grothe and [[Harald Niederreiter|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, 0, 3, 2, 4, 1, 0, ...

In this example, <math>f(x) = x^2 - 3x - 2</math> is irreducible in <math>\mathbb F_5[x]</math>, as none of 0, 1, 2, 3 or 4 is a root. It can also be verified that ''x'' is a [[primitive element (finite field)|primitive element]] of <math>\mathbb F_5[x]/(f)</math> and hence ''f'' is primitive.

==Compound inversive generator==
The construction of a '''compound inversive generator''' (CIG) relies on combining two or more inversive congruential generators according to the method described below.

Let <math>p_1, \dots, p_r</math> be distinct prime integers, each <math>p_j \geq 5</math>. For each index ''j'', ''1'' ≤ ''j'' ≤ ''r'', let <math>(x_n)_{n\geq 0}</math> be a sequence of elements of <math>\mathbb F_{p_j}</math> periodic with period length
<math>p_j</math>. In other words, <math>\{x_n^{(j)} \mid 0 \leq n \leq p_j\} \in \mathbb F_{p_j}</math>.

For each index ''j'', 1 ≤ ''j'' ≤ r, we consider <math>T_j = T/p_j</math>, where <math>T = p_1 \cdots p_r</math> is the period length of the following sequence <math>(x_n)_{n\geq 0}</math>.

The sequence <math>(x_n)_{n\geq 0}</math> of compound pseudorandom numbers is defined as the sum
: <math>x_n = \left(T_1 x_n^{(1)} + T_2 x_n^{(2)} + \dots + T_r x_n^{(r)}\right) \bmod T</math>.
The compound approach allows combining inversive congruential generators, provided they have full period, in parallel generation systems.

==Advantages of CIG==
The CIG are accepted for practical purposes for a number of reasons.

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.<ref name="two"/><ref name="three"/><ref name="four"/>

Secondly, there exists a steady and simple way of parameter choice, based on the Chou algorithm<ref name="one"/> that guarantees maximum period length.

Thirdly, compound approach has the same properties as single inversive generators,<ref name="five"/><ref name="six"/> 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<ref name="seven"/> that 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<ref name="eight"/> 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 process|stochastic simulation]], can be analyzed based on the ''discrepancy'' of ''s''-tuples of successive pseudorandom numbers with <math>s = 1</math> and <math>s = 2</math> 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 [[cryptography|cryptographic]] purposes, and the first aim of the inversive congruential generator is to provide pseudorandom numbers.

==Definition==
For {{mvar|N}} arbitrary points <math>{\mathbf t}_1, \dots , {\mathbf t}_{N-1}\in [0,1)</math> the discrepancy is defined by
<math>D_N({\mathbf t}_1, \dots , {\mathbf t}_{N-1})={\rm sup}_J|F_N(J)- V(J)|</math>,
where the supremum is extended over all subintervals {{mvar|J}} of <math>[0,1)^s</math>, <math>F_N(J)</math> is <math>N^{-1}</math> times the number of points among
<math> {\mathbf t}_1, \dots , {\mathbf t}_{N-1}</math> falling into {{mvar|J}} and {{tmath|V(J)}} denotes the {{mvar|s}}-dimensional volume of {{mvar|J}}.

Until now, we had sequences of integers from 0 to {{tmath|T-1}}, in order to have sequences of <math>[0,1)^s</math>, one can divide a sequences of integers by its period {{mvar|T}}.

From this definition, we can say that if the sequence <math>{\mathbf t}_1, \dots , {\mathbf t}_{N-1} </math> is perfectly random then its well distributed on the interval <math>J=[0,1)^s</math> then <math>V(J)=1</math> and all points are in {{mvar|J}} so <math>F_N(J)=N/N=1</math> hence
<math>D_N({\mathbf t}_1, \dots , {\mathbf t}_{N-1})=0</math> but instead if the sequence is concentrated close to one point then the subinterval {{mvar|J}} is very small <math>V(j)\approx 0</math> and <math>F_N(j)\approx N/N\approx 1</math> so <math>D_N({\mathbf t}_1, \dots , {\mathbf t}_{N-1})=1</math>
Then we have from the better and worst case: 
:<math>0\leq D_N({\mathbf t}_1, \dots , {\mathbf t}_{N-1})\leq 1</math>.

==Notations==
Some further notation is necessary. For integers <math>k\geq 1 </math> and <math>q\geq 2</math> let <math>C_k(q)</math> be the set of nonzero lattice points <math>(h_1,\dots ,h_k)\in Z^k</math> with <math>-q/2< h_j< q/2</math> for <math>1\leq j \leq k</math>.

Define

:<math>r(h,q)= \begin{cases}
q \sin (\pi|h|/q)&\text{for }h \in C_{1}(q)\\
1 &\text{for }h = 0

\end{cases}</math>

and                
:<math>
r (\mathbf{h},q)=\prod_{j=1}^k r(h_j,q)
</math>
for <math>{\mathbf h} =(h_1,\dots ,h_k) \in C_k(q)</math>. For real <math>t</math> the abbreviation <math>e(t)={\rm exp}(2\pi\cdot it)</math> is used, and <math>u\cdot v</math> stands for the standard inner product of <math>u,v</math> in <math>R^k</math>.

==Higher bound==
Let <math>N \geq 1</math> and <math>q \geq 2</math> be integers. Let <math>{\mathbf t}_n= y_n/q \in [0,1)^k</math> with <math>y_n \in \{0,1,\dots ,q-1\}^k</math> for <math>0\leq n< N</math>. 

Then the discrepancy of the points  <math>{\mathbf t}_0 ,\dots ,{\mathbf t}_{N-1}</math>  satisfies

:          <math>D_N (\mathbf{t}_0,\mathbf{t}_1, \dots ,\mathbf{t}_{N-1})</math> ≤ <math>  \frac kq </math> + <math>\frac 1N</math> <math>\sum_{h \in\Complex_k(q)}</math><math>\frac 1{r(\mathbf{h},q)} \Bigg| \sum_{n=0}^{N-1} e(\mathbf{h}\cdot \mathbf{t}_n)\Bigg|</math>

==Lower bound==
The discrepancy of <math>N</math> arbitrary points <math>\mathbf{t}_1, \dots ,\mathbf{t}_{N-1}\in  [0,1)^k</math> satisfies

:      <math>D_N (\mathbf{t}_0,\mathbf{t}_1, \dots ,\mathbf{t}_{N-1}) \ge \frac {\pi}{2N((\pi+1)^l -1)\prod_{j=1}^k {\rm max}(1,h_j)}\Bigg|\sum_{n=0}^{N-1} e(\mathbf{h}\cdot \mathbf{t}_n)\Bigg|</math>

for any nonzero lattice point <math>{\mathbf h}=(h_1,\dots ,h_k)\in Z^k</math>, where <math>l</math> denotes the number of nonzero coordinates of <math>{\mathbf h}</math>.

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.<ref name="nine"/>

==See also==
*[[Pseudorandom number generator]]
*[[List of random number generators]]
*[[Linear congruential generator]]
*[[Generalized inversive congruential pseudorandom numbers]]
*[[Naor-Reingold Pseudorandom Function]]

==References==
{{Reflist|refs=
<ref name="one">W.S. Chou,''On inversive Maximal Period Polynomials over Finite Fields'', Applicable Algebra in Engineering, Communication and Computing, No. 4/5, 1995, pp. 245-250.</ref>

<ref name="two">J. Eichenauer-Herrmannn. ''Inversive congruential pseudorandom numbers avoid the planes'',
Math.Comp., Vol. 56,1991, pp. 297-301.</ref>

<ref name="three">J. Eichenauer-Herrmannn, H. Grothe, A. Topuzoglu, ''On the lattice structure of a nonlinear generator with modulus <math>2^\alpha</math>'', J.Comput. Appl. Math., Vol. 31,1990, pp. 81-85.</ref>

<ref name="four">J. Eichenauer-Herrmannn, [[Harald Niederreiter|H. Niederreiter]], ''Lower bounds for the discrepancy of inversive congruential pseudorandom numbers with power of two modulus'', Math. Comp., Vol. 58, 1992, pp. 775-779.</ref>

<ref name="five">J. Eichenauer-Herrmannn,''Statistical independence of a new class of inversive congruential pseudorandom numbers'', Math. Comp., Vol 60, 1993, pp. 375-384.</ref>

<ref name="six">P. Hellekalek, ''Inversive pseudorandom number generators:concepts, results and links'', Proceedings of the Winter Simulation Conference, 1995, pp 255-262.</ref>

<ref name="seven">J. Bubicz, J. Stoklosa, ''Compound Inversive Congruential Generator Design Algorithm'', §3 .</ref>

<ref name="eight">[[Harald Niederreiter|H. Niederreiter]], ''New developments in uniform pseudorandom number and vector generation'', Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, Berlin, 1995.</ref>

<ref name="nine">J. Eichenauer-Herrmann, F.Emmerich, ''Compound Inversive Congruential Pseudorandom Numbers: An average-Case Analysis'', American Mathematical Society.</ref>

}}

==External links==
* [http://random.mat.sbg.ac.at/generators/wsc95/inversive/node2.html Inversive Generators] {{Webarchive|url=https://web.archive.org/web/20080924112047/http://random.mat.sbg.ac.at/generators/wsc95/inversive/node2.html |date=2008-09-24 }} at the [[University of Salzburg]].

[[Category:Pseudorandom number generators]]