Generalized inversive congruential pseudorandom numbers

An approach to nonlinear congruential methods of [[Pseudorandom number generator |generating uniform pseudorandom numbers]] in the interval [0,1) is the Inversive congruential generator with prime modulus .A generalization for arbitrary composite moduli m = p₁...p_r with arbitrary distinct [[Prime number |primes]] p₁,..., p_r ≥ 5 will be present here.

Let $\mathbb {Z} _{m}=\{0,1,...,m-1\}$ .For integers $a,b\in \mathbb {Z} _{m}$ with gcd (a,m) = 1 a generalized inversive congruential sequence $(y_{n})_{n\geqslant 0}$ of elements of $\mathbb {Z} _{m}$ is defined by

$y_{0}={\text{seed}}$

$y_{n+1}\equiv ay_{n}^{\phi (m)-1}+b{\pmod {m}}{\text{, }}n\geqslant 0$

where$\phi (m)=(p_{1}-1)...(p_{r}-1)$denotes the number of positive integers less than m which are relatively prime to m.

Example:

Let take m = 15 = $3\times 5\,$, a=2 , b=3 and y₀ = 1. Hence $\phi (m)=2\times 4=8\,$ and the sequence $(y_{n})_{n\geqslant 0}=(1,5,13,2,4,7,1,.....)$ is not maximum.

The result below shows that these sequences are closely related to the following inversive congruential sequence with prime moduli.

For $1\leq i\leq r$ let $\mathbb {Z} _{p_{i}}=\{0,1,...,p_{i}-1\},m_{i}=m/p_{i}$ and $a_{i},b_{i}\in \mathbb {Z} _{p_{i}}$ be integers with

$a\equiv m_{i}^{2}a_{i}{\pmod {p_{i}}}\;{\text{and }}\;b\equiv m_{i}b_{i}{\pmod {p_{i}}}{\text{. }}$

Let $(y_{n})_{n\geqslant 0}$ be a sequence of elements of $\mathbb {Z} _{p_{i}}$ , given by

$y_{n+1}^{(i)}\equiv a_{i}(y_{n}^{(i)})^{p_{i}-2}+b_{i}{\pmod {p_{i}}}\;{\text{, }}n\geqslant 0\;{\text{where}}\;y_{0}\equiv m_{i}(y_{0}^{(i)}){\pmod {p_{i}}}\;{\text{is assumed. }}$

Theorem 1

Let $(y_{n}^{(i)})_{n\geqslant 0}$ for $1\leq i\leq r$ be defined as above. Then

$y_{n}\equiv m_{1}y_{n}^{(1)}+m_{2}y_{n}^{(2)}+...+m_{r}y_{n}^{(r)}{\pmod {m}}.$

This theorem shows that an implementation of Generalized Inversive Congruential Generator is possible,where exact integer computations have to be performed only in $\mathbb {Z} _{p_{1}},{\text{..., }}\mathbb {Z} _{p_{r}}$ but not in $\mathbb {Z} _{m}.$

Proof:

First,observe that $m_{i}\equiv 0{\pmod {p_{j}}},\;{\text{for}}\;i\neq j,$ and hence $y_{n}\equiv m_{1}y_{n}^{(1)}+m_{2}y_{n}^{(2)}+...+m_{r}y_{n}^{(r)}{\pmod {m}}$ if and only if $y_{n}\equiv m_{i}(y_{n}^{(i)}){\pmod {p_{i}}}$, for $1\leq i\leq r$ which will be shown on induction on $n\geqslant 0$.

Recall that $y_{0}\equiv m_{i}(y_{0}^{(i)}){\pmod {p_{i}}}$ is assumed for $1\leq i\leq r$. Now, suppose that $1\leq i\leq r$ and $y_{n}\equiv m_{i}(y_{n}^{(i)}){\pmod {p_{i}}}$ for some integer $n\geqslant 0$. Then straightforward calculations and Fermat's Theorem yield

$y_{n+1}\equiv ay_{n}^{\phi (m)-1}+b\equiv m_{i}(a_{i}m_{i}^{\phi (m)}(y_{n}^{(i)})^{\phi (m)-1}+b_{i})\equiv m_{i}(a_{i}(y_{n}^{(i)})^{p_{i}-2}+b_{i})\equiv m_{i}(y_{n+1}^{(i)}){\pmod {p_{i}}}$,

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.

Bounderies of the discrepancy of the GIC Generator

We use the notation $D_{m}^{s}=D_{m}(x_{0},...,x_{m}-1)$ where $x_{n}=(x_{n},x_{n}+1,...,x_{n}+s-1)$ ∈ $[0,1)^{s}$ of Generalized Inversive Congruential Pseudorandom Numbers for s ≥ 2

Higher bound Let s ≥ 2 Then the discrepancy $D_{m}$ $^{s}$ satisfies $D_{m}$ $^{s}$ < $m^{-1/2}$ × $({\frac {2}{\pi }}$ × $\log m+{\frac {7}{5}})^{s}$ × $\textstyle \prod _{i=1}^{r}(2s-2+s(p_{i})^{-1/2})+s_{m}^{-1}$ for any Generalized Inversive Congruential operator.

Lower bound:

There exist Generalized Inversive Congruential Generators with $D_{m}$ $^{s}$ ≥ ${\frac {1}{2(\pi +2)}}$ × $m^{-1/2}$ × $\textstyle \prod _{i=1}^{r}({\frac {p_{i}-3}{p_{i}-1}})^{1/2}$ for all dimension s ≥ 2.

For a fixed number r of prime factors of m,theorem 2 shows that $D_{m}^{(s)}=O(m^{-1/2}(logm)^{s})$ for any Generalized Inversive Congruential Sequence.In this case Theorem 3 implies that there exist Generalized Inversive Congruential Generators having a discrepancy $D_{m}^{(s)}$ which is at least of the order of magnitude $m^{-1/2}$ for all dimension s ≥ 2.However,if m is composed only of small primes,then r can be of an order of magnitude $(logm)/loglogm$ and hence $\textstyle \prod _{i=1}^{r}(2s-2+s(p_{i})^{-1/2})=O{(m^{\epsilon })}$ for every $\epsilon >0$ .Therefore,one obtains in the general case $D_{m}^{s}=O(m^{-1/2+\epsilon })$ for every $\epsilon >0$.

Since $\textstyle \prod _{i=1}^{r}((p_{i}-3)/(p_{i}-1))^{1/2}\geqslant 2^{-r/2}$, similar arguments imply that in the general case the lower bound in Theorem 3 is at least of the order of magnitude $m^{-1/2-\epsilon }$ for every $\epsilon >0$. 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 $m^{-1/2}(loglogm)^{1/2}$ according to the law of the iterated logarithm for discrepancies .In this sense, Generalized Inversive Congruential Pseudo-random Numbers model true random numbers very closely.

See also

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

Notes

• Eichenauer-Herrmann, Jürgen (1994), On Generalized Inversive Congruential Pseudorandom Numbers (first ed.), American Mathematical Society