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}}${\displaystyle m=p_{1},\dots p_{r}} with arbitrary distinct primes ${\displaystyle p_{1},\dots ,p_{r}\geq 5}${\displaystyle p_{1},\dots ,p_{r}\geq 5} will be present here.

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

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

${\displaystyle y_{n+1}\equiv ay_{n}^{\varphi (m)-1}+b{\pmod {m}}{\text{, }}n\geqslant 0}${\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)}${\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.

Let take m = 15 = ${\displaystyle 3\times 5,円a=2,b=3}${\displaystyle 3\times 5,円a=2,b=3} and ${\displaystyle y_{0}=1}${\displaystyle y_{0}=1}. Hence ${\displaystyle \varphi (m)=2\times 4=8,円}${\displaystyle \varphi (m)=2\times 4=8,円} and the sequence ${\displaystyle (y_{n})_{n\geqslant 0}=(1,5,13,2,4,7,1,\dots )}${\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}${\displaystyle 1\leq i\leq r} let ${\displaystyle \mathbb {Z} _{p_{i}}=\{0,1,\dots ,p_{i}-1\},m_{i}=m/p_{i}}${\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}}}${\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{. }}}${\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}}${\displaystyle (y_{n})_{n\geqslant 0}} be a sequence of elements of ${\displaystyle \mathbb {Z} _{p_{i}}}${\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. }}}${\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. }}}

Let ${\displaystyle (y_{n}^{(i)})_{n\geqslant 0}}${\displaystyle (y_{n}^{(i)})_{n\geqslant 0}} for ${\displaystyle 1\leq i\leq r}${\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}}.}${\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}}}${\displaystyle \mathbb {Z} _{p_{1}},\dots ,\mathbb {Z} _{p_{r}}} but not in ${\displaystyle \mathbb {Z} _{m}.}${\displaystyle \mathbb {Z} _{m}.}

Proof:

First, observe that ${\displaystyle m_{i}\equiv 0{\pmod {p_{j}}},\;{\text{for}}\;i\neq j,}${\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}}}${\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}}}}${\displaystyle y_{n}\equiv m_{i}(y_{n}^{(i)}){\pmod {p_{i}}}}, for ${\displaystyle 1\leq i\leq r}${\displaystyle 1\leq i\leq r} which will be shown on induction on ${\displaystyle n\geqslant 0}${\displaystyle n\geqslant 0}.

Recall that ${\displaystyle y_{0}\equiv m_{i}(y_{0}^{(i)}){\pmod {p_{i}}}}${\displaystyle y_{0}\equiv m_{i}(y_{0}^{(i)}){\pmod {p_{i}}}} is assumed for ${\displaystyle 1\leq i\leq r}${\displaystyle 1\leq i\leq r}. Now, suppose that ${\displaystyle 1\leq i\leq r}${\displaystyle 1\leq i\leq r} and ${\displaystyle y_{n}\equiv m_{i}(y_{n}^{(i)}){\pmod {p_{i}}}}${\displaystyle y_{n}\equiv m_{i}(y_{n}^{(i)}){\pmod {p_{i}}}} for some integer ${\displaystyle n\geqslant 0}${\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}}}}${\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.

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

Higher bound

Let ${\displaystyle s\geq 2}${\displaystyle s\geq 2}

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

${\displaystyle D_{m}}${\displaystyle D_{m}} ${\displaystyle ^{s}}${\displaystyle ^{s}} < ${\displaystyle m^{-1/2}}${\displaystyle m^{-1/2}} × ${\displaystyle ({\frac {2}{\pi }}}${\displaystyle ({\frac {2}{\pi }}} × ${\displaystyle \log m+{\frac {7}{5}})^{s}}${\displaystyle \log m+{\frac {7}{5}})^{s}} × ${\displaystyle \textstyle \prod _{i=1}^{r}(2s-2+s(p_{i})^{-1/2})+s_{m}^{-1}}${\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 D_{m}} ${\displaystyle ^{s}}${\displaystyle ^{s}} ≥ ${\displaystyle {\frac {1}{2(\pi +2)}}}${\displaystyle {\frac {1}{2(\pi +2)}}} × ${\displaystyle m^{-1/2}}${\displaystyle m^{-1/2}} : × ${\displaystyle \textstyle \prod _{i=1}^{r}({\frac {p_{i}-3}{p_{i}-1}})^{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})}${\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)}}${\displaystyle D_{m}^{(s)}} which is at least of the order of magnitude ${\displaystyle m^{-1/2}}${\displaystyle m^{-1/2}} for all dimension ${\displaystyle s\geq 2}${\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}${\displaystyle (\log m)/\log \log m} and hence ${\displaystyle \textstyle \prod _{i=1}^{r}(2s-2+s(p_{i})^{-1/2})=O{(m^{\epsilon })}}${\displaystyle \textstyle \prod _{i=1}^{r}(2s-2+s(p_{i})^{-1/2})=O{(m^{\epsilon })}} for every ${\displaystyle \epsilon >0}${\displaystyle \epsilon >0}.^[1] Therefore, one obtains in the general case ${\displaystyle D_{m}^{s}=O(m^{-1/2+\epsilon })}${\displaystyle D_{m}^{s}=O(m^{-1/2+\epsilon })} for every ${\displaystyle \epsilon >0}${\displaystyle \epsilon >0}.

Since ${\displaystyle \textstyle \prod _{i=1}^{r}((p_{i}-3)/(p_{i}-1))^{1/2}\geqslant 2^{-r/2}}${\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 }}${\displaystyle m^{-1/2-\epsilon }} for every ${\displaystyle \epsilon >0}${\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}}${\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.

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

• Eichenauer-Herrmann, Jürgen (1994), "On Generalized Inversive Congruential Pseudorandom Numbers", Mathematics of Computation, 63 (207) (first ed.), American Mathematical Society: 293–299, doi:10.1090/S0025-5718-1994-1242056-8 , JSTOR 2153575

• Pseudorandom number generators