Generalized inversive congruential pseudorandom numbers

An approach to nonlinear congruential methods of generating uniform pseudorandom numbers in the interval [0,1) is the Inversive congruential generator with prime modulus. A generalization for arbitrary composite moduli ${\displaystyle m=p_{1},\dots p_{r}}$ with arbitrary distinct primes ${\displaystyle p_{1},\dots ,p_{r}\geq 5}$ will be present here.

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

${\displaystyle y_{0}={\rm {seed}}}$

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

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

Example

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

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

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

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

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

${\displaystyle 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 ${\displaystyle (y_{n}^{(i)})_{n\geqslant 0}}$ for ${\displaystyle 1\leq i\leq r}$ be defined as above. Then

${\displaystyle y_{n}\equiv m_{1}y_{n}^{(1)}+m_{2}y_{n}^{(2)}+\dots +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 ${\displaystyle \mathbb {Z} _{p_{1}},\dots ,\mathbb {Z} _{p_{r}}}$ but not in ${\displaystyle \mathbb {Z} _{m}.}$

Proof:

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

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

${\displaystyle y_{n+1}\equiv ay_{n}^{\varphi (m)-1}+b\equiv m_{i}(a_{i}m_{i}^{\varphi (m)}(y_{n}^{(i)})^{\varphi (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.

Discrepancy bounds of the GIC Generator

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

Higher bound

Let ${\displaystyle s\geq 2}$

Then the discrepancy ${\displaystyle D_{m}^{s}}$ satisfies

${\displaystyle D_{m}}$ ${\displaystyle ^{s}}$ < ${\displaystyle m^{-1/2}}$ × ${\displaystyle ({\frac {2}{\pi }}}$ × ${\displaystyle \log m+{\frac {7}{5}})^{s}}$ × ${\displaystyle \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

${\displaystyle D_{m}}$ ${\displaystyle ^{s}}$ ≥ ${\displaystyle {\frac {1}{2(\pi +2)}}}$ × ${\displaystyle m^{-1/2}}$ : × ${\displaystyle \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 ${\displaystyle D_{m}^{(s)}=O(m^{-1/2}(\log m)^{s})}$ for any Generalized Inversive Congruential Sequence. In this case Theorem 3 implies that there exist Generalized Inversive Congruential Generators having a discrepancy ${\displaystyle D_{m}^{(s)}}$ which is at least of the order of magnitude ${\displaystyle m^{-1/2}}$ for all dimension ${\displaystyle s\geq 2}$. However, if m is composed only of small primes, then r can be of an order of magnitude ${\displaystyle (\log m)/\log \log m}$ and hence ${\displaystyle \textstyle \prod _{i=1}^{r}(2s-2+s(p_{i})^{-1/2})=O{(m^{\epsilon })}}$ for every ${\displaystyle \epsilon >0}$.[1] Therefore, one obtains in the general case ${\displaystyle D_{m}^{s}=O(m^{-1/2+\epsilon })}$ for every ${\displaystyle \epsilon >0}$.

Since ${\displaystyle \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 ${\displaystyle m^{-1/2-\epsilon }}$ for every ${\displaystyle \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 ${\displaystyle m^{-1/2}(\log \log m)^{1/2}}$ according to the law of the iterated logarithm for discrepancies.[2] 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

References

1. G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 5th ed., Clarendon Press, Oxford, 1979.
2. J. Kiefer, On large deviations of the empiric d.f. Fo vector chance variables and a law of the iterated logarithm, PacificJ. Math. 11(1961), pp. 649-660.

Notes

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