RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 2004, том 16, выпуск 2, страницы 54–78 (Mi dm152)

Спектральные свойства линейного конгруэнтного генератора в специальных случаях

А. С. Рыбаков


Аннотация: В данной работе для линейного конгруэнтного генератора
$$ 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


 Англоязычная версия: Discrete Mathematics and Applications, 2004, 14:3, 231–255

Реферативные базы данных:


© МИАН, 2024