Лучшие вопросы
Таймлайн
Чат
Перспективы

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

простейший метод генерации псевдослучайных числе Из Википедии, свободной энциклопедии

Remove ads

Линейный конгруэнтный метод — один из методов генерации псевдослучайных чисел. Применяется в простых случаях и не обладает криптографической стойкостью. Входит в стандартные библиотеки различных компиляторов.

Описание

Линейный конгруэнтный метод был предложен Д. Г. Лемером на проходившем в 1949 году симпозиуме и опубликован в 1951 году в трудах симпозиума.[1] Суть метода заключается в вычислении последовательности случайных чисел , полагая

где  — модуль (натуральное число, относительно которого вычисляет остаток от деления; ),  — множитель (),  — приращение (),  — начальное значение ().

Эта последовательность называется линейной конгруэнтной последовательностью. Например, для получим последовательность [2]

Remove ads

Свойства

Суммиров вкратце
Перспектива

Линейная конгруэнтная последовательность, определенная числами , , и периодична с периодом, не превышающим . При этом длина периода равна тогда и только тогда, когда[3]:

  1. Числа и взаимно простые;
  2. кратно для каждого простого , являющегося делителем ;
  3. кратно , если кратно .

Наличие этого свойства для случая , где  — число битов в машинном слове, было доказано М. Гринбергом (англ. M. Greenberg).[4] Наличие этого свойства для общего случая и достаточность условий были доказаны Т. Е. Халлом (англ. T. E. Hull) и А. Р. Добеллом (англ. A. R. Dobell).[5]

Метод генерации линейной конгруэнтной последовательности при называют мультипликативным конгруэнтным методом, а при  — смешанным конгруэнтным методом. При генерируемые числа будут иметь меньший период, чем при , но при определенных условиях можно получить период длиной , если  — простое число. Тот факт, что условие может приводить к появлению более длинных периодов, был установлен В. Е. Томсоном (англ. W. T. Thomson) и независимо от него А. Ротенбергом (англ. A. Rotenberg).[2] Чтобы гарантировать максимальность цикла повторения последовательности при , необходимо в качестве значения параметра выбирать простое число. Самым известным генератором подобного рода является так называемый минимальный стандартный генератор случайных чисел, предложенный Стивеном Парком (англ. Stephen Park) и Кейтом Миллером (англ. Keith Miller) в 1988 году. Для него , а .[6][7]

Наиболее часто практикуемым методом генерации последовательностей псевдослучайных чисел является смешанный конгруэнтный метод.[источник не указан 2925 дней]

Remove ads

Часто используемые параметры

Суммиров вкратце
Перспектива

При выборе числа необходимо учитывать следующие условия:

1) число должно быть довольно большим, так как период не может иметь больше элементов;

2) значение числа должно быть таким, чтобы вычислялось быстро.

На практике при реализации метода исходя из указанных условий чаще всего выбирают , где  — число битов в машинном слове. При этом стоит учитывать, что младшие двоичные разряды сгенерированных таким образом случайных чисел демонстрируют поведение, далёкое от случайного, поэтому рекомендуется использовать только старшие разряды. Подобная ситуация не возникает, когда , где  — длина машинного слова. В таком случае младшие разряды ведут себя так же случайно, как и старшие.[2] Выбор множителя и приращения в основном обусловлен необходимостью выполнения условия достижения периода максимальной длины.

Печально известен «неудачный» (с точки зрения качества выходной последовательности) алгоритм RANDU, на протяжении многих десятилетий использовавшийся в самых разных компиляторах.

Для улучшения статистических свойств числовой последовательности во многих генераторах псевдослучайных чисел используется только часть битов результата. Например, в стандарте ISO/IEC 9899 на язык Си приведен (но не указан в качестве обязательного) пример функции rand(), принудительно отбрасывающей младшие 16 и один старший разряд.

#define RAND_MAX 32767 

static unsigned long int next = 1;

int rand(void)
{
  next = next * 1103515245 + 12345;
  return (unsigned int)(next/65536) % (RAND_MAX + 1);
}

void srand(unsigned int seed)
{
  next = seed;
}

Именно в таком виде функция rand() используется в компиляторах Watcom C/C++. Известны числовые параметры иных алгоритмов, применяемых в различных компиляторах и библиотеках.

Подробнее Source, m ...
Remove ads

Возможность использования в криптографии

Хотя линейный конгруэнтный метод порождает статистически хорошую псевдослучайную последовательность чисел, он не является криптографически стойким. Генераторы на основе линейного конгруэнтного метода являются предсказуемыми, поэтому их нельзя использовать в криптографии. Впервые генераторы на основе линейного конгруэнтного метода были взломаны Джимом Ридсом (Jim Reeds), а затем Джоан Бойяр. Ей удалось также вскрыть квадратические и кубические генераторы. Другие исследователи расширили идеи Бояр, разработав способы вскрытия любого полиномиального генератора. Таким образом, была доказана бесполезность генераторов на основе конгруэнтных методов для криптографии. Однако генераторы на основе линейного конгруэнтного метода сохраняют свою полезность для некриптографических приложений, например, для моделирования. Они эффективны и в большинстве используемых эмпирических тестов демонстрируют хорошие статистические характеристики[8].

Remove ads

См. также

Примечания

Литература

Ссылки

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads