Детерминированные случайные числа по seed кратко

Лекция

детерминированные случайные числа — это псевдослучайные последовательности, которые создаются алгоритмами и выглядят как случайные, но полностью определяются начальными условиями (seed).

В математике и информатике часто требуется использовать случайные числа: для моделирования, статистики, криптографии, игр и даже в искусственном интеллекте. Однако настоящая случайность в вычислительных системах получить сложно. Поэтому применяются детерминированные генераторы псевдослучайных чисел (ГПСЧ) — алгоритмы, которые создают последовательности, имитирующие случайность.

Что такое детерминированные случайные числа

Определение: числа, полученные из алгоритма, который при одинаковом начальном состоянии всегда выдает одну и ту же последовательность.
Ключевая особенность: они выглядят случайными, но на самом деле полностью предсказуемы, если известен алгоритм и начальное значение.
Пример: линейный конгруэнтный метод (LCG), где каждое новое число вычисляется по формуле

Xn+1=(aXn+c)mod m

Здесь a,c,ma, c, m — параметры генератора, а X0 — начальное значение (seed).

Основные свойства

Детерминированность: повторяемость последовательности при одинаковом seed.
Псевдослучайность: статистические свойства (равномерное распределение, независимость) приближают их к настоящим случайным числам.
Вычислительная эффективность: генерация чисел происходит быстро и не требует физических источников случайности.
Контролируемость: возможность воспроизвести результаты экспериментов и симуляций.

Детерминированные случайные числа по seed

Существует два основных метода генерации случайных чисел. Первый метод измеряет некое физическое явление, которое, как ожидается, является случайным, а затем компенсирует возможные погрешности в процессе измерения. Примерами источников служат измерения атмосферного шума , теплового шума и других внешних электромагнитных и квантовых явлений. Например, космическое фоновое излучение или радиоактивный распад, измеряемые в течение коротких промежутков времени, представляют собой источники естественной энтропии (как меры непредсказуемости или неожиданности процесса генерации чисел).

виды псевдослучайных чисел:

Криптографически стойкий генератор псевдослучайных чисел ( CSPRNG ) или криптографический генератор псевдослучайных чисел ( CPRNG ) — это генератор псевдослучайных чисел (PRNG), обладающий свойствами, которые делают его пригодным для использования в криптографии . Его также называют криптографическим генератором случайных чисел ( CRNG ).

Псевдослучайные (детерминированные) — числа, внешне случайные, но полностью определяемые начальным seed и алгоритмом.

Применение

Моделирование и метод Монте-Карло: для имитации случайных процессов.
Компьютерные игры: генерация карт, событий, противников.
Криптография: хотя для защиты данных нужны криптографически стойкие генераторы, многие алгоритмы используют псевдослучайные последовательности как основу.
Тестирование и статистика: воспроизводимые случайные выборки позволяют проверять алгоритмы и системы.

Игры	Повторяемые уровни, одинаковые миры

Тестирование

Повторяемые тесты

Симуляции

Воспроизводимые эксперименты

Моделирование

Контроль статистики

ИИ	Обучение нейросетей с фиксированным seed

Генерация миров

Minecraft, No Man’s Sky

Ограничения

Предсказуемость: если известен алгоритм и seed, последовательность можно восстановить.
Не подходят для криптографии без усиления: обычные генераторы легко взломать, поэтому применяются специальные криптографические PRNG.
Конечный период: любая последовательность рано или поздно повторяется.

Где их нельзя использовать

Область	Почему
Криптография	Предсказуемы
Пароли	Легко взломать
Казино	Нельзя гарантировать честность

Для этого используют криптографически стойкие генераторы (CSPRNG).

Реализации КСГПСЧ

Рассмотрим три класса реализации КСГПСЧ:

На основе криптографических алгоритмов
На основе вычислительно сложных математических задач
Специальные реализации

В последних часто используются дополнительные источники энтропии, поэтому, строго говоря, они не являются «чистыми» генераторами, так как их выход не полностью определяется исходным состоянием. Это позволяет дополнительно защититься от атак, направленных на определение исходного состояния.

Реализации на основе криптографических алгоритмов

Безопасный блочный шифр можно преобразовать в КСГПСЧ, запустив его в режиме счетчика. Таким образом, выбрав случайный ключ, можно получать следующий случайный блок, применяя алгоритм к последовательным натуральным числам. Счет можно начинать с произвольного натурального числа. Очевидно, что периодом будет не больше, чем 2ⁿ для n-битного блочного шифра. Также очевидно, что безопасность такой схемы полностью зависит от секретности ключа.
Криптографически стойкая хеш-функция также может быть преобразована в КСГПСЧ. В таком случае исходное значение счетчика должно оставаться в секрете. Однако, некоторые авторы предостерегают от такого использования хеш-функций.

Большинство потоковых шифров работает на основе генерации псевдослучайного потока бит, которые некоторым образом комбинируется (почти всегда с помощью операции XOR) с битами открытого текста. Запуск такого шифра на последовательности натуральных чисел даст новую псевдослучайную последовательность, возможно, даже с более длинным периодом. Такой метод безопасен только если в самом потоковом шифре используется надежный КСГПСЧ (что не всегда так). Опять же, начальное состояние счетчика должно оставаться секретным.

Реализации на основе математических задач

Алгоритм Блюма — Блюма — Шуба имеет высокую криптостойкость, основанную на предполагаемой сложности факторизации целых чисел. Однако, этот алгоритм отличается очень медленной работой.
Алгоритм Блюма — Микали (англ. Blum-Micali algorithm) основан на задаче дискретного логарифма.

Специальные реализации

Существует целый ряд практически используемых ГПСЧ которые разрабатывались с учетом криптографической стойкости, например

Алгоритм Ярроу (англ. Yarrow algorithm) который пытается определить энтропию входных данных. Он используется в FreeBSD, OpenBSD и Mac OS X
Алгоритм Fortuna (англ. Fortuna algorithm), наследник алгоритма Ярроу.
Специальный файл ОС UNIX /dev/random, в частности, /dev/urandom, реализованный в Linux.
Функция CryptGenRandom предоставленная в CryptoAPI компании Microsoft
ISAAC базируется на варианте RC4.

Заключение

Детерминированные случайные числа — это компромисс между настоящей случайностью и практической необходимостью. Они позволяют эффективно моделировать случайные процессы, но требуют осторожности в областях, где важна непредсказуемость, например в криптографии.

Вау!! 😲 Ты еще не читал? Это зря!

Флипизм (решения принимаются путем подбрасывания монеты )
Лига энтропии
Список генераторов случайных чисел
Класс PP
Процедурная генерация
Рандомизированный алгоритм
Генератор случайных паролей
Случайная величина , содержит значение, зависящее от случайности