Marsaglia's lattice test and non-linear congruential pseudo-random number generators (Q1107944): Difference between revisions

A recursive congruential non-additive generator of the form \((1)\quad x_{n+1}\equiv f(x_ n)(mod p),\) \(x_{n+1}\in {\mathbb{Z}}_ p\), \(n\geq 0\), is considered, where p is a large prime number, \({\mathbb{Z}}_ p=\{0,1,...,p-1\}\), \(x_ 0\in {\mathbb{Z}}_ p\), and f: \({\mathbb{Z}}_ p\to {\mathbb{Z}}_ p\) is a function such that (1) has maximal period length. The sequences of integers \(\{x_ i:\) \(i\geq 0\}\) generated by (1) are divided into vectors of \(d\geq 2\) consecutive numbers: \(v^ d_ i=(x_ i,...,x_{i+d-1})^ T\in {\mathbb{Z}}^ d_ p\) and let \(w^ d_ i\equiv v_ i^ d-v^ d_ 0(mod p),\) \(i\geq 0\). For \(d\leq 3\), it is shown that \(V^ d={\mathbb{Z}}^ d_ p,\) where \(V^ d=\{v\in {\mathbb{Z}}^ d_ p| \quad v\equiv \sum^{p-1}_{i=1}z_ iw^ d_ i(mod p);\quad z_ 1,...,z_{p-1}\in {\mathbb{Z}}_ p\}.\) In other words, (1) passes \textit{G. Marsaglia}'s lattice test [Applications of number theory to numerical analysis, 249-285 (1972; Zbl 0266.65007)]. For \(d\geq 4\) there are generators (1) which fail this test. It is also shown that the generators of a class of nonlinear generators introduced by the first and the third author [Stat. Hefte 27, 315-326 (1986; Zbl 0607.65001)] pass Marsaglia's lattice test for \(d\leq (p-1)/2\).