Теория
Xorshift Джорджа Марсальи (2003) построен на простом наблюдении: слово, сдвинутое на несколько бит и сложенное по XOR само с собой, перемешивает биты так же эффективно, как умножение, но в разы быстрее. Один такт — три операции вида \(x \mathbin{\wedge}= x \ll a\), \(x \mathbin{\wedge}= x \gg b\), \(x \mathbin{\wedge}= x \ll c\).
У 32-битной версии период \(2^{32}-1\) при ненулевом зерне, у xorshift128 — \(2^{128}-1\) на четырёх 32-битных словах. Вариант xorshift128+ долго был Math.random() в Chrome и Firefox, пока его не заменили на более современные. «Звёздочные» версии дополнительно умножают выход на константу — скремблер прячет линейность младших бит.
Важно: xorshift — не криптографический генератор: состояние линейно по битам и восстанавливается по нескольким выходам. Для криптографии нужен CSPRNG.
Пример с решением
- Условие. xorshift32 (сдвиги 13/17/5) с зерном 2463534242: первый выход.
- Формула. \(x \mathbin{\wedge}= x \ll 13; \quad x \mathbin{\wedge}= x \gg 17; \quad x \mathbin{\wedge}= x \ll 5\) (всё по модулю \(2^{32}\)).
- Подстановка. \(x = 2463534242 = \mathrm{0x92D68CA2}\).
- Вычисление. После трёх XOR: \(x = \mathrm{0x2B1F4D63}\).
- Ответ. \(723471715\) — то же число выдаёт калькулятор с зерном 2463534242.
Главное
- Идея: XOR со сдвинутыми копиями заменяет умножение.
- Период \(2^{32}-1\) (xorshift32) при ненулевом зерне.
- 128+ — исторический Math.random в V8.