О критериях качества генераторов псевдослучайных чисел

[Dig386]

Skipper в сообщении #1710882 писал(а):

Вот недавно я задался целью сгенерировать истинно случайное число, длиной в 1024 бита.

Есть генераторы псевдослучайных чисел, способные гарантированно выдать любое число от 0 до $2^{1024} - 1$. Например, шифр Threefish-1024 в режиме гаммирования.

Skipper в сообщении #1710882 писал(а):

Но в реальных компьютерах, такого попросту, нет.

Есть, см. инструкции RDRAND или RDSEED на архитектуре x86-64, они дают доступ к аппаратному генератору случайных чисел.

Skipper в сообщении #1710882 писал(а):

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

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

[realeugene]

Dig386 в сообщении #1710892 писал(а):

Сам по себе человек - плохой источник случайности, его нужно рассматривать здесь как запрограммированного биоробота, но с небольшими погрешностями в моторике.

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

-- 28.11.2025, 14:09 --

И не надо забывать, что истинная случайность мешает отладке. Качественная псевдослучайная последовательность с возможностью записи сида в лог для возможности её повторения бывает сильно полезнее истинно случайной.

[Dig386]

realeugene в сообщении #1710889 писал(а):

Впрочем, и для Монте-Карло в большинстве случаев должно хватить даже короткого цикла повторения псевдослучайной последовательности.

Зачем в большинстве случаев вообще об этом задумываться, когда можно просто использовать поточные шифры вроде AES-CTR или ChaCha как ГПСЧ общего назначения? Или если же нужна очень быстрая генерация и допустимо пойти на снижение качества генератора - то можно использовать MT19937, xoroshiro**/++ с очень длинными периодами.

realeugene в сообщении #1710889 писал(а):

Поэтому стандартные генераторы выдают только старшие биты.

Обычно это относится к линейным конгруэнтным генераторам с делителем - степенью двойки. Но их использование без скремблеров бессмысленно, т.к. минимально приемлемое качество достигается где-то на 256 битах (из которых хорошие только старшие то ли 32, то ли 64 бита), а такое расширение состояния может делать его медленнее AES или ChaCha, т.е. заведомо не нужным.

Я считаю, что учебники бывают недостаточно категоричны в плане качества ГПСЧ. По идее современная аппаратура позволяет уже рекомендовать использовать поточные шифры в ГПСЧ просто по умолчанию, и именно их и надо рекомендовать как эталон. С возможным перечнем каких-то 5 более-менее приличных скоростных генераторов вроде Philox, xoroshiro**, PCG, SFC64, даже MT19937 с максимально жёстко-консервативным подходом к их использованию (например, говорить, что PCG или MT19937 нельзя использовать как многопоточные ГПСЧ, и что перед любым применением MT19937 надо думать о том, критичны ли его дефекты для задачи). Причём их можно и нужно позиционировать как "bithacks" для агрессивной оптимизации и/или GPU. При этом надо честно говорить, что большинство ГПСЧ из второго тома Кнута - это игрушки, и что сам Кнут это предвидел.

Т.е. вполне допустим и желателен сдвиг в мышлении: переход от "почему Вы использовали шифр для ГПСЧ" к "отказ от использования шифра в ГПСЧ требует специального обоснования".

Цитата:

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

Думаю, тут надо уже обращаться к описаниям алгоритмов Fortuna и Yarrow.

[realeugene]

Dig386 в сообщении #1710897 писал(а):

т.к. минимально приемлемое качество

Зависит от задачи.

-- 28.11.2025, 14:24 --

Dig386 в сообщении #1710897 писал(а):

Думаю, тут надо уже обращаться к описаниям алгоритмов Fortuna и Yarrow.

В криптографии придумано много хороших сильных алгоритмов. Которые избыточны если не нужна криптографическая стойкость.

-- 28.11.2025, 14:26 --

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

[Dig386]

realeugene в сообщении #1710898 писал(а):

Зависит от задачи.

Если задача заранее не известна, то минимально приемлемое качество - это поточный шифр, причём не всякий. Даже если мы работаем с методом Монте-Карло, а не с безопасностью.

realeugene в сообщении #1710898 писал(а):

И не забывайте, что стандартные библиотеки спроектированы для использования на максимально возможной линейке ядер, в том числе, встраиваемых без криптографических ускорителей и аппаратных генераторов случайности.

Даже если на каком-то специфическом оборудовании гипотетическая ChaCha из стандартной библиотеки замедлится, то насколько это будет фатально? Даже если она будет генерировать 100 МиБ в секунду, то этого почти всегда будет достаточно. Вот если косинус из стандартной бибилотеки будет на каком-то специфическом железе медленно работать, то мы ожидаем, что программисты напишут своё быстрое решение. Почему с ГПСЧ должно быть иначе?

Цитата:

Для большинства задач линейного конгруэнтного генератора хватает.

Каких именно задач и какого именно LCG?

[Евгений Машеров]

Dig386 в сообщении #1710897 писал(а):

Зачем в большинстве случаев вообще об этом задумываться, когда можно просто использовать поточные шифры вроде AES-CTR или ChaCha как ГПСЧ общего назначения?

"Если у тебя в руках молоток - всё на свете кажется гвоздями"

[realeugene]

Dig386 в сообщении #1710901 писал(а):

Каких именно задач и какого именно LCG?

Для тетриса и подобного. LCG из стандартных библиотек.

Кстати, заглянул в исходники современных CRTL. Выдают предупреждение если используется детерминированный random().

[Dig386]

realeugene в сообщении #1710903 писал(а):

Для тетриса и подобного. LCG из стандартных библиотек.

Ну от использования критографических алгоритмов в Тетрисе ничего не случится, пользователь даже ничего не заметит. А если так - то зачем держать дефектные алгоритмы в стандартной библиотеке?

realeugene в сообщении #1710903 писал(а):

Выдают предупреждение если используется детерминированный random().

Шифр, кстати, может быть столь же детерминированным, как и LCG, достаточно лишь в качестве seed задать ключ и счётчик. Но даже если его инициализировать из time(NULL), что ужасно для целей безопасности, он всё равно даст очень хорошие псевдослучайных выборки без статистических дефектов.

Евгений Машеров в сообщении #1710902 писал(а):

"Если у тебя в руках молоток - всё на свете кажется гвоздями"

Может быть. Но плата за использование шифров в роли ГПСЧ общего назначения - это возможное снижение производительности в некоторых специфических случаях. А вот попытка заниматься микрооптимизациями за счёт выбора плохих генераторов может привести к не вполне корректным результатам. Считаю, что коррректность важнее.

[realeugene]

Dig386 в сообщении #1710904 писал(а):

Но плата за использование шифров в роли ГПСЧ общего назначения - это возможное снижение производительности в некоторых специфических случаях.

Что осложнит некоторому количеству народа переход на новые версии CRTL.

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

-- 28.11.2025, 14:59 --

Dig386 в сообщении #1710904 писал(а):

Считаю, что коррректность важнее.

Ну а другие люди с другим опытом считают иначе. И действуют осторожнее, когда дело касается столь широко используемых библиотек.

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

[Dig386]

realeugene в сообщении #1710905 писал(а):

Когда осознаны специальные требования - можно вызвать специальный генератор.

Несомненно. Я просто не понимаю, почему AES-CTR или ChaCha20 должны считаться "специальными генераторами", а не стандартом по умолчанию. Кому нужны безумные скорости или микроконтроллеры - те смогут написать и свои алгоритмы. И, кстати, более быстрые и несравненно более качественные, чем типичный LCG из учебника или библиотеки.

Цитата:

кому-то нужна истинная случайность, а кому-то нужна наоборот истинная детерминированность

Я рассматриваю именно детерминированные ГПСЧ и их статистическое качество. Разумное, хотя и максималистское требование к качеству ГПСЧ общего назначения - тест на следующий бит, т.е. мы не должны знать способов восстановления его состояния по выходу быстрее, чем за 2^128 тактов на классическом компьютере. Разумное требование к скоростным генераторам - это прохождение батарей TestU01 и PractRand на 32 ТиБ.

realeugene в сообщении #1710905 писал(а):

Что осложнит некоторому количеству народа переход на новые версии CRTL.

Судя по всовыванию мьютексов в rand(), на производительность как раз всем плевать.

[realeugene]

Dig386 в сообщении #1710906 писал(а):

Судя по всовыванию мьютексов в rand(), на производительность как раз всем плевать.

Встраиваемые системы нередко однопоточные.

-- 28.11.2025, 15:08 --

Утомительно.

Заканчиваю, сформулировав своё окончательное мнение: проблема высосана из пальца, не нужно на неё тратить время.

-- 28.11.2025, 15:20 --

Добавлю.

Что реально напрягало однажды при использовании "хорошего" генератора в Шарпе - невозможность сохранить внутреннее состояние псевдослучайного генератора в лог для его непосредственного использования в качестве сида при последующей отладке данного случая. Так что специально часто сидировал свой генератор каждого алгоритма 32-битными псевдослучайными числами глобального генератора сидов.

[Dig386]

realeugene в сообщении #1710907 писал(а):

Встраиваемые системы нередко однопоточные.

Это вообще совершенно особая ниша, но мы теперь знаем алгоритмы вроде xoroshiro++, которым даже умножения не надо, и при этом они BigCrush и PractRand пройдут, хотя и не криптостойкие, и очень простые. И при этом оно будет компактнее, быстрее и элегантнее подборки треш-генераторов из glibc. И Марсалья ещё публиковал в Интернете модификации KISS, также не использующие умножение.

-- 28.11.2025, 15:25 --

realeugene в сообщении #1710907 писал(а):

"хорошего" генератора в Шарпе

А какой алгоритм там они использовали? Если речь не про крипто-API, то видел когда-то упоминание об использовании аддитивных генераторов Фибоначчи, которые также очень плохие.

[realeugene]

Dig386 в сообщении #1710909 писал(а):

А какой алгоритм там они использовали?

Не помню как называется, с большим предынициализированным массивом и подмешиванием нескольких прошлых элементов.

-- 28.11.2025, 15:30 --

И, кстати, замена алгоритма сидируемого генератора - это изменение интерфейса.

[Dig386]

realeugene в сообщении #1710910 писал(а):

И, кстати, замена алгоритма сидируемого генератора - это изменение интерфейса.

В C# алгоритм, похоже, меняли на более качественный: был ALFIB, стал xoroshiro**. И у него состояние стало меньше. Я прекрасно понимаю, что изменение генератора в стандартной библиотеке может сломать совместимость в каких-то случаях. Но в таком случае в glibc и ряд других библиотек нужно добавить четкое предупреждение о том, что их ГПСЧ - низкокачественное legacy, которое нельзя использовать для чего-то серьёзного.

[realeugene]

И ещё кстати, во многих аппаратных применениях, где важна оптимизация железа, а криптографическая стойкость не важна, успешно используют "отвратительный" LFSR. Требования определяются решаемой задачей.

-- 28.11.2025, 15:47 --

Dig386 в сообщении #1710911 писал(а):

нужно добавить четкое предупреждение о том, что их ГПСЧ - низкокачественное legacy, которое нельзя использовать для чего-то серьёзного.

Те, кто занимаются серьёзно, и так всё понимают.

-- 28.11.2025, 15:53 --

Dig386 в сообщении #1710911 писал(а):

И у него состояние стало меньше.

Да его просто не вытащишь стандартными методами из объекта. И потом не запихнёшь обратно. Не знаю, может быть и можно было сериализовать как-то в текстовый поток - не стал копать это в Шарпе.