Линейный конгруэнтный генератор

Из известных процедур генерации последовательности псевдослучайных целых чисел наиболее часто применяется так называемый линейный конгруэнтный генератор. Этот генератор вырабатывает последовательность псевдослучайных чисел Y1, Y2, Yi-1,Yi, ., используя соотношение

(2.3)

где Yi - i-e (текущее) число последовательности; Yi-1 - предыдущее число последовательности; а,b и m - константы; m - модуль;

а - множитель (коэффициент); b - приращение; Yo - порождающее число (исходное значение).

Текущее псевдослучайное число Yi получают из предыдущего числа Yi-1 умножением его на коэффициент а, сложением с приращением b и вычислением остатка от деления на модуль m. Данное уравнение генерирует псевдослучайные числа с периодом повторения, который зависит от выбираемых значений параметров а, и m и может достигать значения m. Если a, b и m выбраны правильно, то генератор будет с максимальным периодом (например, b должно быть взаимно простым с m и коэффициент а должен быть нечетным числом). Значение модуля m берется равным 2n либо равным простому числу, например m=231-1.

Преимуществом линейных конгруэнтных генераторов является их быстрота за счет малого количества операций на бит.

Конгруэнтные генераторы, работающие по алгоритму, предложенному

Национальным бюро стандартов США, используются, в частности, в системах программирования. Эти генераторы имеют длину периода 224 и обладают хорошими статистическими свойствами. Однако такая длина периода мала для криптографических применений. Кроме того, доказано, что последовательности, генерируемые конгруэнтными генераторами, не являются криптографически стойкими.

Однако линейные конгруэнтные генераторы сохраняют свою полезность для не криптографических приложений, например, для моделирования. Они эффективны в большинстве используемых эмпирических тестах и демонстрируют хорошие статистические характеристики.

Читайте также

Проектирование сооружений городской районной телефонной сети
Основными задачами, стоящими перед отраслью связи на городской телефонной сети (ГТС), являются улучшение характеристик качества обслуживания и предоставление новых видов услуг св ...

Проект устройства со световыми эффектами на основе микроконтроллера ATtiny12 семейства AVR фирмы Atmel
Популярность микроконтроллеров ATtiny постоянно увеличивается. Не последнюю роль в этом играет соотношение показателей «цена/ быстродействие/ энергопотребление», являющееся одним из ...

Проектирование РЭА
При конструкторском проектировании РЭА (радиоэлектронной аппаратуры) решаются задачи, связанные с поиском наилучшего варианта конструкции, удовлетворяющего требованиям технического задан ...

Основные разделы

Все права защищены! (с)2020 - www.generallytech.ru