Вихрь Мерсенна (англ. Mersenne twister) — генератор псевдослучайных чисел (ГПСЧ), разработанный в 1997 году японскими учёными Макото Мацумото (яп. 松本 眞) и Такудзи Нисимура (яп. 西村 拓士). Вихрь Мерсенна основывается на свойствах простых чисел Мерсенна (отсюда название) и обеспечивает быструю генерацию высококачественных псевдослучайных чисел. Вихрь Мерсенна лишен многих недостатков, присущих другим ГПСЧ, таких как малый период, предсказуемость, легко выявляемая статистическая зависимость. Тем не менее этот генератор не является криптостойким, что ограничивает его использование в криптографии.
Существуют по меньшей мере два общих варианта алгоритма, различающихся только размером используемого простого числа Мерсенна, наиболее распространённым из которых является MT19937.
Вихрь Мерсенна является витковым регистром сдвига с обобщённой отдачей (twisted generalised feedback shift register, TGFSR). «Вихрь» — это преобразование, которое обеспечивает равномерное распределение генерируемых псевдослучайных чисел в 623 измерениях (для линейных конгруэнтных генераторов оно ограничено 5-ю измерениями). Поэтому корреляция между последовательными значениями в выходной последовательности Вихря Мерсенна пренебрежимо мала.
Вихрь Мерсенна имеет огромный период, равный числу Мерсенна 219937 − 1, что более чем достаточно для многих практических приложений.
Существуют эффективные реализации Вихря Мерсенна, превосходящие по скорости многие стандартные ГПСЧ (в частности, в 2-3 раза быстрее линейных конгруэнтных генераторов). Вихрь Мерсенна реализован в библиотеке gLib и стандартных библиотеках для PHP, Python и Ruby.
Выдаваемые вихрем Мерсенна псевдослучайные числа успешно проходят тесты DIEHARD, что говорит об их хороших статистических свойствах.
Вихрь Мерсенна.