Спектральные свойства линейного конгруэнтного генератора в специальных случаях
А. С. Рыбаков
Аннотация:
В данной работе для линейного конгруэнтного генератора
$$
z_{N+1}=G(z_N),\quad N=1,2,\dots,
$$
где
$G(x)=\lambda x+c \pmod W$,
$W=p^F$,
$p$ — простое число, имеющего полный период и множитель
$\lambda$ специального вида, устанавливается нетривиальная
нижняя оценка наименьшего ненулевого волнового числа
$e_L(\lambda)$ — базовой характеристики, вводимой в спектральном тесте для проверки случайности на основе изучения частоты встречаемости
$L$-наборов
$(t_1,\ldots,t_L)$ в последовательности
$(z_N)$. Указываемая нижняя граница имеет вид
$W^{1/L-\delta}$, где
$\delta$ — некоторая величина, явно зависящая от параметров, определяющих множитель
$\lambda$. При специальном выборе параметров
$\delta$ можно сделать сколь угодно малым. Показатель
$1/L$ в этой оценке нельзя заменить большим. Такого рода оценки необходимы для изучения классов множителей, проходящих спектральный тест.
УДК:
519.7 Статья поступила: 26.02.2003
DOI:
10.4213/dm152