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\ge 5}$ will be present here.

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

${\displaystyle y_0=\mathrm{s}\mathrm{e}\mathrm{e}\mathrm{d}}$

${\displaystyle y_{n+1}\equiv a{y}_n^{\phi (m)-1}+b(\mathrm{mod}m)\text{, }n⩾0}$

where ${\displaystyle \phi (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 5a=2,b=3}$ and ${\displaystyle y_0=1}$. Hence ${\displaystyle \phi (m)=2\times 4=8}$ and the sequence ${\displaystyle (y_n{)}_{n⩾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\le i\le r}$ let ${\displaystyle {\mathbb{\mathbb{Z}}}_{p_i}=\{0,1,\dots ,p_i-1\},m_i=m/p_i}$ and ${\displaystyle a_i,b_i\in {\mathbb{\mathbb{Z}}}_{p_i}}$ be integers with

${\displaystyle a\equiv m_i^2{a}_i(\mathrm{mod}{p}_i)\text{and }b\equiv m_i{b}_i(\mathrm{mod}{p}_i)\text{. }}$

Let ${\displaystyle (y_n{)}_{n⩾0}}$ be a sequence of elements of ${\displaystyle {\mathbb{\mathbb{Z}}}_{p_i}}$, given by

${\displaystyle y_{n+1}^{(i)}\equiv a_i(y_n^{(i)}{)}^{p_i-2}+b_i(\mathrm{mod}{p}_i)\text{, }n⩾0\text{where}{y}_0\equiv m_i(y_0^{(i)})(\mathrm{mod}{p}_i)\text{is assumed. }}$

Let ${\displaystyle (y_n^{(i)}{)}_{n⩾0}}$ for ${\displaystyle 1\le i\le 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)}(\mathrm{mod}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{\mathbb{Z}}}_{p_1},\dots ,{\mathbb{\mathbb{Z}}}_{p_r}}$ but not in ${\displaystyle {\mathbb{\mathbb{Z}}}_m.}$

Proof:

First, observe that ${\displaystyle m_i\equiv 0(\mathrm{mod}{p}_j),\text{for}i\ne j,}$ and hence ${\displaystyle y_n\equiv m_1{y}_n^{(1)}+m_2{y}_n^{(2)}+\dots +m_r{y}_n^{(r)}(\mathrm{mod}m)}$ if and only if ${\displaystyle y_n\equiv m_i(y_n^{(i)})(\mathrm{mod}{p}_i)}$, for ${\displaystyle 1\le i\le r}$ which will be shown on induction on ${\displaystyle n⩾0}$.

Recall that ${\displaystyle y_0\equiv m_i(y_0^{(i)})(\mathrm{mod}{p}_i)}$ is assumed for ${\displaystyle 1\le i\le r}$. Now, suppose that ${\displaystyle 1\le i\le r}$ and ${\displaystyle y_n\equiv m_i(y_n^{(i)})(\mathrm{mod}{p}_i)}$ for some integer ${\displaystyle n⩾0}$. Then straightforward calculations and Fermat's Theorem yield

${\displaystyle y_{n+1}\equiv a{y}_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)})(\mathrm{mod}{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)}$ 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\ge 2}$.

Higher bound

Let ${\displaystyle s\ge 2}$

Then the discrepancy ${\displaystyle D_m^s}$ satisfies

${\displaystyle D_m}$ $s^{}$ < ${\displaystyle m^{-1/2}}$ × ${\displaystyle (\frac{2}{\pi }}$ × ${\displaystyle \log m+\frac{7}{5}{)}^s}$ × ${\displaystyle {\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}$ $s^{}$ ≥ ${\displaystyle \frac{1}{2(\pi +2)}}$ × ${\displaystyle m^{-1/2}}$ : × ${\displaystyle {\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\ge 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 {\prod }_{i=1}^r(2s-2+s(p_i{)}^{-1/2})=O(m^{ϵ})}$ for every ${\displaystyle ϵ>0}$.^[1] Therefore, one obtains in the general case ${\displaystyle D_m^s=O(m^{-1/2+ϵ})}$ for every ${\displaystyle ϵ>0}$.

Since ${\displaystyle {\prod }_{i=1}^r((p_i-3)/(p_i-1){)}^{1/2}⩾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-ϵ}}$ for every ${\displaystyle ϵ>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.

• 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 (American Mathematical Society) 63 (207): 293–299, doi:10.1090/S0025-5718-1994-1242056-8 

0.00 (0 votes) Original source: https://en.wikipedia.org/wiki/Generalized inversive congruential pseudorandom numbers. Read more