|
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.
Received: 26.02.2003
Citation:
A. S. Rybakov, “Spectral properties of a linear congruential generator in special cases”, Diskr. Mat., 16:2 (2004), 54–78; Discrete Math. Appl., 14:3 (2004), 231–255
Linking options:
https://www.mathnet.ru/eng/dm152https://doi.org/10.4213/dm152 https://www.mathnet.ru/eng/dm/v16/i2/p54
|
|