Просмотр кода страницы Вихрь Мерсенна

'''Вихрь Мерсе́нна''' ({{lang-en|Mersenne twister}}, MT) — [[генератор псевдослучайных чисел]] (ГПСЧ), [[алгоритм]], разработанный в [[1997 год]]у японскими учёными Макото Мацумото ({{lang-ja|松本 眞}}) и Такудзи Нисимура ({{lang-ja|西村 拓士}}). Вихрь Мерсенна генерирует псевдослучайные последовательности чисел с периодом, равным одному из простых [[Число Мерсенна|чисел Мерсенна]], отсюда этот алгоритм и получил своё название, и обеспечивает быструю генерацию высококачественных по критерию случайности псевдослучайных чисел.

Вихрь Мерсенна лишён многих недостатков, присущих другим ГПСЧ, таких как малый период, [[детерминированность]], легко выявляемые статистические закономерности.

Тем не менее, этот генератор не является [[криптостойкость|криптостойким]], что ограничивает его использование в [[криптография|криптографии]].

Существуют по меньшей мере два общих варианта алгоритма, различающихся только величиной используемого [[Число Мерсенна|простого числа Мерсенна]], наиболее распространённым из которых является алгоритм ''MT19937'', период которого составляет 2<sup>19937</sup> − 1 (приблизительно 4,3•10<sup>6001</sup>).

== Свойства ==
Вихрь Мерсенна является витковым регистром сдвига с обобщённой отдачей (TGFSR){{sfn|Twisted GFSR generators|1992}} ({{lang-en|twisted generalised feedback shift register}}). «Вихрь» — это преобразование, которое обеспечивает [[дискретное равномерное распределение|равномерное распределение]] генерируемых псевдослучайных чисел в 623 измерениях (для [[линейный конгруэнтный метод|линейных конгруэнтных генераторов]] оно ограничено 5 измерениями). Поэтому функция корреляции между двумя последовательностями выборок в выходной последовательности вихря Мерсенна пренебрежимо мала.

[[Псевдослучайная последовательность]], порождаемая вихрем Мерсенна, имеет очень большой период, равный числу Мерсенна, что более чем достаточно для многих практических приложений.

Существуют эффективные реализации Вихря Мерсенна, превосходящие по скорости многие стандартные ГПСЧ (в частности, в 2—3 раза быстрее линейных конгруэнтных генераторов). Алгоритм вихря Мерсенна реализован в программной библиотеке [[Boost]]<ref>
{{cite web
 |title       = boost/random/mersenne_twister.hpp
 |work        = Boost C++ Libraries
 |url         = http://www.boost.org/doc/libs/1_49_0/boost/random/mersenne_twister.hpp
 |accessdate  = 2012-05-29
 |archiveurl  = https://www.webcitation.org/6CIQRpwZz?url=http://www.boost.org/doc/libs/1_49_0/boost/random/mersenne_twister.hpp
 |archivedate = 2012-11-19
}}</ref>, [[Glib]]<ref>{{cite web
 |title       = Changes to GLib
 |work        = GLib Reference Manual
 |url         = http://developer.gnome.org/glib/stable/glib-changes.html
 |accessdate  = 2012-05-29
 |archiveurl  = https://www.webcitation.org/6CIQSeThc?url=http://developer.gnome.org/glib/stable/glib-changes.html
 |archivedate = 2012-11-19
}}</ref> и стандартных библиотеках для [[C++]], [[Python]]<ref>{{cite web
 |title       = 9.6 random — Generate pseudo-random numbers
 |work        = Python v2.6.8 documentation
 |url         = http://docs.python.org/release/2.6.8/library/random.html
 |accessdate  = 2012-05-29
 |archiveurl  = https://www.webcitation.org/6CIQTPrJR?url=http://docs.python.org/release/2.6.8/library/random.html
 |archivedate = 2012-11-19
}}</ref><ref>{{cite web
 |title       = 8.6 random — Generate pseudo-random numbers
 |work        = Python v3.2 documentation
 |url         = http://docs.python.org/release/2.6.8/library/random.html
 |accessdate  = 2012-05-29
 |archiveurl  = https://www.webcitation.org/6CIQTPrJR?url=http://docs.python.org/release/2.6.8/library/random.html
 |archivedate = 2012-11-19
}}</ref><ref>{{cite web
 | title      = random — Generate pseudo-random numbers — Python 3.8.3 documentation
 | work      = Python 3.8.3 documentation
 | url      = https://docs.python.org/3/library/random.html
 | accessdate      = 2020-06-23
 | archive-date      = 2021-07-28
 | archive-url      = https://web.archive.org/web/20210728124929/https://docs.python.org/3/library/random.html
 | deadlink      = no
 }}</ref>, [[Ruby]]<ref>{{cite web|title="Random" class documentation|work=Ruby 1.9.3 documentation|url=http://www.ruby-doc.org/core-1.9.3/Random.html|accessdate=2012-05-29|archive-date=2021-06-26|archive-url=https://web.archive.org/web/20210626184033/https://ruby-doc.org/core-1.9.3/Random.html|deadlink=no}}</ref>, [[R (язык программирования)|R]]<ref>{{cite web
 |title       = Random Number Generators
 |work        = CRAN Task View:  Probability Distributions
 |url         = http://cran.r-project.org/web/views/Distributions.html
 |accessdate  = 2012-05-29
 |archiveurl  = https://www.webcitation.org/6CIQUW4o8?url=http://cran.r-project.org/web/views/Distributions.html
 |archivedate = 2012-11-19
}}</ref>, [[PHP]]<ref>{{cite web
 |title       = mt_srand
 |work        = php documentation
 |url         = http://php.net/manual/en/function.mt-srand.php
 |accessdate  = 2012-05-29
 |archiveurl  = https://www.webcitation.org/6CIQVoON9?url=http://php.net/manual/en/function.mt-srand.php
 |archivedate = 2012-11-19
}}</ref>, [[MATLAB]]<ref>{{cite web
 |title       = Control random number generation (RNG)
 |work        = Matlab Documentation
 |url         = http://mathworks.com/help/matlab/ref/rng.html?searchHighlight=twister
 |accessdate  = 2015-11-23
 |deadlink    = 
 |archiveurl  = https://web.archive.org/web/20100912151657/http://www.mathworks.com/help/techdoc/math/bsn94u0-1.html
 |archivedate = 2010-09-12
}}</ref>, [[AutoIt|Autoit]]<ref>{{Cite web |url=http://www.autoitscript.com/autoit3/docs/functions/Random.htm |title=Function Random<!-- Заголовок добавлен ботом --> |access-date=2014-03-22 |archive-date=2021-04-06 |archive-url=https://web.archive.org/web/20210406183153/https://www.autoitscript.com/autoit3/docs/functions/Random.htm |deadlink=no }}</ref>.

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

Генератор не предназначен для получения [[Криптографически стойкий генератор псевдослучайных чисел|криптографически стойких случайных последовательностей чисел]]. Для обеспечения криптостойкости выходную последовательность генератора необходимо подвергнуть обработке одним из криптографических алгоритмов хеширования{{sfn|CryptMT Stream Cipher}}.

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

=== Определение ===
Говорят, что псевдослучайная последовательность '''''x'''<sub>i</sub>'' периода ''P'', состоящая из ''w''-битных целых, имеет ''k''-распределение с ''v''-битной точностью, если она удовлетворяет следующему условию:<br>
Пусть ''trunc<sub>v</sub>(x)'' — число, образованное первыми ''v'' битами последовательности ''x<sub>i</sub>'', рассмотрим ''P'' векторов вида{{sfn|Matsumoto, Nishimura|2017|name="twister"}} <math> (\text{trunc}_v(x_i), \, \text{trunc}_v(x_{i+1}), \, ..., \, \text{trunc}_v(x_{i+k-1})) \quad (0\leq i< P) </math>, длиной ''kv'' бит. <br>
Тогда каждая из ''2<sup>kv</sup>'' возможных комбинаций битов встречается равное число раз, за исключением комбинации, состоящей полностью из нулей, которая встречается на один раз меньше.

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

== Описание ==
'''''x''''' будем обозначать ''w''-мерные векторы над [[конечное поле|полем <math>F_{2}</math> = {0,1}]], соответствующие [[машинное слово|машинным словам]] размера ''w''.
Вихрь Мерсенна генерирует последовательность векторов, которые являются псевдослучайными целыми из диапазона от 0 до 2<sup>w</sup> — 1. Путём деления на 2<sup>w</sup> — 1 можно также получить псевдослучайное [[вещественное число]] из диапазона [0,1].

Алгоритм основан на следующей [[рекуррентная формула|рекуррентной формуле]]:
: <math>x_{k+n} := x_{k+m} \oplus ({x_k}^u \mid {x_{k+1}}^l) A, \qquad k=0,1,\ldots \qquad(1)</math>
где:
* ''n'' — целое, которое обозначает порядок [[Рекуррентная формула|рекуррентности]],
* ''m'' — целое, ''1 ≤ m < n'',
* ''A'' — матрица размера ''w×w'', с элементами из <math>F_{2}</math>,
* <math>\mid</math> — [[побитовое ИЛИ]] (OR),
* <math>\oplus</math> — [[сложение по модулю два]] (XOR).

В правой части '''''x'''<sub>k</sub><sup>u</sup>'' обозначает «старшие ''w-r'' бит» '''''x'''<sub>k</sub>'' и '''''x'''<sub>k+1</sub><sup>l</sup>'' «младшие ''r'' бит» '''''x'''<sub>k+1</sub>''. Вектор ''('''x'''<sub>k</sub><sup>u</sup> | '''x'''<sub>k+1</sub><sup>l</sup>)'' является конкатенацией старших ''w-r'' бит '''''x'''<sub>k</sub>'' и младших ''r'' бит '''''x'''<sub>k+1</sub>''. Возьмём ''('''x'''<sub>0</sub>, '''x'''<sub>1</sub>,…, '''x'''<sub>n-1</sub>)'' в качестве начального заполнения. Тогда генератор вычислит '''''x'''<sub>n</sub>'' по рекуррентному выражению при ''k''= 0. Полагая ''k'' = 1,2, …, генератор вычислит ''x<sub>n+1</sub>'', '''''x'''<sub>n+2</sub>'',…
Форма матрицы ''A'' выбрана из расчета скорости выполнения умножения на ''A'':
: <math>
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}
</math>

И вычисление '''''x'''A'' сводится к побитовым операциям:
: <math>
\boldsymbol{x}A = \begin{cases}\boldsymbol{x} \gg 1 & x_0 = 0\\(\boldsymbol{x} \gg 1) \oplus \boldsymbol{a} & x_0 = 1\end{cases}
</math>
где
: <math>\boldsymbol{x} := ({x_k}^u \mid {x_{k+1}}^l) \qquad \qquad k=0,1,\ldots</math>
: <math>\boldsymbol{a} := ({a_{w-1}}, {a_{w-2}},\ldots ,{a_{0}})</math>
: <math>\boldsymbol{x} := ({x_{w-1}}, {x_{w-2}},\ldots ,{x_{0}})</math>

=== Неполные массивы ===
[[Файл:Неполные массивы.png|thumb|Неполные массивы]]
Последовательность МТ ''('''x'''<sub>k+n</sub>, '''x'''<sub>k+n-1</sub>,…, '''x'''<sub>k+1</sub><sup>u</sup>)'' образует ''(n × w — r)''-массив. Так как ''r'' битов отбрасываются, массив называется неполным массивом<ref name="twister" />. Каждый элемент получен из рекуррентного соотношения (1). Смена состояния MT также происходит по линейному соотношению и определяется с помощью линейного преобразования ''B''.

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

<math>
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}
</math>

<math>
S = \begin{pmatrix} 0 & I_{r} \\ I_{w - r} & 0 \end{pmatrix} A
</math>

Где <math> I_{r} </math> — [[единичная матрица]] размера ''r'' × ''r''.

Для <math> l=0,1,\ldots</math> выполняется <math>(x_{l+n},x_{l+n-1},\ldots,x_{l+1}) := (x_{l+n-1},x_{l+n-2},\ldots,x_{l}) B </math>.<br>
Характеристический многочлен ''φ''<sub>''B''</sub>(''t'') преобразования ''B'' имеет вид<ref name="twister" />:

<math>
\Phi_B(t) = (t^n + t^m)^{w-r} \cdot (t^{n-1} + t^{m-1})^r + a_0(t^n + t^m)^{w-r} \cdot (t^{n-1} + t^{m-1})^{r-1} + ... + a_{r-2}(t^n + t^m)^{w-r} \cdot (t^{n-1} + t^{m-1}) + a_{r-1}(t^n + t^m)^{w-r} + a_r(t^n + t^m)^{w-r-1} + ... + a_{w-2}(t^n + t^m) + a_{w-1}
</math>

Последовательность достигает максимального периода 2<sup>(''nw-r'')</sup>−1, тогда и только тогда когда ''φ''<sub>''B''</sub>(''t'') -примитивный<ref name="twister" />.

=== Закалка ===
Необработанные последовательности, генерируемые рекурсией (1), обладают плохим равномерным распределением на больших размерностях. Чтобы это исправить, используется метод ''закалки'' ({{lang-en|tempering}})<ref name="twister" />, на выходе которого получается итоговая псевдослучайная последовательность. Метод заключается в том, что каждое сгенерированное слово умножается справа на специальную обратимую матрицу ''T'' размера ''w'' × ''w''. Для матрицы ''T'': '''''x''''' → '''''z''''' = '''''x''''' ''T'', выбраны следующие последовательные преобразования:
: '''''y''''' := '''''x''''' ⊕ ('''''x''''' >> ''u'')
: '''''y''''' := :'''''y''''' ⊕ (('''''y''''' << ''s'') &amp; '''''b''''')
: '''''y''''' := :'''''y''''' ⊕ (('''''y''''' << ''t'') &amp; '''''c''''')
: '''''z''''' := '''''y''''' ⊕ ('''''y''''' >> ''l'')

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

== Алгоритм ==
Вихрь Мерсенна алгоритмически реализуется двумя основными частями: ''рекурсивной'' и ''закалки''. Рекурсивная часть представляет собой [[регистр сдвига с линейной обратной связью]], в котором все биты в его слове определяются рекурсивно; поток выходных битов определяются также рекурсивно функцией битов состояния.
[[Файл:Блок схема МТ.png|thumb|Блок-схема.]]
Регистр сдвига состоит из 624 элементов, и, в общей сложности, из 19937 клеток. Каждый элемент имеет длину 32 бита за исключением первого элемента, который имеет только 1 бит за счет отбрасывания бита.

Процесс генерации начинается с логического умножения на битовую маску, отбрасывающей 31 бита (кроме наиболее значащих).

Следующим шагом выполняется инициализация ''('''x'''<sub>0</sub>, '''x'''<sub>1</sub>,…, '''x'''<sub>623</sub>)'' любыми беззнаковыми 32-разрядными целыми числами. Следующие шаги включают в себя объединение и переходные состояния.
[[Файл:Смена состояния МТ.png|thumb|Смена состояния МТ.]]

Пространство состояний имеет 19937 бит (624·32 — 31). Следующее состояние генерируется сдвигом одного слова вертикально вверх и вставкой нового слова в конец. Новое слово вычисляется гаммированием средней части с исключённой{{sfn|Cryptographic Mersenne Twister and Fubuki Stream/Block Cipher|2005}}. Выходная последовательность начинается с '''''x'''<sub>624</sub>, '''x'''<sub>625</sub>'',…

Алгоритм производится в шесть этапов:

  '''Шаг 0.''' Предварительно инициализируется значение констант ''u1'', ''h1'', ''a''
   ''u1''&nbsp;&larr;&nbsp;10&hellip;0&nbsp;&nbsp; битовая маска старших ''w-r'' бит,
   ''h1''&nbsp;&larr;&nbsp;01&hellip;1&nbsp;&nbsp; битовая маска младших ''r'' бит,
   ''a''&nbsp;&larr;&nbsp;''a<sub>w-1</sub>a<sub>w-2</sub>&hellip;a<sub>0</sub>''&nbsp;&nbsp;последняя          строка матрицы ''A''.<br>
  '''Шаг 1.''' '''''x'''''[0], '''''x'''''[1],&hellip;,'''''x'''''[n-1]&nbsp;&larr;&nbsp; начальное    заполнение<br>
  '''Шаг 2.''' Вычисление ''('''x'''<sub>i</sub><sup>u</sup> | '''x'''<sub>i+1</sub><sup>l</sup>)''
   '''''y'''''&nbsp;&larr;&nbsp;('''''x'''''[i] AND ''u1'') OR ('''''x'''''[(i + 1) mod n] AND ''h''1)<br>
  '''Шаг 3.''' Вычисляется значение следующего элемента последовательности по 
  рекуррентному выражению (1)
   '''''x'''''[i]&nbsp;&larr;&nbsp;'''''x'''''[(i + m) mod n] XOR ('''''y'''''>>1) XOR ''a''&nbsp;&nbsp;  если младший бит '''''y''''' = 1<br>
   Или
   '''''x'''''[i]&nbsp;&larr;&nbsp;'''''x'''''[(i + m) mod n] XOR ('''''y'''''>>1) XOR 0&nbsp;&nbsp; если  младший бит '''''y''''' = 0
  '''Шаг 4.''' Вычисление '''''x'''''[i]''T''
   '''''y'''''&nbsp;&larr;&nbsp;'''''x'''''[i]
   '''''y'''''&nbsp;&larr;&nbsp;'''''y''''' XOR ('''''y'''''>>''u'')
   '''''y'''''&nbsp;&larr;&nbsp;'''''y''''' XOR (('''''y'''''<<''s'') AND '''b''')
   '''''y'''''&nbsp;&larr;&nbsp;'''''y''''' XOR (('''''y'''''<<''t'') AND '''c''')
   '''''z'''''&nbsp;&larr;&nbsp;'''''y''''' XOR ('''''y'''''>>''l'')
   вывод '''''z'''''
  '''Шаг 5.''' i&nbsp;&larr;&nbsp;(i + 1) mod n <br>
  '''Шаг 6.''' Перейти к шагу 2.

== Параметры 32-битного генератора MT ==
Параметры MT были тщательно подобраны для достижения упомянутых выше свойств. Параметры ''n'' и ''r'' выбраны так, что характеристический многочлен примитивный или ''nw — r'' равна [[число Мерсенна|числу Мерсенна]] 19937. Значение ''w'' эквивалентно размеру 32-битового слова компьютера. В этом случае это 32 бита. В то время как значения ''n'', ''m'', ''r'' и ''w'' фиксируются, значение последней строки матрицы ''A'' выбирается случайным образом. Для чисел Мерсенна тест на простоту целых намного проще. Так, известно много простых чисел Мерсенна (то есть простых вида 2<sup>p</sup>−1), до p=43112609 [http://primes.utm.edu/mersenne/index.html#known] .
Параметры ''закалки'' ({{lang-en|tempering }}) подобраны так, что мы можем получить хорошее равномерное распределение. Все параметры МТ приведены в таблице 1.
{| class="standard"
|+Таблица 1
|-
|n||624
|-
|w||32
|-
|r||31
|-
|m||397
|-
|a||9908B0DF<sub>16</sub>
|-
|u||11
|-
|s||7
|-
|t||15
|-
|l||18
|-
|b||9D2C5680<sub>16</sub>
|-
|c||EFC60000<sub>16</sub>
|}

== Другие варианты реализации ==
В связи с изменениями в технологии, в частности, ростом производительности процессоров, были изобретены 64-битные и 128-битные версии МТ. 64-разрядная версия была предложена Такудзи Нисимурой в 2000 году,{{sfn|Nishimura|2000}} 128-разрядная − в 2006 году<ref>{{Cite web |url=http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html |title=SIMD-oriented Fast Mersenne Twister (SFMT)<!-- Bot generated title --> |access-date=2012-11-15 |archive-date=2020-11-09 |archive-url=https://web.archive.org/web/20201109030227/http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html |deadlink=no }}</ref><ref>{{Cite web |url=http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/speed.html |title=SFMT:Comparison of speed<!-- Bot generated title --> |access-date=2012-11-15 |archive-date=2020-01-08 |archive-url=https://web.archive.org/web/20200108013735/http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/speed.html |deadlink=no }}</ref> тоже Такудзи Нисимурой. Обе версии имеют тот же период, что и оригинальный MT.

64-битный MT имеет две версии. Первая версия использует то же рекурсивное соотношение, во вторую версию были добавлены ещё два вектора, что увеличило количество членов характеристического многочлена:
: <math>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) </math>
По сравнению с 32-разрядной MT, 64-разрядная версия работает быстрее. Все параметры для 64-битной версии приведены в таблице 2.
{| class="standard"
|+Таблица 2
|-
!ID
!colspan="2" |Для рекурсивного соотношения (1)
!colspan="3" |Для рекурсивного соотношения (2)
|-
|n
|312
|312
|312
|312
|312
|-
|w
|64
|64
|64
|64
|64
|-
|r
|31
|31
|31
|31
|31
|-
|m
|156
|156
|colspan="3"|
|-
|m<sub>0</sub>
|colspan="2"|
|63
|63
|63
|-
|m<sub>1</sub>
|colspan="2"|
|151
|151
|151
|-
|m<sub>2</sub>
|colspan="2"|
|224
|224
|224
|-
|a
|B5026F5AA96619E9<sub>16</sub>
|F6A3F020F058B7A7<sub>16</sub>
|B3815B624FC82E2F<sub>16</sub>
|8EBD4AD46CB39A1E<sub>16</sub>
|CACB98F78EBCD4ED<sub>16</sub>
|-
|b
|D66B5EF5B4DA0000<sub>16</sub>
|28AAF6CDBDB40000<sub>16</sub>
|599CFCBFCA660000<sub>16</sub>
|656BEDFFD9A40000<sub>16</sub>
|A51DBEFFDA6C0000<sub>16</sub>
|-
|c
|FDED6BE000000000<sub>16</sub>
|FDEDEAE000000000<sub>16</sub>
|FFFAAFFE00000000<sub>16</sub>
|FDFECE7E00000000<sub>16</sub>
|FFEE9BF600000000<sub>16</sub>
|-
|u
|29
|29
|26
|26
|26
|-
|s
|17
|17
|17
|17
|17
|-
|t
|37
|37
|33
|33
|33
|-
|l
|41
|41
|39
|39
|39
|}

== Примечания ==
{{примечания|27em}}

== Литература ==
* {{статья |ref=Matsumoto, Nishimura |<!-- year=19914870800021--> |заглавие=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 |язык=en |тип=journal |автор=M. Matsumoto, T. Nishimura |год=1998}}
* {{статья |заглавие=Twisted GFSR generators |издание=ACM Trans. on Modeling and Computer Simulations |том=2 |номер=3 |страницы=179—194 |doi=10.1145/146382.146383 |ref=Twisted GFSR generators |язык=und |автор=Matsumoto, M.; Kurita, Y. |год=1992}}
* {{статья |заглавие=Cryptographic Mersenne Twister and Fubuki Stream/Block Cipher |ссылка=http://eprint.iacr.org/2005/165.pdf |ref=Cryptographic Mersenne Twister and Fubuki Stream/Block Cipher |язык=en |тип=journal |автор=Matsumoto, Makoto; Nishimura, Takuji; Hagita, Mariko; Saito, Mutsuo |год=2005}}
* {{статья |заглавие=Tables of 64-bit Mersenne twisters |издание=ACM Trans. on Modeling and Computer Simulations |том=10 |номер=4 |страницы=248—357 |doi=10.1145/369534.369540 |ref=Nishimura |язык=und |автор=T. Nishimura |год=2000}}
* {{статья |заглавие=CryptMT Stream Cipher Ver. 3.The eSTREAM Project |ссылка=http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/cryptMT3-book1.pdf |ref=CryptMT Stream Cipher |язык=und |автор=Matsumoto M., Saito M., Nishimura T., Hagita M.}}

== Ссылки ==
* Makoto Matsumoto, [http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/earticles.html Academic publications on MT]{{ref-en}}
* [https://web.archive.org/web/20070828025507/http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html Mersenne Twister home page, with C code]{{ref-en}}
* [http://www.feynarts.de/cuba/ Cuba — a library for multidimensional numerical integration]
* [http://www.quadibloc.com/crypto/co4814.htm The Mersenne Twister]{{ref-en}}
{{Нерабочие сноски|дата=2017-04-07}}

[[Категория:Генераторы псевдослучайных чисел]]