Перегляд вихідного коду сторінки Вихор Мерсенна

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

Вихор Мерсенна позбавлений багатьох недоліків, властивих іншим ГПВЧ, таких як малий період, передбачуваність, легко відшукувані статистичні закономірності.

Проте, цей генератор не є [[Криптографічна стійкість|криптостійким]], що обмежує його використання в [[Криптографія|криптографії]].

Існують принаймні два загальних варіанти [[алгоритм]]у, що відрізняються тільки величиною використовуваного [[Число Мерсенна|простого числа Мерсенна]], найпоширенішим з яких є алгоритм ''MT19937'', період якого становить 2<sup>19937</sup>&nbsp;— 1 (приблизно 4,3·10<sup>6001</sup>).

== Властивості ==
Вихор Мерсенна є витковим регістром зсуву з узагальненою віддачею (TGFSR){{Sfn|Twisted GFSR generators|1992}} ({{Lang-en|twisted generalised feedback shift register}}). «Вихор»&nbsp;— це перетворення, яке забезпечує [[Дискретний рівномірний розподіл|рівномірний розподіл]] генерованих псевдовипадкових чисел у 623 вимірах (для [[Лінійний конгруентний метод|лінійних конгруентних генераторів]] його обмежено 5 вимірами). Тому функція кореляції між двома послідовностями вибірок у вихідній послідовності вихору Мерсенна мізерно мала.

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

Існують ефективні реалізації вихору Мерсенна, що перевершують за швидкістю багато стандартних ГПВЧ (зокрема, в 2-3 рази швидше від лінійних конгруентних генераторів). Алгоритм вихору Мерсенна реалізовано в програмній бібліотеці [[Boost]]<ref>
{{Cite web|title=boost/random/mersenne_twister.hpp|website=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|Glib]]<ref>{{Cite web|title=Changes to GLib|website=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|website=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|website=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|website=Python 3.8.3 documentation|url=https://docs.python.org/3/library/random.html|accessdate=2020-06-23|archive-date=28 липня 2021|archive-url=https://web.archive.org/web/20210728124929/https://docs.python.org/3/library/random.html}}</ref>, [[Ruby]]<ref>{{Cite web|title="Random" class documentation|website=Ruby 1.9.3 documentation|url=http://www.ruby-doc.org/core-1.9.3/Random.html|accessdate=2012-05-29|archive-date=26 червня 2021|archive-url=https://web.archive.org/web/20210626184033/https://ruby-doc.org/core-1.9.3/Random.html}}</ref>, [[R (мова програмування)|R]]<ref>{{Cite web|title=Random Number Generators|website=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|website=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)|website=Matlab Documentation|url=http://mathworks.com/help/matlab/ref/rng.html?searchHighlight=twister|accessdate=2015-11-23|deadurl=|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 |accessdate=28 липня 2021 |archive-date=6 квітня 2021 |archive-url=https://web.archive.org/web/20210406183153/https://www.autoitscript.com/autoit3/docs/functions/Random.htm }}</ref>.

Видавані вихором Мерсенна послідовності псевдовипадкових чисел успішно проходять статистичні [[тести Diehard]], що підтверджує їхні хороші статистичні властивості.

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

== ''K''-розподіл ==
Запропоновано багато генераторів можливо «високої якості», але тільки деякі можна використати для серйозного моделювання через відсутність чіткого поняття «хаотичності» для генераторів псевдовипадкових чисел, оскільки кожен дослідник концентрується на конкретних параметрах хаотичності. Серед багатьох відомих мір, тести, засновані на вищому рівномірному розподілі, такі як спектральний тест і тест на ''k''-розподілі, описаний нижче, вважаються найсильнішими.

=== Визначення ===
Кажуть, що псевдовипадкова послідовність '''''x'''<sub>i</sub>'' з періодом ''P'', що складається з ''w''-бітових цілих, має ''k''-розподіл з ''v''-бітовою точністю, якщо вона задовольняє такій умові: Нехай ''trunc<sub>v</sub>''(''x'')&nbsp;— число, утворене першими ''v'' бітами послідовності ''x<sub>i</sub>'', розглянемо ''P'' з ''k'' ''v''-бітових векторів вигляду{{Sfn|Matsumoto, Nishimura|2017}} <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>. Тоді кожна з ''2<sup>kv</sup>'' можливих комбінацій бітів зустрічається рівне число разів, за винятком комбінації, що складається повністю з нулів, яка зустрічається на один раз менше.

=== Геометрична інтерпретація ===
Для кожного ''v'' = 1, 2,., ''w'', нехай ''k(v)''&nbsp;— найбільше число, таке, що послідовність є ''k''-розподіленою з ''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>'' малих кубів. Послідовність є ''k''-розподіленою з ''v''-бітовою точністю, якщо кожен малий куб містить рівне число точок, крім куба в початку координат, який містить на одну точку менше. Отже, чим вище ''k''(''v'') для кожного ''v'', тим більше вимірів матиме розподіл з ''v''-бітовою точністю. Під тестом на ''k''-розподіл будемо розуміти отримання значень ''k''(''v'').

== Опис ==
'''''x''''' позначатимемо ''w''-вимірні вектори над [[Поле Галуа|полем <math>F_{2}</math> = {0,1}]], відповідні [[Машинне слово|машинним словам]] розміру ''w''. Вихор Мерсенна генерує послідовність векторів, які є псевдовипадковими цілими з діапазону від 0 до 2<sup>w</sup>&nbsp;— 1. Діленням на 2<sup>w</sup>&nbsp;— 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''&nbsp;— ціле, яке позначає порядок рекурентності,
* ''m''&nbsp;— ціле, ''1 ≤ m < n'',
* ''A''&nbsp;— матриця розміру ''w×w'', з елементами з <math>F_{2}</math>,
* <math>\mid</math>&nbsp;— [[Бітові операції|побітове АБО]] (OR),
* <math>\oplus</math>&nbsp;— [[Виключна диз'юнкція|додавання за модулем два]] (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|міні|Неповні масиви]]
Послідовність МТ ('''''x'''<sub>k+n</sub>, '''x'''<sub>k+n-1</sub>,…, '''x'''<sub>k+1</sub><sup>u</sup>'') утворює (''n × w&nbsp;— r'')-масив. Оскільки ''r'' бітів відкидаються, масив називають неповним масивом. Кожен елемент отримано з рекурентного співвідношення (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>&nbsp;— одинична матриця розміру ''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>.Характеристичний многочлен ''φ''<sub>''B''</sub>(''t'') перетворення ''B'' має вигляд:

<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'')&nbsp;— примітивний.

=== Загартування ===
Необроблені послідовності, що генеруються рекурсією (1), мають поганий рівномірний розподіл на великих розмірностях. Щоб це виправити, використовується метод ''загартування'' ({{Lang-en|tempering}}), на виході якого отримують кінцеву псевдовипадкову послідовність. Метод полягає в тому, що кожне згенероване слово множиться праворуч на спеціальну оборотну матрицю ''T'' розміром ''w''×''w''. Для матриці ''T'': '''''x''''' → '''''z''''' = '''''x''''' ''T'', вибрано такі послідовні перетворення:

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

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

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

Процес генерування починається з логічного множення на бітову маску, що відкидає 31 біт (крім найбільш значущих).

Наступним кроком виконується ініціалізація ''('''x'''<sub>0</sub>, '''x'''<sub>1</sub>,…, '''x'''<sub>623</sub>)'' будь-якими беззнаковими 32-розрядними цілими числами. Наступні кроки включають об'єднання та перехідні стани.
[[Файл:Смена_состояния_МТ.png|міні|Зміна стану МТ.]]
Простір станів має 19937 біт (624·32&nbsp;— 31). Наступний стан генерується зсувом одного слова вертикально вгору і вставленням нового слова в кінець. Нове слово обчислюється [[Шифр XOR|гамуванням]] середньої частини з виключеною{{Sfn|Cryptographic Mersenne Twister and Fubuki Stream/Block Cipher|2005}}. Вихідна послідовність починається з '''''x'''<sub>624</sub>, '''x'''<sub>625</sub>'',…

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

== Параметри 32-бітового генератора MT ==
Параметри MT ретельно підібрано для досягнення згаданих вище властивостей. Параметри ''n'' і ''r'' вибрано так, що характеристичний многочлен примітивний або ''nw&nbsp;— r'' дорівнює [[Число Мерсенна|числу Мерсенна]] 19937. Зверніть увагу, що значення ''w'' еквівалентне розміру слова комп'ютера. У цьому випадку це 32 біти. Тоді як значення ''n'', ''m'', ''r'' і ''w'' фіксуються, значення останнього рядка матриці ''A'' вибирається випадковим чином. Для чисел Мерсенна тест на простоту цілих значно простіший. Так, відомо багато простих чисел Мерсенна (тобто простих виду 2<sup>p</sup>−1), до p=43112609[http://primes.utm.edu/mersenne/index.html#known] {{Webarchive|url=https://web.archive.org/web/20190313005102/https://primes.utm.edu/mersenne/index.html#known |date=13 березня 2019 }} . Параметри ''загартування'' ({{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-розрядну&nbsp;— 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) |accessdate=28 липня 2021 |archive-date=9 листопада 2020 |archive-url=https://web.archive.org/web/20201109030227/http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html }}</ref><ref>{{Cite web |url=http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/speed.html |title=SFMT: Comparison of speed |accessdate=28 липня 2021 |archive-date=8 січня 2020 |archive-url=https://web.archive.org/web/20200108013735/http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/speed.html }}</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
|}

== Примітки ==
{{Reflist|27em}}

== Література ==
* {{Стаття|<!-- year=19914870800021-->|ref=Matsumoto, Nishimura|title=Mersenne twister: A 623-dimensionally equidistributed uniform pseudorandom number generator|видання=ACM Trans. on Modeling and Computer Simulations|том=8|номер=1|pages=3—30|doi=10.1145/272991.272995|language=en|тип=journal|author=M. Matsumoto, T. Nishimura|date=2017}}
* {{Стаття|title=Twisted GFSR generators|видання=ACM Trans. on Modeling and Computer Simulations|том=2|номер=3|pages=179—194|doi=10.1145/146382.146383|ref=Twisted GFSR generators|language=und|author=Matsumoto, M.; Kurita, Y.|date=1992}}
* {{Стаття|title=Cryptographic Mersenne Twister and Fubuki Stream/Block Cipher|url=http://eprint.iacr.org/2005/165.pdf|ref=Cryptographic Mersenne Twister and Fubuki Stream/Block Cipher|language=en|тип=journal|author=Matsumoto, Makoto; Nishimura, Takuji; Hagita, Mariko; Saito, Mutsuo|date=2005|accessdate=28 липня 2021|archivedate=27 липня 2021|archiveurl=https://web.archive.org/web/20210727220236/https://eprint.iacr.org/2005/165.pdf}}
* {{Стаття|title=Tables of 64-bit Mersenne twisters|видання=ACM Trans. on Modeling and Computer Simulations|том=10|номер=4|pages=248—357|doi=10.1145/369534.369540|ref=Nishimura|language=und|author=T. Nishimura|date=2000}}
* {{Стаття|title=CryptMT Stream Cipher Ver. 3.The eSTREAM Project|url=http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/cryptMT3-book1.pdf|ref=CryptMT Stream Cipher|language=und|author=Matsumoto M., Saito M., Nishimura T., Hagita M.|accessdate=28 липня 2021|archivedate=20 липня 2020|archiveurl=https://web.archive.org/web/20200720024602/http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/cryptMT3-book1.pdf}}

== Посилання ==
* Makoto Matsumoto, [http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/earticles.html Academic publications on MT] {{Webarchive|url=https://web.archive.org/web/20200803215540/http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/earticles.html |date=3 серпня 2020 }}{{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&nbsp;— a library for multidimensional numerical integration] {{Webarchive|url=https://web.archive.org/web/20140407085022/http://www.feynarts.de/cuba/ |date=7 квітня 2014 }}
* [http://www.quadibloc.com/crypto/co4814.htm The Mersenne Twister] {{Webarchive|url=https://web.archive.org/web/20210626183914/http://www.quadibloc.com/crypto/co4814.htm |date=26 червня 2021 }}{{Ref-en}}

[[Категорія:Генератори псевдовипадкових чисел]]
[[Категорія:1997  у науці]]