×

zbMATH — the first resource for mathematics

Remarks on nonlinear congruential pseudorandom numbers. (English) Zbl 0663.65005
Let \(x_ 1,x_ 2,...,x_ n,..\). be a sequence of pseudorandom numbers obtained by a generator producing a permutation of \(\{\) 1,2,...,p\(\}\), p a prime. Let \(u_ n=(0,x_{n+1}-x_ n,x_{n+2}-x_ n,...,x_{n+p- 1}-x_ n)\) and \(G^{(d)}\) be the \(d\times p\) matrix with rows \(u_ 0,u_ 1,...,u_{d-1}\). We say that the generator passes the d- dimensional lattice test iff rank \((G^{(d)})=d\). Consider the generator \(x_{n+1}=ax_ n+b\), where \(\bar O=O\), \(\bar c=c^{-1}\) (in the field \(F_ p)\). If this generator has period p then it passes the lattice test for all \(d\leq (p+1)/2\). Some generalizations of the result for the fields \(F_ q\) where q is some power of a prime \(p\geq 3\) are given.
Reviewer: J.Král

MSC:
65C10 Random number generation in numerical analysis
PDF BibTeX Cite
Full Text: DOI EuDML
References:
[1] Eichenauer J, Grothe H, Lehn J (1988) Marsaglia’s lattice test and non-linear congruential pseudo random number generators. Metrika 35:241–250 · Zbl 0653.65006
[2] Eichenauer J, Lehn J (1986) A non-linear congruential pseudo random number generator. Statistische Hefte 27:315–326 · Zbl 0607.65001
[3] Lidl R, Niederreiter H (1983) Finite fields. Addison-Wesley, Reading · Zbl 0554.12010
[4] Lidl R, Niederreiter H (1986) Introduction to finite fields and their applications. Cambridge Univ. Press, Cambridge · Zbl 0629.12016
[5] Niederreiter H, Shiue J-S (1977) Equidistribution of linear recurring sequences in finite fields. Indagationes Math 80:397–405 · Zbl 0372.12021
[6] Niederreiter H, Shiue J-S (1980) Equidistribution of linear recurring sequences in finite fields, II. Acta Arith 38:197–207 · Zbl 0466.12010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.