## A statistical analysis of generalized feedback shift register pseudorandom number generators.(English)Zbl 0634.65003

The author considers sequences of pseudorandom numbers, equidistributed in [0,1], of the form $$x_ n=\sum^{m}_{j=1}y_{n+k}p^{-j}$$ $$n=0,1,2,..$$. where the p-adic digits $$y_ r$$ are obtained by the recurrence $$y_ r=a_{k-1}y_{r-1}+...+a_ 0y_{r-k}$$ mod p and the numbers $$k_ j$$ are distinct nonnegative arbitrary integers. The distribution of the sequence of s-dimensional vectors $$X_ n=(x_ n,x_{n+1},...,x_{n+s-1})\in [0,1]\quad s$$ is examined by considering the discrepancy $$D_ N^{(s)}=\sup | E_ N(J)-V(J)|$$ for $$N\geq 1$$ where $$E_ N(J)$$ is $$N^{-1}$$ times the number of terms $$X_ 0,X_ 1,...,X_{N-1}$$ falling into the s-dimensional interval $$J=\prod^{s}_{i=1}[0,t_ i]$$, $$V(J)=\prod^{s}_{i=1}t_ i$$, and the supremum is extended over all the intervals for which $$0\leq t_ i\leq 1.$$
It is assumed that $$f(x)=x$$ $$k-a_{k-1}x^{k-1}...-a_ 0$$ is an irreducible polynomial over the field $$F_ p$$ of the residue classes mod p. Let $$\tau$$ be the least period of the sequence: the maximal value of $$\tau$$ is p k-1, and is achieved when f(x) is a primitive polynomial over $$F_ p$$. In the paper some interesting formulae giving upper and lower bounds for $$D_ N^{(s)}$$ are proved, both in the case $$N=\tau$$ and in the case $$0\leq N<\tau$$. Particular results for $$p=2$$ are deduced. The troublesome evaluation of the term that measures the dependence of $$D_ N^{(s)}$$ on f(x) and the constants $$k_ j$$ is avoided in every case by the introduction of another quantity (called figure of merit) which is easier to handle.
Reviewer: M.Cugiani

### MSC:

 65C10 Random number generation in numerical analysis
Full Text: