Pseudorandom vector generation by the inversive method. (English) Zbl 0847.11039

Niederreiter, Harald

ACM Trans. Model. Comput. Simul. 4, No. 2, 191-212 (1994).

This paper gives a detailed analysis of the inversive method for the generation of uniform pseudorandom vectors. Let \(p\) be a prime and \(q= p^k\), where \(k\in \mathbb{Z}\) is the dimension of the vectors to be generated. Denote by \(F_q\) the finite field with \(q\) elements and by \(F^*_q\) the multiplicative group of nonzero elements of \(F_q\). For an initial value \(\gamma_0\in F_q\) and parameters \(\alpha\in F^*_q\) and \(\beta\in F_q\) we use the recursion \[ \gamma_{n+ 1}= \alpha \overline \gamma_n+ \beta,\quad n\geq 0 \] to generate a sequence \((\gamma_n)_{n\geq 0}\) in \(F_q\), where \(\overline\gamma= \gamma^{- 1}\) is the multiplicative inverse of \(\gamma\in F^*_q\) and \(\overline 0:= 0\). As usual, the coordinate vector \(c_n\) of \(\gamma_n\in F_q\) relative to a basis of \(F_q\) over \(F_p\) can be viewed as an element of \(\mathbb{Z}^k_p\). We define pseudorandom vectors \(u_n= {1\over p} c_n\in [0, 1)^k\), \(n\geq 0\). The author gives a necessary and sufficient condition so that the sequence \((u_n)_{n\geq 0}\) achieves the maximal period length \(p^k\), and proves that for the sequence \((u_n)_{n\geq 0}\) with period length \(q= p^k\) the discrete discrepancy of the points \(v_0, v_1,\dots, v_{q- 1}\), \[ E^{(s)}_{q, p}= O(q^{- 1/2}(\log p)^{ks}) \] for all \(s\geq 2\), and that this estimate is essentially best possible up to the logarithmic factor, where \(v_n= (u_n, u_{n+ 1},\dots, u_{n+ s- 1})\), \(n\geq 0\).

Reviewer: Zhu Yaochen (Beijing)

MSC:

11K45	Pseudo-random numbers; Monte Carlo methods
65C10	Random number generation in numerical analysis

Keywords:

parallelized simulation method; inversive method; generation of uniform pseudorandom vectors; maximal period length; discrete discrepancy