Теория
Вихрь Мерсенна (MT19937, Мацумото–Нисимура, 1997) — классический ГПСЧ общего назначения: на нём десятилетиями работали Python random, Ruby, Excel и старый PHP mt_rand. Название — от периода \(2^{19937}-1\) (простое число Мерсенна), а «вихрь» — из-за перекрутки состояния.
Состояние — 624 слова по 32 бита. Инициализация init_genrand заполняет его рекуррентно: \(mt_i = (1812433253 \cdot (mt_{i-1} \oplus (mt_{i-1} \gg 30)) + i) \bmod 2^{32}\). Раз в 624 выхода состояние «перекручивается» (twist), а каждое выходное слово проходит темперацию — серию сдвигов и XOR, выравнивающую биты.
Важно: MT не криптографический: по 624 подряд идущим выходам состояние восстанавливается полностью, и все следующие числа предсказуемы.
Пример с решением
- Условие. init_genrand(5489): первый выход.
- Формула. Инициализация, затем twist, затем темперация: \(y \mathbin{\wedge}= y \gg 11\), \(y \mathbin{\wedge}= (y \ll 7) \wedge \mathrm{0x9D2C5680}\), \(y \mathbin{\wedge}= (y \ll 15) \wedge \mathrm{0xEFC60000}\), \(y \mathbin{\wedge}= y \gg 18\).
- Подстановка. Зерно 5489, первое слово состояния после twist.
- Вычисление. После темперации \(y = 3499211612\).
- Ответ. 3499211612. Именно его делят на \(2^{32}\), получая знаменитое 0{,}8147 из MATLAB rand, — и тот же результат даёт калькулятор.
Главное
- Период \(2^{19937}-1\), состояние 624×32 бита.
- Темперация — финальное перемешивание бит выхода.
- Не криптографический: вскрывается по 624 выходам.