×

On the period length of pseudorandom vector sequences generated by matrix generators. (English) Zbl 0657.65008

Let m be a positive integer, let \({\mathbb{Z}}_ m=\{0,1,...,m-1\}\), and let A be an \(r\times r\) matrix with elements in \({\mathbb{Z}}_ m\) which is nonsingular (mod m). The following linear recursive congruential matrix generator for generating r-dimensional pseudorandom vectors is considered \((*)\quad \bar x_{n+1}\equiv A\bar x_ n (mod m)\), \(\bar x_{n+1}\in {\mathbb{Z}}^ r_ m\), \(n\geq 0\), with \(\bar x_ 0\in {\mathbb{Z}}^ r_ m\). The sequence \(\{z_ n:\) \(n\geq 0\}\) is purely periodic and let \(\lambda(A,\bar x_ 0,m)\) denote its period length. In this paper the case \(m=p^{\alpha}\), \(\alpha\geq 2\), is considered with p a prime number. It is shown that for \(p\geq 3\) and \(r\geq 2\) there exist matrix generators (*) with \(\lambda (A,\bar x_ 0,p^{\alpha})=(p^ r- 1)p_{\alpha -1}\) for any \(\bar x_ 0\in {\mathbb{Z}}^ r_{p^{\alpha}}\) with \(\bar x_ 0\equiv \bar O (mod p)\).
Reviewer: R.Theodorescu

MSC:

65C10 Random number generation in numerical analysis
11K99 Probabilistic theory: distribution modulo \(1\); metric theory of algorithms
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Lothar Afflerbach and Holger Grothe, The lattice structure of pseudo-random vectors generated by matrix generators, J. Comput. Appl. Math. 23 (1988), no. 1, 127 – 131. · Zbl 0658.65006
[2] Holger Grothe, Matrix generators for pseudo-random vector generation, Statist. Hefte 28 (1987), no. 3, 233 – 238. · Zbl 0629.65006
[3] Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. · Zbl 0477.65002
[4] Harald Niederreiter, A pseudorandom vector generator based on finite field arithmetic, Math. Japon. 31 (1986), no. 5, 759 – 774. · Zbl 0619.65002
[5] E.-H. A. D. E. Tahmi, Contribution aux Générateurs de Vecteurs Pseudo-Aléatoires, Thèse, Université des Sciences et de la Technologie Houari Boumedienne, Algier, 1982.
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.