вихор Мерсенна

| UK | KK | BE | EN |

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

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

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

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

зміст

• 1 Властивості
• 2 К-розподіл
  • 2.1 Визначення
  • 2.2 Геометрична інтерпретація
• 3 Опис
  • 3.1 Неповні масиви
  • 3.2 Загартування
• 4 Алгоритм
• 5 Параметри 32-бітного генератора MT
• 6 Інші варіанти реалізації
• 7 Реалізації на різних мовах програмування
• 8 Примітки
• 9 Література
• 10 Посилання

властивості

Вихор Мерсенна є виткового регістром зсуву з узагальненою віддачею (TGFSR) (англ. Twisted generalised feedback shift register). «Вихор» - це перетворення, яке забезпечує рівномірний розподіл генеруються псевдовипадкових чисел в 623 вимірах (для лінійних конгруентних генераторів воно обмежене 5-ю вимірами). Тому функція кореляції між двома послідовностями вибірок в вихідний послідовності вихору Мерсенна нехтує мала.

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

Існують ефективні реалізації Вихора Мерсенна, що перевершують за швидкістю багато стандартні ГПСЧ (зокрема, в 2-3 рази швидше лінійних конгруентних генераторів). Алгоритм вихору Мерсенна реалізований в програмній бібліотеці Boost, Glib і стандартних бібліотеках для Python, Ruby, R, PHP, MATLAB, Autoit.

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

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

К-розподіл

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

визначення

Кажуть, що псевдослучайная послідовність x i періоду P, що складається з w-бітних цілих, має k-розподіл з v-бітної точністю, якщо вона задовольняє наступній умові:
Нехай truncv (x) - число, утворене першими v битами послідовності xi, розглянемо P векторів виду (trunc v (xi), trunc v (xi + 1),..., Trunc v (xi + k - 1)) (0 ≤ i <P) {\ displaystyle ({\ 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-бітної точністю. Розділимо кожне ціле x i на 2w для нормалізації в псевдовипадкове дійсне число x i з інтервалу. Помістимо P точок в k- мірний куб з координатами (x i, x i + 1 ..., x i + k-1) (i = 0, 1, ..., P-1) для всього періоду. Кожна з осей даного k-мірного куба розділена на 2v інтервалів. Таким чином, ми розділили куб на 2kv малих куба. Послідовність є до-розподіленої з v-бітної точністю, якщо кожен малий куб містить рівну кількість точок, крім куба на початку координат, який містить на одну менше точок. Отже, чим вище k (v) для кожного v, тим більше багатовимірним буде розподіл з v-бітної точністю. Під тестом на k-розподіл, ми будемо розуміти отримання значень k (v).

опис

x будемо позначати вектори-слова, які представляють собою w-мірні вектори над полем F 2 {\ displaystyle F_ {2}} = {0,1}, відповідні машинному слову розміру w. Вихор Мерсенна генерує послідовність вектор-слів, які є псевдовипадковими цілими з діапазону від 0 до 2w - 1. Шляхом ділення на 2w - 1 ми отримаємо псевдовипадкове речовий з діапазону. Алгоритм заснований на наступному рекуррентном вираженні:

xk + n: = xk + m ⊕ (xku | xk + 1 l) A (1) k = 0, 1, ... {\ displaystyle 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 {\ displaystyle F_ {2}}.
• | {\ Displaystyle \ mid} - Побітове АБО (OR)
• ⊕ {\ displaystyle \ oplus} - Додавання за модулем два (XOR)

У правій частині x ku позначає «старші wr біт» x k і x k + 1l «младшіе r біт» x k + 1. Вектор (x ku | x k + 1l) є конкатенацией старших wr біт x k і молодших r біт x k + 1. Візміть (x 0, x 1, ..., x n-1) в якості початкового заповнення. Тоді генератор вирахує x n по рекурентному висловом при k = 0. Вважаючи k = 1,2, ..., генератор вирахує xn + 1, x n + 2, ... Форма матриці A обрана з розрахунку швидкості виконання множення на A:

A = (0 1 0 0 1 0 ⋯ ⋯ ⋱ ⋱ 1 aw - 1 aw - 2 ⋯ ⋯ ⋯ a 0) {\ displaystyle 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}}}

І обчислення x A зводиться до побітовим операціями:

x A = {x »1 x 0 = 0 (x» 1) ⊕ ax 0 = 1 {\ displaystyle {\ boldsymbol {x}} A = {\ begin {cases} {\ boldsymbol {x}} \ gg 1 & x_ { 0} = 0 \\ ({\ boldsymbol {x}} \ gg 1) \ oplus {\ boldsymbol {a}} & x_ {0} = 1 \ end {cases}}}

де

x: = (xku | xk + 1 l) k = 0, 1, ... {\ displaystyle {\ boldsymbol {x}}: = ({x_ {k}} ^ {u} \ mid {x_ {k + 1} } ^ {l}) \ qquad \ qquad k = 0,1, \ ldots} a: = (aw - 1, aw - 2, ..., a 0) {\ displaystyle {\ boldsymbol {a}}: = ({ a_ {w-1}}, {a_ {w-2}}, \ ldots, {a_ {0}})} x: = (xw - 1, xw - 2, ..., x 0) {\ displaystyle {\ boldsymbol {x}}: = ({x_ {w-1}}, {x_ {w-2}}, \ ldots, {x_ {0}})}

неповні масиви

неповні масиви

Послідовність МТ (x k + n, x k + n-1, ..., x k + 1u) утворює (n × w - r) -Маса. Так як r бітів відкидаються, масив називається неповним масивом. Кожен елемент отримано з рекурентного співвідношення (1). Зміна стану MT також відбувається за лінійним співвідношенням і визначається за допомогою лінійного перетворення B.

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

B = (0 I w ⋯ 0 0 ⋮ I w ⋮ ⋱ ⋮ ⋮ ⋮ 0 0 ⋯ I w 0 0 0 ⋯ 0 I w - r S 0 ⋯ 0 0) ← m -th row {\ displaystyle 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_ {wr} \\ S & 0 & \ cdots & 0 & 0 \ end {pmatrix}} {\ begin {matrix} \\\\\ leftarrow m {\ hbox {-th row}} \\\\\\\\ \ end {matrix}}}

S = (0 I r I wr 0) A {\ displaystyle S = {\ begin {pmatrix} 0 & I_ {r} \\ I_ {wr} & 0 \ end {pmatrix}} A}

Де I r {\ displaystyle I_ {r}} - одинична матриця розміру r × r.

Для l = 0, 1, ... {\ displaystyle l = 0,1, \ ldots} виконується (xl + n, xl + n - 1, ..., xl + 1): = (xl + n - 1, xl + n - 2, ..., xl) B {\ displaystyle (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 має вигляд:

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

Послідовність досягає максимального періоду 2 (nw-r) -1, тоді і тільки тоді коли φB (t) -прімітівний.

загартування

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

y:

= x ⊕ (x >> u) y: =: y ⊕ ((y b) y: =: y ⊕ ((y c) z: = y ⊕ (y >> l)

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

алгоритм

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

Блок-схема.

Регістр зсуву складається з 624 елементів, і, в цілому, з 19937 клітин. Кожен елемент має довжину 32 біта за винятком першого елемента, який має тільки 1 біт за рахунок відкидання біта.

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

Наступним кроком виконується ініціалізація (x 0, x 1, ..., x 623) будь-якими беззнаковими 32-розрядними цілими числами. Наступні кроки включають в себе об'єднання і перехідні стани.

Зміна стану МТ.

Простір станів має 19937 біт (624 · 32 - 31). Наступне стан генерується зрушенням одного слова вертикально вгору і вставкою нового слова в кінець. Нове слово обчислюється гаммированием середній частині з виключений. Вихідна послідовність починається з x 624, x 625, ...

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

Попередньо инициализируется значення констант u, h, au ← 10 ... 0 бітова маска старших wr біт, h ← 01 ... 1 бітова маска молодших r біт, a ← aw-1aw-2 ... a0 останній рядок матриці A.
Крок 1. x, x, ..., x ← початкове заповнення
Крок 2. Обчислення (x iu | x i + 1l) y ← (x AND u1) OR (x AND h1)
Крок 3. Обчислюється значення наступного елемента послідовності по рекурентного висловом (1) x ← x XOR (y >> 1) XOR a якщо молодший біт y = 1
Або x ← x XOR (y >> 1) XOR 0 якщо молодший біт y = 0 Крок 4. Обчислення x T y ← x y ← y XOR (y >> u) y ← y XOR ((y b) y ← y XOR ((y c) z ← y XOR (y >> l) висновок z Крок 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. Параметри гарту (англ. 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 році, 128-розрядна - в 2006 році теж Такудзі Нісимура. Обидві версії мають той же період, що і оригінальний MT.

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

xk + n: = xk + m 2 ⊕ xk + m 1 ⊕ xk + m 0 ⊕ (xku | xk + 1 l) A (2) {\ displaystyle 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

Реалізації на різних мовах програмування

• ABAP
• ActionScript 1
• ActionScript 3.0
• Ada
• C ++
• C and C ++
• C ++
• C ++
• Clojure
• Clean
• C ++ Sony Cell Broadband Engine
• C #
• Erlang
• Euphoria
• Excel addin
• Microsoft Excel
• Forth
• Fortran 95:
• F #
• The GNU Scientific Library (GSL)
• Haskell
• Haskell
• Java
• JavaScript
• JavaScript
• Lisp
• Lua
• Mitrion-C
• Pascal / FreePascal / Delphi
• Perl
• PHP 5.3.0
• REALbasic
• Standard ML
• SIMUL8
• Scala
• VBA
• Visual Basic
• MetaTrader5 MQL5

Примітки

1. ↑ Twisted GFSR generators.
2. ↑ boost / random / mersenne_twister.hpp. Boost C ++ Libraries. Перевірено 29 травня 2012 року Процитовано 19 листопада 2012.
3. ↑ Changes to GLib. GLib Reference Manual. Перевірено 29 травня 2012 року Процитовано 19 листопада 2012.
4. ↑ 9.6 random - Generate pseudo-random numbers. Python v2.6.8 documentation. Перевірено 29 травня 2012 року Процитовано 19 листопада 2012.
5. ↑ 8.6 random - Generate pseudo-random numbers. Python v3.2 documentation. Перевірено 29 травня 2012 року Процитовано 19 листопада 2012.
6. ↑ "Random" class documentation. Ruby 1.9.3 documentation. Перевірено 29 травня 2012.
7. ↑ Random Number Generators. CRAN Task View: Probability Distributions. Перевірено 29 травня 2012 року Процитовано 19 листопада 2012.
8. ↑ mt_srand. php documentation. Перевірено 29 травня 2012 року Процитовано 19 листопада 2012.
9. ↑ Control random number generation (RNG). Matlab Documentation. Перевірено 23 листопада 2015. Процитовано 12 вересня 2010 року.
10. ↑ Function Random
11. ↑ CryptMT Stream Cipher.
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

література

• 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.
• Matsumoto, M .; Kurita, Y. (1992). «Twisted GFSR generators». ACM Trans. on Modeling and Computer Simulations 2 (3): 179-194. DOI: 10.1145 / 146382.146383.
• Matsumoto, Makoto; Nishimura, Takuji; Hagita, Mariko; Saito, Mutsuo (2005). «Cryptographic Mersenne Twister and Fubuki Stream / Block Cipher».
• 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.
• Matsumoto M., Saito M., Nishimura T., Hagita M .. «CryptMT Stream Cipher Ver. 3.The eSTREAM Project ».

посилання

• Makoto Matsumoto, Academic publications on MT (англ.)
• Mersenne Twister home page, with C code (англ.)
• Cuba - a library for multidimensional numerical integration
• The Mersenne Twister (англ.)

Вихор Мерсенна Інформацію Про

Вихор Мерсенна Коментарі

Ви переглядаєте суб'єкт

Вихор Мерсенна що, Вихор Мерсенна хто, Вихор Мерсенна опис

There are excerpts from wikipedia on this article and video