Виток Мерсенна


Виток Мерсенна

Вихрь Мерсенна (Mersenne twister) — это генератор псевдослучайных чисел (ГПСЧ), разработанный в 1997 японскими учёными Макото Мацумото (松本 眞) и Такудзи Нисимура (西村 拓士). Их работа основывается на свойствах простых чисел Мерсенна (отсюда название) и обеспечивает быструю генерацию высококачественных псевдослучайных чисел. Вихрь Мерсенна лишен многих недостатков присущих другим ГПСЧ таких как малый период, предсказуемость, легко выявляемая статистическая зависимость. Тем не менее этот генератор не является криптостойким, что ограничивает его использование в криптографии.

Существуют по меньшей мере два общих варианта алгоритма, различающихся только размером использующегося простого числа Мерсенна, наиболее распространённым из которых является MT19937.

Свойства

Вихрь Мерсенна является витковым регистром сдвига с обобщённой отдачей (twisted generalised feedback shift register, TGFSR). «Вихрь» — это преобразование, которое обеспечивает равномерное распределение генерируемых псевдослучайных чисел в 623 измерениях (для линейных конгруэнтных генераторов оно ограничено 5-ю измерениями). Поэтому корреляция между последовательными значениями в выходной последовательности Вихря Мерсенна пренебрежимо мала.

Вихрь Мерсенна имеет огромный период, а именно, доказано, что его период равен числу Мерсенна 219937 − 1, что более чем достаточно для многих практических приложений.

Существуют эффективные реализации Вихря Мерсенна, превосходящие по скорости многие стандартные ГПСЧ (в частности, в 2-3 раза быстрее линейных конгруэнтных генераторов). Вихрь Мерсенна реализован в библиотеке PHP, Руби.

Выдаваемые Вихрем Мерсенна псевдослучайные числа успешно проходят тесты DIEHARD, что говорит об их хороших статистических свойствах.

Литература

  • M. Matsumoto and T. Nishimura, Mersenne twister: A 623-dimensionally equidistributed uniform pseudorandom number generator, ACM Trans. on Modeling and Computer Simulations, 1998.

Ссылки


Wikimedia Foundation. 2010.