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

Матеріал з Вікіпедії — вільної енциклопедії.
(Перенаправлено з Вихор Мерсена)
Перейти до навігації Перейти до пошуку

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

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

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

Існують принаймні два загальних варіанти алгоритму, що відрізняються тільки величиною використовуваного простого числа Мерсенна, найпоширенішим з яких є алгоритм MT19937, період якого становить 219937 — 1 (приблизно 4,3·106001).

Властивості[ред. | ред. код]

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

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

Існують ефективні реалізації вихору Мерсенна, що перевершують за швидкістю багато стандартних ГПВЧ (зокрема, в 2-3 рази швидше від лінійних конгруентних генераторів). Алгоритм вихору Мерсенна реалізовано в програмній бібліотеці Boost[2], Glib[3] і стандартних бібліотеках для C++, Python[4][5][6], Ruby[7], R[8], PHP[9], MATLAB[10], Autoit[11].

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

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

K-розподіл[ред. | ред. код]

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

Визначення[ред. | ред. код]

Кажуть, що псевдовипадкова послідовність xi з періодом P, що складається з w-бітових цілих, має k-розподіл з v-бітовою точністю, якщо вона задовольняє такій умові: Нехай truncv(x) — число, утворене першими v бітами послідовності xi, розглянемо P з k v-бітових векторів вигляду[13] . Тоді кожна з 2kv можливих комбінацій бітів зустрічається рівне число разів, за винятком комбінації, що складається повністю з нулів, яка зустрічається на один раз менше.

Геометрична інтерпретація[ред. | ред. код]

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

Опис[ред. | ред. код]

x позначатимемо w-вимірні вектори над полем = {0,1}, відповідні машинним словам розміру w. Вихор Мерсенна генерує послідовність векторів, які є псевдовипадковими цілими з діапазону від 0 до 2w — 1. Діленням на 2w — 1 можна також отримати псевдовипадкове дійсне число з діапазону [0,1].

Алгоритм ґрунтується на такій рекурентній формулі:

де:

  • n — ціле, яке позначає порядок рекурентності,
  • m — ціле, 1 ≤ m < n,
  • A — матриця розміру w×w, з елементами з ,
  •  — побітове АБО (OR),
  •  — додавання за модулем два (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:

І обчислення xA зводиться до побітових операцій:

де

Неповні масиви[ред. | ред. код]

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

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

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

де  — одинична матриця розміру r × r.

Для виконується .Характеристичний многочлен φB(t) перетворення B має вигляд:

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

Загартування[ред. | ред. код]

Необроблені послідовності, що генеруються рекурсією (1), мають поганий рівномірний розподіл на великих розмірностях. Щоб це виправити, використовується метод загартування (англ. tempering), на виході якого отримують кінцеву псевдовипадкову послідовність. Метод полягає в тому, що кожне згенероване слово множиться праворуч на спеціальну оборотну матрицю 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). Наступний стан генерується зсувом одного слова вертикально вгору і вставленням нового слова в кінець. Нове слово обчислюється гамуванням середньої частини з виключеною[14]. Вихідна послідовність починається з x624, x625,…

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

 Крок 0. Попередньо ініціалізується значення сталих u, h, a
 u ← 10…0   бітова маска старших w-r бітів,
 h ← 01…1   бітова маска молодших r бітів,
 a ← aw-1aw-2…a0  останній рядок матриці A.
Крок 1. x[0], x[1],…,x[n-1] ←  початкове заповнення
Крок 2. Обчислення (xiu | xi+1l) y ← (x[i] AND u1) OR (x[(i + 1) mod n] AND h1)
Крок 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 y ← x[i] y ← y XOR (y>>u) y ← y XOR ((y<<s) AND b) y ← y XOR ((y<<t) AND 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[1] [Архівовано 13 березня 2019 у Wayback Machine.] . Параметри загартування (англ. 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 року Такудзі Нісімура,[15] 128-розрядну — 2006 року[16][17] теж він. Обидві версії мають той самий період, що й оригінальний MT.

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

Порівняно з 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, 1992.
  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 — Generate pseudo-random numbers — Python 3.8.3 documentation. Python 3.8.3 documentation. Архів оригіналу за 28 липня 2021. Процитовано 23 червня 2020. 
  7. "Random" class documentation. Ruby 1.9.3 documentation. Архів оригіналу за 26 червня 2021. Процитовано 29 травня 2012. 
  8. Random Number Generators. CRAN Task View: Probability Distributions. Архів оригіналу за 19 листопада 2012. Процитовано 29 травня 2012. 
  9. mt_srand. php documentation. Архів оригіналу за 19 листопада 2012. Процитовано 29 травня 2012. 
  10. Control random number generation (RNG). Matlab Documentation. Архів оригіналу за 12 вересня 2010. Процитовано 23 листопада 2015. 
  11. Function Random. Архів оригіналу за 6 квітня 2021. Процитовано 28 липня 2021. 
  12. CryptMT Stream Cipher.
  13. Matsumoto, Nishimura, 2017.
  14. Cryptographic Mersenne Twister and Fubuki Stream/Block Cipher, 2005.
  15. Nishimura, 2000.
  16. SIMD-oriented Fast Mersenne Twister (SFMT). Архів оригіналу за 9 листопада 2020. Процитовано 28 липня 2021. 
  17. SFMT: Comparison of speed. Архів оригіналу за 8 січня 2020. Процитовано 28 липня 2021. 

Література[ред. | ред. код]

  • M. Matsumoto, T. Nishimura. Mersenne twister: A 623-dimensionally equidistributed uniform pseudorandom number generator // ACM Trans. on Modeling and Computer Simulations : journal. — 2017. — Vol. 8, no. 1 (23 March). — P. 3—30. — DOI:10.1145/272991.272995.
  • Matsumoto, M.; Kurita, Y. Twisted GFSR generators // ACM Trans. on Modeling and Computer Simulations. — 1992. — Т. 2, № 3 (23 March). — С. 179—194. — DOI:10.1145/146382.146383.
  • Matsumoto, Makoto; Nishimura, Takuji; Hagita, Mariko; Saito, Mutsuo. Cryptographic Mersenne Twister and Fubuki Stream/Block Cipher. — 2005. — 23 March. Архівовано з джерела 27 липня 2021. Процитовано 28 липня 2021.
  • T. Nishimura. Tables of 64-bit Mersenne twisters // ACM Trans. on Modeling and Computer Simulations. — 2000. — Т. 10, № 4 (23 March). — С. 248—357. — DOI:10.1145/369534.369540.
  • Matsumoto M., Saito M., Nishimura T., Hagita M. CryptMT Stream Cipher Ver. 3.The eSTREAM Project. Архівовано з джерела 20 липня 2020. Процитовано 28 липня 2021.

Посилання[ред. | ред. код]