Spectral properties of a linear congruential generator in special cases
A. S. Rybakov
Abstract:
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.
UDC:
519.7 Received: 26.02.2003
DOI:
10.4213/dm152