×

Pseudorandom number and vector generation by compound inversive methods. (English) Zbl 0862.11047

Darmstadt: TH Darmstadt, FB Math. 69 p. (1996).
The present PhD thesis gives a nice survey on the theory of pseudorandom numbers, including new results on compound inversive methods. After an introduction of known results and standard methods the author collects several discrepancy bounds, which have to be used in analyzing pseudorandom sequences. In section 3 compound inversive pseudorandom vectors are studied in a very general situation. Let \(m=p_1\dots p_r\) with distinct primes \(p_i\) and \(m_i = m/p_i\), \(q_i = p^k_i\) \((1\leq i\leq r)\), where \(k\geq 1\) is the dimension of the vectors to be generated. Let \((\gamma_n^{(i)})_{n \geq 0}\) denote inversive sequences \(\gamma_{n+1}^{(i)} = \alpha_i \overline \gamma_n^{(i)} + \beta_i\) in the finite field \(F_{q_i}\) and let \({\mathbf c}_n^{(i)}\) be the coordinate vector of \(\gamma_n^{(i)}\) relative to an ordered basis of \(F_{q_i}\) over \(F_{p_i}\). Then a compound inversive sequence \(({\mathbf u}_n)_{n \geq 0}\) in \([0,1)^k\) is defined by \({\mathbf u}_n \equiv {\mathbf u}_n^{(1)} + \cdots + {\mathbf u}_n^{(r)} \pmod 1\).
For \(r=1\) one has the ordinary inversive method due to H. Niederreiter [ACM Trans. Model. Comput. Simul. 4, 191-212 (1994; Zbl 0847.11039)], and the case \(k=1\) was studied by J. Eichenauer-Herrmann [Math. Comput. 63, 293-299 (1994)].
The present author proves a criterion for the maximum possible period length of pseudorandom vectors generated by the compound inversive method. Then, based on exponential sums, discrepancy bounds for related point sequences are proved. Section 4 is devoted to digital compound inversive generators. Also in this case discrepancy bounds are established. The thesis concludes with comments on the implementation of generators (including tables) and a useful bibliography.
Reviewer: R.F.Tichy (Graz)

MSC:

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

Citations:

Zbl 0847.11039