A multiple recursive non-linear congruential pseudo random number generator

Abstract

On-linear multiple recursive congruential pseudo random number generator with prime modulus p is introduced. Let x, n≥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≥0, the sequence of non-negative integers with x_N(n)≢0 (mod p). The non-linear generator is defined by z_n≡x_N(n)+1·x ⁻¹_N(n) (mod p), n≥0, where x ⁻¹_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-tupels (y₁,...,y_r) with 1≤y₁,...,y_r≤p are generated once per period when r-tupels of consecutive numbers of the generated sequence are formed. For r=1 this generator coincides with the generator introduced by Eichenauer and Lehn [2].