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

Дискрет. матем., 2011, том 23, выпуск 1, страницы 51–71 (Mi dm1130)

Эта публикация цитируется в 1 статье

О свойствах генератора

С. В. Рыков


Аннотация: Генератор псевдослучайных чисел (ГПСЧ), порождаемый преобразованием
$$ F_c(x)=x+(x^2\vee c)\pmod{2^n}, $$
был представлен Климовым и Шамиром в 2002 г. Функция $F_c(x)$ транзитивна по модулю $2^n$ тогда и только тогда, когда $c\equiv5\pmod8$ или $c\equiv7\pmod8$.
В работе рассматриваются свойства распределения пар $(x_i, F_c(x_i))$ ГПСЧ при всевозможных значениях $c\in\mathbf Z/2^n\mathbf Z$ и показываются их неудовлетворительные статистические свойства, в особенности при $c\geq2^{n/3}$.
Показано, что в случае если $n=32$ требуется не более 9 различных пар $(x_i, F_c(x_i))$ для определения значения $c$ с вероятностью $P\geq0,999$.

УДК: 519.7

Статья поступила: 16.04.2010

DOI: 10.4213/dm1130


 Англоязычная версия: Discrete Mathematics and Applications, 2011, 21:2, 179–202

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


© МИАН, 2024