Псевдослучайные числа: состояние, период и воспроизводимость

Если различаешь воспроизводимый опыт и непредсказуемый токен, листай до «Теперь сам».

Как думаешь, откуда взялось случайное число

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

На что это похоже

Представь длинную заранее определённую дорожку с указателем текущей позиции. Начальное состояние выбирает, откуда начать чтение, а правило перехода передвигает указатель. Цифры могут выглядеть беспорядочными, но следующий шаг уже определён. Генератор не получает новую независимую случайность после каждого вызова только потому, что функция называется random.

Механизм: конечное состояние обязательно повторится

Линейный конгруэнтный генератор хранит x и обновляет его по правилу x = (a·x+c) mod m. Возможных состояний m. Когда какое-то повторится, все будущие значения повторят прежний хвост. Период не больше m, а при неудачных параметрах может быть намного меньше. Длинный период необходим для большого опыта, но сам по себе не обеспечивает хорошее распределение многомерных точек.

При чётном m и нечётных a,c младший бит нового состояния равен младшему биту x+1. Он меняется каждый шаг. Поэтому последовательные результаты по модулю два предсказуемы полностью, даже если всё слово выглядит приемлемо. Программа ниже демонстрирует это на маленьком модуле и проверяет весь цикл.

В алгоритмическом доказательстве часто предполагаются независимые равномерные числа. Реальный генератор лишь приближает нужные свойства. Проверка частот - диагностический опыт, она не доказывает независимость всех событий и не даёт криптографическую защиту.

Правило

Выбирай источник по требованию: воспроизводимость опыта, статистическое качество или непредсказуемость для противника. Не подменяй эти требования друг другом. Для ограниченного диапазона применяй готовый метод равномерного выбора, а не произвольное взятие остатка.

Разбор: период есть, младший бит плох

from collections import Counter
from random import Random


def lcg(seed, a, c, m):
    x = seed
    while True:
        x = (a * x + c) % m
        yield x


def orbit(seed, a, c, m):
    seen = {}
    x = seed
    while x not in seen:
        seen[x] = len(seen)
        x = (a * x + c) % m
    return len(seen) - seen[x]


g = lcg(0, 5, 1, 16)
values = [next(g) for _ in range(16)]
print("Цикл:", values)
print("Младшие биты:", [x & 1 for x in values])
print("Период:", orbit(0, 5, 1, 16))
print("Плохие параметры:", orbit(0, 0, 1, 16))
counts = Counter(x % 6 for x in range(16))
print("Остатки mod 6:", sorted(counts.items()))
accepted = [x % 6 for x in range(16) if x < 12]
print("После отбрасывания:", sorted(Counter(accepted).items()))
a, b = Random(731), Random(731)
one = [a.randrange(100) for _ in range(8)]
two = [b.randrange(100) for _ in range(8)]
assert one == two
print("Зерно воспроизводит опыт:", one == two)

Цикл: [1, 6, 15, 12, 13, 2, 11, 8, 9, 14, 7, 4, 5, 10, 3, 0]
Младшие биты: [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]
Период: 16
Плохие параметры: 1
Остатки mod 6: [(0, 3), (1, 3), (2, 3), (3, 3), (4, 2), (5, 2)]
После отбрасывания: [(0, 2), (1, 2), (2, 2), (3, 2), (4, 2), (5, 2)]
Зерно воспроизводит опыт: True

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

Разбор: смещение при взятии остатка

Если равномерное исходное число принимает значения от нуля до пятнадцати, то остаток по шести принимает 0,1,2,3 по три раза, а 4,5 лишь по два. Здесь причина не в генераторе: размер исходного диапазона не делится на размер целевого. Отбрасывая значения 12–15, оставляем по два представителя каждого остатка. Это метод отбрасывания, на котором строятся равномерные преобразования диапазона.

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

Что ломается без этого

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

Зачем это в работе

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

Теперь сам

Генератор обновляет x = (5x+1) mod 16. Что можно сказать о младшем бите после каждого шага? Почему 16 возможных состояний ещё не доказывают период 16 у произвольных параметров?