A multiple recursive nonlinear congruential pseudo random number generator (Q1086972): Difference between revisions

A nonlinear multiple recursive congruential pseudo-random number generator with prime modulus p is introduced. Let \(x_ n\), \(n\geq 0\), be the sequence generated by a usual linear \((r+1)\)-step recursive congruential generator with prime modulus p and denote by N(n), \(n\geq 0\), the sequence of non-negative integers with \(x_{N(n)}\not\equiv 0\) (mod p). The nonlinear generator is defined by \(z_ n\equiv x_{N(n+1)}\cdot x^{-1}_{N(n)}\quad (mod p),\) \(n\geq 0\), where \(x^{-1}_{N(n)}\) denotes the inverse element of \(x_{N(n)}\) in the Galois field \(GF(p).\) A condition is given which ensures that the generated sequence is purely periodic with period length \(p^ r\) and all \((p-1)^ r\) r-tuples \((y_ 1,...,y_ r)\) with \(1\leq y_ 1,...,y_ r<p\) are generated once per period when r-tuples of consecutive numbers of the generated sequence are formed. For \(r=1\) this generator coincides with a nonlinear generator introduced by the first and the third author in an earlier paper.