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

[Dig386]

Здравствуйте!

Я не так давно начал изучать устройство и качество генераторов псевдослучайных чисел и обнаружил очень странную ситуацию: какое-то излишне попустительское отношение к этим алгоритмам и полную уверенность в том, что в стандартную библиотеку языка программирования и даже в некоторые учебники можно помещать очень низкокачественные алгоритмы. Например, алгоритмы из стандартных библиотек языков Си, golang и Java попросту непригодны для серьёзной работы и при этом нет грозного предупреждения в документации в духе "осторожно, мусор для написания Тетриса! оставлено для совместимости!" Также в R есть какие-то дополнительные алгоритмы без аналогичного предупреждения. Да, я знаю, что в Python и MATLAB ситуация получше, там хотя бы MT19937 по умолчанию (и можно загрузить совсем приличные Philox или PCG64), статистические дефекты которого обычно не мешают.

Также очень странно то, что в учебниках по теории вероятности, математической статистике и численным методам довольно редко упоминается т.н. "тест на следующий бит" и возможность и даже желательность использования поточных шифров в качестве ГПСЧ. Хотя если подходить к качеству ГПСЧ для моделирования столь же строго, как к качеству функций sin или cos, то криптографическая стойкость и считалась бы синонимом статистического качества, а не основанные на шифрах генераторы - уделом удалых хакеров-расчётчиков, занимающихся агрессивной низкоуровневой оптимизацией кода. К тому же у AES и ChaCha12 на современных процессорах скорость может быть близкой к 1 cpb (2-3 ГиБ/с на одном ядре), и они могут быть даже быстрее линейных конгруэнтных генераторов. Также они значительно удобнее вихря Мерсенна для параллельного программирования. Но пока так сделано только в Rust и новых релизах golang.

Насколько обоснована моя точка зрения? Или она всё же излишне алармистская?

[mihaild]

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

Например, алгоритмы из стандартных библиотек языков Си, golang и Java попросту непригодны для серьёзной работы

Что такое "серьезная работа"? Далеко не все использования псевдослучайных чисел требуют криптостойкости.
И, как обычно, людям, которым нужны предупреждения о некриптостойкости стандартных генераторов, критостойкие генераторы не нужны - им нужно брать готовые существенно более высокоуровневые библиотеки.

[Dig386]

mihaild писал(а):

Что такое "серьезная работа"? Далеко не все использования псевдослучайных чисел требуют криптостойкости.

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

Цитата:

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

Я имел в виду даже не предупреждения об отсутствии криптостойкости, без нее еще можно обойтись. А о грубых статистических дефектах, выявляемых TestU01 и PractRand, причем таких, которые делают сомнительными любые результаты, полученные с помощью таких генераторов. Например, таковы 32-битные и 64-битные линейные конгруэнтные генераторы без скремблеров, аддитивные и субтрактивные генераторы Фибоначчи, Subtract With Borrow без децимации, генератор Wichmann-Hill-1982.

[mihaild]

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

Но я не вполне понимаю, зачем отказываться от шифров в ГПСЧ общего назначения при их столь высокой скорости на современном "железе"?

Например чтобы код одинаково работал на современном железе и на любом валенке.

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

А о грубых статистических дефектах, выявляемых TestU01 и PractRand, причем таких, которые делают сомнительными любые результаты, полученные с помощью таких генераторов.

Что такое "грубые статистические дефекты"?
Для того же вихря Мерсенна очень легко сделать статистический тест, который он провалит (нулевая гипотеза "625е сгенерированное число отличается от правильно вычисленного по предыдущим 624"). Но вряд ли большинство приложений, которые не делают чего-то подобного специально, заметят его отличие от более качественных генераторов.

[Dig386]

mihaild писал(а):

Например чтобы код одинаково работал на современном железе и на любом валенке.

Что такое "любой валенок"? Инструкции x86-64 AVX2 и AESNI уже достаточно древние. Да и даже без AVX2 ChaCha20 способна работать на скорости около 5 cpb на железе 20-летней давности, причем реализация minstd с 32-разрядными числам и делениями из учебника даёт около 3 cpb. И на древнем валенке и синусы с косинусами могут медленно считаться тоже, но это же не повод заменять их в стандартной библиотеке языка на какие-то грубые приближения. Общеупотребительные реализации алгоритмов должны работать в первую очередь корректно, и лишь во вторую очередь быстро. Т.е. ситуация уже давно стала такой, что вполне допустима позиция: если для кого-то шифры в ГПСЧ - это медленно, то эти люди сами способны реализовать собственные или подключить сторонние оптимизированные под их задачи алгоритмы. Если не способны - то им на самом деле не нужны эти алгоритмы, т.к. они не знают, чего хотят.

mihaild писал(а):

Что такое "грубые статистические дефекты"?

Для большинства линейных конгруэнтных генераторов и аддитивных генераторов Фибоначчи - это тесты Birthday Spacings и Gap Test, которые нацелены на выявления вещей вроде решетчатой структуры в последовательности. Вот пример того, к чему могут приводить провалы похожих тестов: https://pubmed.ncbi.nlm.nih.gov/10046804/ . После этого лично мне становится очевидным, что такие дефекты - это сразу генератор нужно "выкрасить и выбросить", не рассуждая даже. Вообще написать хороший LCG без скремблера, при этом ощутимо обгоняющий оптимизированные реализации AES или ChaCha - нетривиальная задача, требующая чтения научных статей и упражнений в теории чисел. Это связано с необходимостью длинной арифметики из-за низкого качества LCG с состоянием короче 256 бит для m = 2^k и короче 128 бит для простого m.

Цитата:

Для того же вихря Мерсенна очень легко сделать статистический тест

Да, он моментально проваливает тест "линейная сложность", и всего за несколько часов - "ранг двоичной матрицы размером 32768x32768". Для большинства симуляций это не критично. Но насколько уместно писать в документации к ГПСЧ общего назначения "осторожно, биты не выковыривать"? И даже если MT19937 в большинстве случаев подойдет и его вполне можно оставить там, где он уже есть, для меня всё ещё загадка, почему в учебниках по статистике и численным методам почти никогда нет "теста на следующий бит" и шифров.

[mihaild]

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

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

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

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

После этого лично мне становится очевидным, что такие дефекты - это сразу генератор нужно "выкрасить и выбросить", не рассуждая даже

А мне не становится. Потому что я не занимаюсь моделированием какой-то сложной физики. А для случайной задержки при перезапросах сойдёт.

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

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

почему в учебниках по статистике и численным методам почти никогда нет "теста на следующий бит" и шифров

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

[Dig386]

mihaild писал(а):

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

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

Цитата:

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

Если применить мой подход к glibc (везде шифры), то код там станет короче, т.к. вместо 4 вариантов устаревших ГПСЧ будет один нормальный. И она даже замедлится процентов на 30 всего даже при наивной реализации, т.к. там основной ресурс мьютексы сжирают. И задержка от ChaCha для задержки перед перезапросами будет вообще неощутимой.

Цитата:

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

Согласен. И поэтому, возможно, и стоит там привести ту же ChaCha как универсальный ГПСЧ вместо LCG. С напутствием в духе "отказ от шифров в ГПСЧ требует четкого понимания условий задачи и специальных знаний" (и кратким списком более-менее приличных некриптографических ГПСЧ). Нужен кому-то LCG - пусть Кнута и Марсалью читают.

[mihaild]

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

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

У меня нет в этом уверенности.

C standard 2024 писал(а):

5.2.5.3.3.20. The accuracy of the floating-point operations (+, -, *, /) and of most of the library functions in <math.h> and <complex.h> that return floating-point results is implementation-defined, as is the accuracy of the conversion between floating-point internal representations and string representations performed by the library functions in <stdio.h>, <stdlib.h>, and <wchar.h>. The implementation may state that the accuracy is unknown.

Т.е. как минимум язык ничего про точность не гарантирует. И я не очень удивлюсь, если какие-то реализации для экзотического железа используют float sin(x) { return x - x*x*x / 6; }.

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

И она даже замедлится процентов на 30 всего даже при наивной реализации

glibc официально поддерживает, например, m68k. Лично мне не хочется думать, как под это эффективно что-то реализовывать.

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

И поэтому, возможно, и стоит там привести ту же ChaCha как универсальный ГПСЧ вместо LCG

Давайте возьмем двух студентов, я буду объяснять одному LCG, Вы другому ChaCha, и посмотрим, чей студент быстрее напишет реализацию без ошибок

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

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

Я бы сказал, что наоборот.

[sergey zhukov]

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

Откуда взялось убеждение, что со случайностью можно иначе?

С другой стороны, откуда взялось убеждение, что так нельзя? Любая псевдослучайность чем-то, да грешит. Какая "точность", для чего и когда достаточна? Можно и 16 цифр после запятой легко исчерпать в реальных задачах. Так может, стоит 30 цифр после запятой "в общих вычислениях" использовать? Если при любом столкновении с каким-то ограничением все со всех сторон расширять "на всякий случай", то скоро все это станет неподьемным.

[Dig386]

mihaild писал(а):

Давайте возьмем двух студентов, я буду объяснять одному LCG, Вы другому ChaCha, и посмотрим, чей студент быстрее напишет реализацию без ошибок

Для ChaCha достаточно объяснить, что есть стандарт RFC, в котором она описана прямо вместе с тестовыми векторами, а также один неочевидный нюанс с размером счетчика. В результате средствами С99 она реализуется быстро и просто. Суть тоже простая: берут 16 32-битных слов, инициализируют, обратимо перемешивают особой функцией биты, и в конце добавляют поэлементно выход к входу. В случае же качественного LCG мне придется объяснять какой-то вариант длинной арифметики и конструирование матриц перехода для обеспечения многопоточности. Самые эффективные варианты длинной арифметики с подбором множителей специального вида для таких генераторов вообще на русский не переводились, и до состояния "учебное пособие" не разжевывались, там хватает умолчаний и коварных моментов. Возни точно будет больше, чем с ChaCha.

Цитата:

И я не очень удивлюсь, если какие-то реализации для экзотического железа используют

На экзотическом железе много чего может быть, там вообще может и математической библиотеки не быть, и аппаратной плавающей запятой не быть. Но это не повод на нормальном железе пихать в функцию rand() аналоги Вашей упрощенной реализации синуса. И то, даже для микроконтроллера есть примитивные, строк так на 15, некриптографические ГПСЧ, которые прекрасно проходят TestU01 и PractRand, и могут даже без умножения обойтись, и памяти потреблять мало. Получается, что всей это вакханалии в rand() стандартных библиотеках Си вообще нет оправдания, это просто раздолбайство и недостаток знаний. И, кстати, m68k - 32-разрядные, все нужные для ARX-шифров операции там есть.

И тем не менее: если бы на обычной рабочей станции x86-64 функция sin(x) имела бы точность 6 знаков после запятой для double - это сочли бы багом. Но в случае rand() подобное почему-то считают нормой.

Цитата:

Я бы сказал, что наоборот.

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

-- 19.11.2025, 02:55 --

sergey zhukov писал(а):

Любая псевдослучайность чем-то, да грешит.

Разумеется. Но в случае ГПСЧ единственно объективный критерий качества - это тест на следующий бит, который вульгаризованно формулируется так: человечеству не должен быть известен способ отличить вывод ГПСЧ от случайного меньше, чем за 2^128 операций.

Цитата:

Какая "точность", для чего и когда достаточна?

Для научных и инженерных расчётов. При использовании шифров шансы нарваться на артефакты ГПСЧ резко снижаются.

Цитата:

Так может, стоит 30 цифр после запятой "в общих вычислениях" использовать?

И тут есть интересный момент: в некоторых случаев замена LCG (RANLUX, minstd, Wichmann-Hill) на шифр ведет не к замедлению, а к ускорению работы генератора, иногда - в разы. И артефакты ГПСЧ куда коварнее ограниченности точности вычислений с плавающей запятой, т.к. у каждого некриптографического генератора могут быть свои "фирменные" дефекты. Проще использовать шифры по умолчанию, чем тратить время на исследование "приколов" конкретного алгоритма.

[mihaild]

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

Для ChaCha достаточно объяснить, что есть стандарт RFC, в котором она описана прямо вместе с тестовыми векторами, а также один неочевидный нюанс с размером счетчика

Зависит от курса. Руками код писать тоже надо. Естественно без длинной арифметики и многопоточности, с модулем, укладывающемся в 32 бита.
Длинная арифметика и многопоточность тоже нужны, но потом.

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

На экзотическом железе много чего может быть, там вообще может и математической библиотеки не быть, и аппаратной плавающей запятой не быть.

float любая реализация C обязана обеспечить так, чтобы соблюдались указанные в стандарте требования. А что значит "может не быть математической библиотеки" когда мы разговариваем о том, что, собственно, добавлять в библиотеку?

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

Получается, что всей это вакханалии в rand() стандартных библиотеках Си вообще нет оправдания, это просто раздолбайство и недостаток знаний.

Ну отправьте pull request в glibc. Узнаете довольно много интересного про то, как весело менять что-то настолько массово и разнообразно использующееся.
Мне, честно говоря, даже думать про это страшно. Была же замечательная история, когда они порядок копирования байт в memcpy поменяли, и сломалось много неожиданного.
-- 19.11.2025, 01:28 --

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

Но в случае rand() подобное почему-то считают нормой

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

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

И она даже замедлится процентов на 30 всего даже при наивной реализации, т.к. там основной ресурс мьютексы сжирают. И задержка от ChaCha для задержки перед перезапросами будет вообще неощутимой.

Кстати хотелось бы посмотрет на бенчмарки.

[Dig386]

mihaild писал(а):

Естественно без длинной арифметики и многопоточности, с модулем, укладывающемся в 32 бита.

Модуль, укладывающийся в 32 бита - это период, исчерпывающийся за минуты, а то и вообще за несколько секунд. Если показывать классику в духе $x_n = (69069 x_{n-1} + 12345) \mod 2^{32}$, то скорее как антипример в одном ряду с RANDU. Можно с демонстрационным примером для решения у доски, который покажет решетки в выходе генератора. Это очень легко на самом деле сделать. Простейший LCG, остающийся пригодным для использования, выглядит вот так:
https://cas.ee.ic.ac.uk/people/dt10/res ... wc64x.html

Цитата:

Ну отправьте pull request в glibc. Узнаете довольно много интересного про то, как весело менять что-то настолько массово и разнообразно использующееся.

Да, там менять будет сложно, т.к. они навесили на свой ГПСЧ несколько разных режимов работы с разным потреблением памяти. Хороших путей тут несколько:
1) Если ничего не менять вообще - то на man страницу нужно добавить четкое предупреждение о непригодности алгоритма для научных и инженерных расчётов. И вообще сказать, что он тут только для совместимости оставлен, а статистическое качество ужасно.
2) Добавить скремблер на выход их генератора ALFIB, это устранит большинство проблем и обойдется в несколько строк кода.
3) Просто сделать все эти режимы работы (размер ALFIB) бутафорией и заменить всё на ChaCha или LEA. Но на это могут не пойти. Хотя они уже когда-то меняли ГПСЧ.

Цитата:

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

Каких именно приложений? Есть очень простой эвристический тест: если Вы не можете использовать ГПСЧ вида $x_n = (x_{n-1} + \mathrm{DEADBEEF}_{16}) \mod 2^{32}$, то rand() из стандартной библиотеки языка Си Вам не подойдет. И стандарт языка Си такой примитивный счетчик даже разрешает.

Цитата:

Кстати хотелось бы посмотрет на бенчмарки.

В glibc я ChaCha не засовывал, но получается у меня так на Intel(R) Core(TM) i5-11400H:
1) xoroshiro128++ - 0.25 cpb
2) lcg69069 ~ 0.2-0.3 cpb
3) MWC64X ~ 0.4 cpb
4) ChaCha12 на AVX2 - 0.8 cpb
5) minstd на 32-битной арифметике - 2.6 cpb
6) ChaCha12 без AVX2 - 2.6 cpb
7) AES128 (AESNI) - 0.9 cpb
8) RANLUX++ - 2.3 cpb
9) ranlux классический (luxury level 3) - 55 cpb.
10 MT19937 - 0.5 cpb

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

[epros]

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

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

Какова Ваша конкретная задача? Потому что для задачи, например, генерации криптографических ключей любой ГПСЧ будет плох.

[Dig386]

epros писал(а):

Какова Ваша конкретная задача? Потому что для задачи, например, генерации криптографических ключей любой ГПСЧ будет плох.

Для генерации криптографических ключей используют вообще программно-аппаратные комплексы (вроде /dev/urandom), ядро которых - это ГПСЧ на основе шифра, но ключ часто обновляется за счёт аппаратных источников случайности.

Одна из моих конкретных задач - это, например, генерация псевдослучайных выборок концентраций в 15-мерном пространстве для тестирования термодинамических расчётов. Для однопоточного режима мне было достаточно MT19937 (но не rand(), оно же плохое и главное - непортабельное), но в многопоточном пришлось заменять на ChaCha20, т.к. в стандартной библиотеке C++ нет пригодных для многопоточного использования ГПСЧ, и обещают добавить только в С++26. Просто этот шифр оказался самым простым для реализации из таких генераторов. У меня нет времени и желания проводить сложные исследования на тему того, какие сиды того же MT19937 будут приводить к корреляциям между потоками, а какие - нет. Шифр оказался проще.

Ещё одна задача - это разработка статистических тестов для ГПСЧ, там вообще ничего, кроме шифров, для калибровки использовать нельзя.

[warlock66613]

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

Каких именно приложений?

Ну вот я последние два раза пользовался ГПСЧ для 1) случайно выбрать раскраску 100500 графика (когда предзабитые красивые цвета кончились), 2) генерация гуарда в поколенческой арене, но со случайными числами вместо номера поколения. На кой чёрт, извините, мне в этих задачах криптостойкость (во втором случае она откровенно даже вредна, ибо надо максимально быстро генерить, а качество совершенно неважно)? И почему вы считаете что ваши задачи важнее моих?