On the lattice structure of pseudorandom numbers generated over arbitrary finite fields

Abstract

Marsaglia's lattice test for congruential pseudorandom number generators modulo a prime is extended to a test for generators over arbitrary finite fields. A congruential generator η0, η1,..., generated by ηn = g(n), n = 0, 1,..., passes Marsaglia's s-dimensional lattice test if and only if s ≤ deg(g). It is investigated how far this condition holds true for polynomials over arbitrary finite fields Fq, particularly for polynomials of the form gd (x) = α(x + β)d + γ, α, β, γ ∈ Fq, α ≠ 0, 1 ≤ d ≤ q - 1.