RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2004 Volume 16, Issue 2, Pages 54–78 (Mi dm152)

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


 English version:
Discrete Mathematics and Applications, 2004, 14:3, 231–255

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025