Рандомайзер — генератор случайных чисел и объектов¶
Рандомайзер — это устройство, программа или алгоритм, предназначенные для генерации случайных или псевдослучайных величин: чисел, последовательностей, состояний. Термин образован от англ. random — «случайный». В широком смысле рандомайзером называют любой механизм, чей выход не может быть заранее предсказан без знания внутреннего состояния или источника энтропии.
¶Принцип работы
Рандомайзеры делятся на две большие категории: аппаратные и программные.
Аппаратные рандомайзеры (так называемые генераторы истинно случайных чисел, TRNG) используют физические явления: шум транзистора, радиоактивный распад, тепловые колебания, квантовые процессы. Выход таких устройств принципиально непредсказуем, но скорость генерации обычно ограничена.
Программные рандомайзеры (генераторы псевдослучайных чисел, PRNG) вычисляют последовательность по детерминированному алгоритму. Классический пример — линейный конгруэнтный метод, предложенный Д. Лемером в 1949 году: последующее значение вычисляется как остаток от умножения предыдущего на множитель, сложения прибавляемого и взятия по модулю. Более совершенные алгоритмы — Mersenne Twister (1998, М. Мацумото и Т. Нисимура), xorshift, PCG. Современные ОС (Linux, Windows, FreeBSD) используют гибридные схемы: комбинируют быстрый PRNG с аппаратной энтропией из /dev/urandom или CryptGenRandom.
¶Качество случайности
Для оценки рандомайзера применяются статистические тесты: частотный тест, тест серий, тест автокорреляции, спектральный тест, а также комплексные батареи — например, NIST SP 800-22 и Dieharder. Качественный PRNG должен проходить их без отклонений.
Для криптографии предъявляются более строгие требования: выход должен быть неотличим от случайного даже при известном состоянии предыдущих значений. Такие генераторы называются криптографически стойкими (CSPRNG) — например, ChaCha20, AES-CTR-DRBG, Fortuna.
¶Применение
Рандомайзеры используются повсеместно:
- Криптография — генерация ключей, nonce, солей, одноразовых паролей.
- Игры и азартные игры — генерация карт, выпадения кубиков, лута. В онлайн-казино и лотереях применяются аппаратные RNG с сертификацией.
- Моделирование и наука — метод Монте-Карло, статистическая физика, биоинформатика, имитация квантовых систем.
- Информатика — рандомизация алгоритмов (быстрая сортировка, хеш-таблицы), тестирование, рассеивание данных.
- Искусство и музыка — генеративное искусство, алгоритмическая композиция (системы Макса Матта, SuperCollider).
¶Рандомайзер в русскоязычном интернете
В разговорном русском языке «рандомайзер» часто обозначает веб-сервис или бот, выбирающий случайный объект из заданного списка: случайное слово, число, изображение, персонажа, песню. Подобные сервисы активно используются в социальных сетях, стриминге и играх (например, «случайный персонаж» для ролевых игр, рандомайзеры для выбора победителя розыгрыша).
¶История
Понятие случайности в вычислениях восходит к работам Джона фон Неймана, предложившего в 1940-х годах простой квадратичный метод генерации псевдослучайных чисел. В 1958 году Д. Халл и А. Дюбелл разработали первый стандартный тест на случайность для IBM 704. В 1996 году Мацумото и Нисимура представили Mersenne Twister, ставший де-факто стандартом для некриптографических задач.
¶Ограничения
Главный недостаток PRNG — детерминированность: зная алгоритм и начальное состояние (seed), всю последовательность можно воспроизвести. Это и достоинство (воспроизводимость экспериментов), и уязвимость (в криптографии). Для критичных задач используют комбинированные генераторы, периодически перемешивающие состояние аппаратной энтропией.
Источники:
- Knuth D. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms
- L'Ecuyer P. Random Number Generation // Handbook of Computational Statistics
- Matsumoto M., Nishimura T. Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator
- NIST SP 800-22 Rev. 1a. A Statistical Test Suite for Random and Pseudorandom Number Generators
- Википедия: Генератор псевдослучайных чисел, Генератор истинных случайных чисел