Parallel streams of nonlinear congruential pseudorandom numbers (Q1266425): Difference between revisions

The authors present the general nonlinear congruential method for generating uniform pseudorandom numbers using permutation polynomials over finite prime fields and study mutual statistical independence properties of parallelized nonlinear congruential generators on the basis of the discrepancy. Let \(p\geq 5\) be an arbitrary prime, and identify \(\mathbb{Z}_p= \{0,1,\dots, p-1\}\) with the finite field of order \(p\). For \(i\in \{1,\dots, s\}\) with \(s\geq 2\), let \(g_i: \mathbb{Z}\to \mathbb{Z}_p\) be a monic permutation polynomial of \(\mathbb{Z}_p\) with \(g_i(0)=0\) and degree \(d_i\) as a polynomial over \(\mathbb{Z}_p\), where \(3\leq d_i\leq p-2\). For parameters \(a_i\in \mathbb{Z}_p\setminus \{0\}\) and \(b_i\in \mathbb{Z}_p\), let \[ y_n^{(i)}\equiv a_ig_i(n)+ b_i\pmod p, \quad n\geq 0, \] and define a sequence \((x_n^{(i)})_{n\geq 0}\) of nonlinear congruential pseudorandom numbers in \([0,1)\) by \(x_n^{(i)}= y_n^{(i)}/p\) for \(n\geq 0\). This sequence is purely periodic with period length \(p\). Finally, let \(\vec x_n= (x_n^{(1)},\dots, x_n^{(s)})\in [0,1)^s\), \(n\geq 0\), and for \(1\leq N\leq p\) denote the discrepancy of the point set \(\vec x_0,\vec x_1,\dots, \vec x_{N-1}\) by \(D_N^{(s)}= D_N(\vec x_0,\vec x_1,\dots,\vec x_{N-1})\). The authors prove that if \(g_1,\dots, g_s\) are linearly independent over \(\mathbb{Z}_p\), then \[ D_p^{(s)}\leq (d-1)p^{-1/2} \biggl(\frac{4} {\pi^2}\log p+ 1.38+ 0.64p^{-1} \biggr)^s+ sp^{-1} \] for all \(a_1,\dots, a_s\in \mathbb{Z}_p\setminus \{0\}\) and \(b_1,\dots, b_s\in \mathbb{Z}_p\). They also discuss lower bounds for \(D_p^{(s)}\). Furthermore, the lower and upper bounds for \(D_N^{(s)}\) with \(N<p\) and an upper bound for the average value of \(D_N^{(s)}\) with \(1\leq N\leq p\) are also presented.