Вихрь Мерсенна


Вихрь Мерсенна

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

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

Содержание

Свойства

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

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

Существуют эффективные реализации Вихря Мерсенна, превосходящие по скорости многие стандартные ГПСЧ (в частности, в 2-3 раза быстрее линейных конгруэнтных генераторов). Вихрь Мерсенна реализован в библиотеке Boost,[2] Glib.[3] и стандартных библиотеках для Python, [4] [5] Ruby,[6] R,[7] PHP,[8] MATLAB [9]

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

Генератор не предназначен для получения криптографически-стойких случайных последовательностей чисел. Для этого выходную последовательность необходимо подвергнуть обработке одним из криптографических алгоритмов хеширования.[10]

К-распределение

Было предложено много генераторов возможно «высокого качества», но только немногие могут быть использованы для серьёзного моделирования из-за отсутствия чёткого понятия «хаотичности» для генераторов псевдослучайных чисел, так как каждый исследователь концентрируется на конкретных параметрах хаотичности. Среди многих известных мер, тесты, основанные на более высоком равномерном распределении, таких как спектральный тест и тест на к-распределении, описанный ниже, считается сильнейшим.

Определение

Говорят, что псевдослучайная последовательность xi периода P, состоящая из w-битных целых, имеет k-распределение с v-битной точностью, если она удовлетворяет следующему условию:
Пусть truncv(x) — число, образованное первыми v битами последовательности xi, рассмотрим P векторов вида[11]  (\text{trunc}_v(x_i), \, \text{trunc}_v(x_{i+1}), \, ..., \, \text{trunc}_v(x_{i+k-1})) \quad (0\leq i< P) , длиной kv бит.
Тогда каждая из 2kv возможных комбинаций битов встречается равное число раз, за исключением комбинации, состоящей полностью из нулей, которая встречается на один раз меньше.

Геометрическая интерпретация

Для каждого v = 1, 2,., w, пусть k(v) — максимальное число, такое, что последовательность является к-распределенной с v-битной точностью. Разделим каждое целое xi на 2w для нормализации в псевдослучайное вещественное число xi из интервала [0, 1]. Поместим P точек в k- мерный куб с координатами (xi, xi+1…, xi+k-1)(i = 0, 1,…, P-1) для всего периода. Каждая из осей данного k-мерного куба разделена на 2v интервалов. Таким образом, мы разделили куб на 2kv малых куба. Последовательность является к-распределенной с v-битной точностью, если каждый малый куб содержит равное число точек, кроме куба в начале координат, который содержит на одну меньше точек. Следовательно, чем выше k(v) для каждого v, тем более многомерным будет распределение с v-битной точностью. Под тестом на k-распределение, мы будем понимать получение значений k(v).

Описание

x будем обозначать векторы-слова, которые представляют собой w-мерные векторы над полем F_{2} = {0,1} , соответствующие машинному слову размера w. Вихрь Мерсенна генерирует последовательность вектор-слов, которые являются псевдослучайными целыми из диапазона от 0 до 2w - 1. Путем деления на 2w - 1 мы получим псевдослучайное вещественное из диапазона [0,1]. Алгоритм основан на следующем рекуррентном выражении:

x_{k+n} := x_{k+m} \oplus ({x_k}^u \mid {x_{k+1}}^l) A \qquad(1) \qquad k=0,1,\ldots

Где:

  • n-целое, которое обозначает степень рекуррентности
  • m-целое, 1 ≤ m ≤ n
  • A- матрица размера w×w, с элементами из F_{2}.
  • \mid — Побитовое ИЛИ (OR)
  • \oplus — Сложение по модулю два (XOR)

В правой части xku обозначает «старшие w-r бит» xk и xk+1l ≪младшие r бит≫ xk+1. Вектор (xku | xk+1l) является конкатенацией старших w-r бит xk и младших r бит xk+1. Возмьем (x0, x1,…, xn-1) в качестве начального заполнения. Тогда генератор вычислит xn по рекуррентному выражению при k= 0. Полагая k = 1,2, …, генератор вычислит xn+1, xn+2,… Форма матрицы A выбрана из расчета скорости выполнения умножения на A:


A = \begin{pmatrix}
0 & 1 & & & & \\
0 & 0 & 1 & & & \\
0 & \cdots & \cdots & \ddots & & \\
  & & & &  \ddots &  \\
  & & & & & 1\\
a_{w-1} & a_{w-2} & \cdots & \cdots & \cdots & a_{0}
\end{pmatrix}

И вычисление xA сводится к побитовым операциям:


\boldsymbol{x}A = \begin{cases}\boldsymbol{x} \gg 1 & x_0 = 0\\(\boldsymbol{x} \gg 1) \oplus \boldsymbol{a} & x_0 = 1\end{cases}

Где

\boldsymbol{x} := ({x_k}^u \mid {x_{k+1}}^l) \qquad \qquad k=0,1,\ldots
\boldsymbol{a} := ({a_{w-1}}, {a_{w-2}},\ldots ,{a_{0}})
\boldsymbol{x} := ({x_{w-1}}, {x_{w-2}},\ldots ,{x_{0}})

Неполные массивы

Неполные массивы

Последовательность МТ (xk+n, xk+n-1,…, xk+1u) образует (n × w — r)-массив. Так как r битов отбрасываются, массив называется неполным массивом[11]. Каждый элемент получен из рекуррентного соотношения (1). Смена состояния MT также происходит по линейному соотношению и определяется с помощью линейного преобразования B.

В соответствии с общей теорией линейных рекуррентных последовательностей, каждое значение в (n × w  −  r)-массиве есть линейная рекуррентная последовательность, соответствующая характеристическому многочлену φB(t) реобразования B. Матрица B имеет размеры (n × w  −  r) × (n × w  −  r) и следующую форму:


B = \begin{pmatrix}
0 & I_{w} & \cdots & 0 & 0 \\
\vdots & & & & \\
I_{w} & \vdots & \ddots & \vdots & \vdots \\
\vdots & & & & \\
0 & 0 & \cdots & I_{w} & 0 \\
0 & 0 & \cdots & 0 & I_{w - r} \\
S & 0 & \cdots & 0 & 0
\end{pmatrix}
\begin{matrix}
\\ \\ \leftarrow m\hbox{-th row} \\ \\ \\ \\
\end{matrix}


S = \begin{pmatrix} 0 & I_{r} \\ I_{w - r} & 0 \end{pmatrix} A

Где  I_{r}  — единичная матрица размера r × r.

Для  l=0,1,\ldots выполняется (x_{l+n},x_{l+n-1},\ldots,x_{l+1}) := (x_{l+n-1},x_{l+n-2},\ldots,x_{l}) B .
Характеристический многочлен φB(t) реобразования B имеет вид:[11]

 φB(t) = (tn + tm)w-r × (tn-1 + tm-1)r + a0(tn + tm)w-r × (tn-1 + tm-1)r-1 + … + ar-2(tn + tm)w-r × (tn-1 + tm-1) + ar-1(tn + tm)w-r + ar(tn + tm)w-r-1 + … + aw-2(tn + tm) + aw-1

Последовательность достигает максимального периода 2(nw-r)−1, тогда и только тогда когда φB(t) -примитивный.[11]

Закалка

Необработанные последовательности, генерируемые рекурсией (1) обладают плохим равномерным распределением на больших размерностях. Чтобы это исправить, используется метод закалки(англ. tempering )[11], на выходе которого получается итоговая псевдослучайная последовательность. Метод заключается в том, что каждое сгенерированное слово умножается справа на специальную обратимую матрицу T размера w × w. Для матрицы T: xz = x T, выбраны следующие последовательные преобразования:

y := x ⊕ (x >> u)
y := :y ⊕ ((y << s) & b)
y := :y ⊕ ((y << t) & c)
z := y ⊕ (y >> l)

где l, s, t и u — целые, а b и c — специально подобранные битовые маски размера слова, и (x≫u) обозначает побитовую операцию сдвига вправо на u бит.

Алгоритм

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

Блок-схема

Регистр сдвига состоит из 624 элементов, и в общей сложности 19937 клеток. Каждый элемент имеет длину 32 бита за исключением первого элемента, который имеет только 1 бит за счет отбрасывания бита. Процесс генерации начинается с применения битовой маски, отбрасывающей 31 бита (кроме наиболее значащих). С ледующим шагом будет инициализация (x0, x1,…, x623) любыми беззнаковыми 32-разрядными целыми числами .Следующие шаги включают в себя объединение и переходные состояния.

Смена состояния МТ

Пространство состояний имеет 19937 бит (624 х 32 — 31). Следующее состояние генерируется сдвигом одного слова вертикально вверх и вставкой нового слова в конец. Новое слово вычисляется гаммированием средней части с исключённой[12]. Выходная последовательность начинается с x624, x625,…
Алгоритм производится в шесть этапов:

 Шаг 0. Предварительно инициализируется значение констант u, h, a
  u ← 10…0   битовая маска старших w-r бит,
  h ← 01…1   битовая маска младших r бит,
  aaw-1aw-2…a0  последняя          строка матрицы A.
Шаг 1. x[0], x[1],…,x[n-1] ← начальное заполнение
Шаг 2. Вычисление (xiu | xi+1l) y ← (x[i] AND u) OR (x[(i + 1) mod n] AND h)
Шаг 3. Вычисляется значение следующего элемента последовательности по рекуррентному выражению (1) x[i] ← x[(i + m) mod n] XOR (y>>1) XOR a если младший бит y = 1
Или x[i] ← x[(i + m) mod n] XOR (y>>1) XOR 0 если младший бит y = 0 Шаг 4. Вычисление x[i]T yx[i] yy XOR (y>>u) yy XOR ((y<<s) AND b) yy XOR ((y<<t) AND c) zy XOR (y>>l) вывод y Шаг 5. i ← (i + 1) mod n
Шаг 6. Перейти к шагу 2.

Параметры 32-битного генератора MT

Параметры MT были тщательно подобраны для достижения упомянутых выше свойств. Параметры n и r выбраны так, что характеристический многочлен примитивный или nw — r равна числу Мерсенна 19937. Обратите внимание, что значение w эквивалентно размеру слова компьютера. В этом случае это 32 бита. В то время как значения n, m, r и w фиксируются, значение последней строки матрицы A выбирается случайным образом. Тогда тест на простоту целых намного проще. Так, известно много простых чисел Мерсенна (то есть простых вида 2p−1), до p=43112609 [1] . Параметры закалки (англ. tempering ) подобраны так, что мы можем получить хорошее равномерное распределение. Все параметры МТ приведены в таблице 1.

Таблица 1
n 624
w 32
r 31
m 397
a 9908B0DF16
u 11
s 7
t 15
l 18
b 9D2C568016
c EFC6000016

Другие варианты реализации

В связи с изменениями в технологии, в частности, ростом производительности процессоров, были изобретены 64-битные и 128-битные версии МТ. 64-разрядная версия была предложена Такудзи Нисимурой в 2000 году,[13] 128-разрядная − в 2006 году[14][15] тоже Такудзи Нисимурой. Обе версии имеют тот же период, что и оригинальный MT.

64-битный MT имеет две версии. Первая версия использует то же рекурсивное соотношение, во вторую версию были добавлены ещё два вектора, что увеличило количество членов характеристического многочлена:

x_{k+n} := x_{k+m2} \oplus x_{k+m1} \oplus x_{k+m0} \oplus ({x_k}^u \mid {x_{k+1}}^l) A \qquad(2)

По сравнению с 32-разрядной MT, 64-разрядная версия работает быстрее. Все параметры для 64-битной версии приведены в таблице 2.

Таблица 2
ID Для рекурсивного соотношения (1) Для рекурсивного соотношения (2)
n 312 312 312 312 312
w 64 64 64 64 64
r 31 31 31 31 31
m 156 156
m0 63 63 63
m1 151 151 151
m2 224 224 224
a B5026F5AA96619E916 F6A3F020F058B7A716 B3815B624FC82E2F16 8EBD4AD46CB39A1E16 CACB98F78EBCD4ED16
b D66B5EF5B4DA000016 28AAF6CDBDB4000016 599CFCBFCA66000016 656BEDFFD9A4000016 A51DBEFFDA6C000016
c FDED6BE00000000016 FDEDEAE00000000016 FFFAAFFE0000000016 FDFECE7E0000000016 FFEE9BF60000000016
u 29 29 26 26 26
s 17 17 17 17 17
t 37 37 33 33 33
l 41 41 39 39 39

Реализации на разных языках программирования

Примечания

  1. Twisted GFSR generators
  2. boost/random/mersenne_twister.hpp. Boost C++ Libraries. Архивировано из первоисточника 19 ноября 2012. Проверено 29 мая 2012.
  3. Changes to GLib. GLib Reference Manual. Архивировано из первоисточника 19 ноября 2012. Проверено 29 мая 2012.
  4. 9.6 random — Generate pseudo-random numbers. Python v2.6.8 documentation. Архивировано из первоисточника 19 ноября 2012. Проверено 29 мая 2012.
  5. 8.6 random — Generate pseudo-random numbers. Python v3.2 documentation. Архивировано из первоисточника 19 ноября 2012. Проверено 29 мая 2012.
  6. "Random" class documentation. Ruby 1.9.3 documentation. Проверено 29 мая 2012.
  7. Random Number Generators. CRAN Task View: Probability Distributions. Архивировано из первоисточника 19 ноября 2012. Проверено 29 мая 2012.
  8. mt_srand. php documentation. Архивировано из первоисточника 19 ноября 2012. Проверено 29 мая 2012.
  9. Updating Your Random Number Generator Syntax. R2012a Documentation.(недоступная ссылка — история) Проверено 25 июля 2012.
  10. CryptMT Stream Cipher
  11. 1 2 3 4 5 Mersenne twister: A 623-dimensionally equidistributed uniform pseudorandom number generator
  12. Cryptographic Mersenne Twister and Fubuki Stream/Block Cipher
  13. T. Nishimura.Tables of 64-bit Mersenne twisters
  14. SIMD-oriented Fast Mersenne Twister (SFMT)
  15. SFMT:Comparison of speed

Литература

  1. M. Matsumoto, T. Nishimura (1998). «Mersenne twister: A 623-dimensionally equidistributed uniform pseudorandom number generator». ACM Trans. on Modeling and Computer Simulations 8 (1): 3-30. DOI:10.1145/272991.272995.
  2. Matsumoto, M.; Kurita, Y. (1992). «Twisted GFSR generators». ACM Trans. on Modeling and Computer Simulations 2 (3): 179-194. DOI:10.1145/146382.146383.
  3. Matsumoto, Makoto; Nishimura, Takuji; Hagita, Mariko; Saito, Mutsuo (2005). «Cryptographic Mersenne Twister and Fubuki Stream/Block Cipher».
  4. T. Nishimura (200). «Tables of 64-bit Mersenne twisters». ACM Trans. on Modeling and Computer Simulations 10 (4): 248-357. DOI:10.1145/369534.369540.
  5. Matsumoto M., Saito M., Nishimura T., Hagita M.. «CryptMT Stream Cipher Ver. 3.The eSTREAM Project».

Ссылки

  1. The academic paper for MT, and related articles by Makoto Matsumoto
  2. Mersenne Twister home page, with C code (англ.)
  3. Cuba — a library for multidimensional numerical integration
  4. The Mersenne Twister (англ.)
  5. Mersenne Primes:History, Theorems and Lists (англ.)

Wikimedia Foundation. 2010.

Смотреть что такое "Вихрь Мерсенна" в других словарях:

  • Вихрь — порывистое круговое движение ветра. перен. cтремительное течение, развитие или бурное проявление чего либо. быстрая смена чувств, мыслей и т.п. в природе: Вихрь  природное явление. Вихри в океане (англ. Eddy) в математике: Вихрь… …   Википедия

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

  • Числа Мерсенна — числа вида , где натуральное число. Названы в честь французского математика Марена Мерсенна. Последовательность чисел Мерсенна начинается так: 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, … (последовательность A000225 в OEIS) Иногда числами Мерсенна …   Википедия

  • Вихри — Вихрь (англ. Whirlwind)  природное явление. Кроме того: Вихрь Мерсенна Артиллерия Вихрь (Warhammer 40,000) Березняк, Евгений Степанович Вихрь антитеррор ПТРК «Вихрь» ПТУРС «Вихрь» «Вихрь»  марка советского/российского подвесного лодочного мотора …   Википедия

  • GIMPS — Платформа своя Объём загружаемого ПО 1,1 МБ Объём загружаемых данных задания <1 КБ Объём отправляемых данных задания <1 КБ Объём места на диске 20 МБ Используемый объём памяти 25 МБ (TF), 45 МБ (PM1 1), 350 МБ (PM1 2), 25 МБ (LL)… …   Википедия

  • Простое число — Простое число  это натуральное число, имеющее ровно два различных натуральных делителя: единицу и само себя. Все остальные натуральные числа, кроме единицы, называются составными. Таким образом, все натуральные числа больше единицы… …   Википедия

  • Датчик случайных чисел — Генератор псевдослучайных чисел (ГПСЧ, англ. Pseudorandom number generator, PRNG)  алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).… …   Википедия

  • Криптостойкий генератор псевдослучайных чисел — Генератор псевдослучайных чисел (ГПСЧ, англ. Pseudorandom number generator, PRNG)  алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).… …   Википедия

  • Псевдослучайное число — Генератор псевдослучайных чисел (ГПСЧ, англ. Pseudorandom number generator, PRNG)  алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).… …   Википедия

  • Псевдослучайные числа — Генератор псевдослучайных чисел (ГПСЧ, англ. Pseudorandom number generator, PRNG)  алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).… …   Википедия