Spectral properties of a linear congruential generator in special cases

A. S. Rybakov

Diskretnaya Matematika, Tome 16 (2004) no. 2, pp. 54-78

Résumé

In this paper for the linear congruent generator $$ z_{N+1}=G(z_N),\qquad N=1,2,\dots, $$ where $G(x)=\lambda x+c \pmod W$, $W=p^F$, $p$ is a prime number, we find a non-trivial lower bound for the least non-zero wave number $e_L(\lambda)$, the fundamental characteristic introduced in the spectral test to check for randomness on the base of analysis of the frequence of occurrences of $L$-tuples $(t_1,\ldots,t_L)$ in the sequence $(z_N)$. The lower bound obtained is of the form $W^{1/L-\delta}$, where $\delta$ is some variable explicitly depending on parameters which determine the factor $\lambda$. Under an appropriate choice of the parameters, $\delta$ can be made as small as desired. The factor $1/L$ cannot be changed for a greater one. Such bounds are necessary in studying classes of multipliers that pass the spectral test.