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

[Dig386]

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

успешно используют "отвратительный" LFSR

В том-то и дело, что в glibc - не классический LFSR, а аддитивный генератор Фибоначчи, проваливающий тривиальные gap test и birthday spacings test. А грамотно спроектированный LFSR с достаточно плотной матрицей перехода и хорошей выходной функцией, например, xoroshiro++, может быть как раз довольно неплох, особенно для микроконтроллеров. Уж точно лучше LCG. И это прекрасно - иметь запас таких алгоритмов для особых случаев. Я просто ставлю под сомнение целесообразность их использования на обычных рабочих станциях в подавляющем большинстве случаев. Есть же знаменитый принцип "преждевременная оптимизация — корень всех зол".

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

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

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

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

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

[realeugene]

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

не классический LFSR

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

-- 28.11.2025, 16:09 --

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

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

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

-- 28.11.2025, 16:10 --

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

авторы учебников далеко не всегда понимают, что такое хороший ГПСЧ, и там можно и Wichmann-Hill увидеть, и LCG, и какие-то плохо спроектированные LFSR

Или не считают такие генераторы плохими для своих задач.

[Dig386]

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

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

Я думаю, что у разработчиков аппаратных протоколов есть и sympy, и TestU01 с PractRand для проектирования LFSR, и они знают, что делают, и чего они хотят от своего регистра сдвига. Но это опять же - узкоспециализированная ниша. И заметьте - LCG тут нет, т.к. умножение здесь дорогое. Тащить же микроконтроллерно-железячные оптимизации на рабочие станции обычно нецелесообразно.

Впрочем, я как-то видел пример реализации LFSR на Си, в которой умудрились быть медленнее AES в 100 раз.

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

Или не считают такие генераторы плохими для своих задач.

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

[realeugene]

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

и чего они хотят от своего регистра сдвига

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

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

Или же просто они не осознают характер проблемы и не знакомы с современными подходами

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

[Dig386]

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

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

Я ориентируюсь не просто на специалистов, а на специалистов мирового уровня.
1) Разработчики TestU01 (https://simul.iro.umontreal.ca/testu01/tu01.html) - они ещё около 20 лет назад говорили про "very bad lattice structure" и/или "should be discarded" про почти все линейные генераторы из учебников. И наименее проблемными ГПСЧ у них были комбинированные генераторы и криптографические генераторы.
2) Разработчик PractRand (https://pracrand.sourceforge.net/) - использует поточные шифры для калибровки своей батареи тестов и всячески рекомендует их как эталон.
3) Дональд Кнут - ещё 30 лет назад в своей трёхтомной монографии предупреждал об артефактах многих линейных генераторов. А для 32-битных LCG рекомендует такие малые выборки, на которых тесты ещё не начинают "видеть" артефакты генератора.
4) Дж. Марсалья открыл решетчатую структуру LCG, очень много внимания уделял проблеме поиска качественных ГПСЧ, и предложил в итоге семейство довольно качественных комбинированных генераторов KISS. А модификации его LCG с большим состояниям (RANLUX) до сих пор трудятся в CERN.
5) Современные издания Numerical Recipes - рекомендуют комбинированные и похожие на KISS ГПСЧ, а также шифр RC4 (ныне устаревший, в нем нашли дефекты)
6) Разработчики ThreeFry и Philox - взяли шифры как основу, и упростили их для ускорения на GPU.

И если в каких-то учебниках по численным методам и статистике ещё остались всякие "дребезделки" вроде 32-64 битных LCG, xorshift64, аддитивных генераторов Фибоначчи или Wichmann-Hill-1982 - то их просто давно не обновляли. Также проблема может быть в отсутствии перевода многих вещей на русский язык, хотя вряд ли: авторы учебников по подобным предметам обязаны знать английский язык.

[TheRuinedMap]

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

mihaild писал(а):

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

Любое использование для научных и инженерных расчётов, в т.ч. для метода Монте-Карло.

Нет.

Для любых научных расчетов, включая методы Монте-Карло, прекрасно подходят обыкновенные элементарные псевдослучайные генераторы, реализуемые в три строчки стандартных библиотеках языков программирования. Никаких претензий к ним со стороны "научных расчетов" нет. Расхожий миф, о каких-то "проблемах" с такими генераторами, произрастает из давнишней истории c тупейшим багом в реализации `rand()` в какой-то замшелой версии стандартной библиотеки для какой-то давно забытой платформы. Эта история методом "испорченного телефона" превратилась в городскую легенду о какой-то "некачественности" классических генераторов, имеющую хождение лишь среди тинейджеров в игровых компьютерных клубах а-ля "привет девяностые" в провинциальных городках.

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

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

[sergey zhukov]

Я думаю, что если ты при решении практической задачи столкнулся с проблемой, связанной с "некачественной" псевдослучайностью (и показал, что это именно так и есть), то, видимо, имеет смысл поднимать вопрос о том, что вот, смотрите, а проблемы-то не выдуманные.

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

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

[Dig386]

TheRuinedMap в сообщении #1712434 писал(а):

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

Какие именно из элементарных генераторов? Их много разных. Маленькие генераторы бывают как и очень приличные (PCG, xoroshiro++/**, SFC64), так и совершенно ужасные (LCG64, аддитивные генераторы Фибоначчи, xorshift32 или 64). 35 лет назад тот же CERN для своих научных расчётов "элементарными генераторами" не удовольствовался, они сделали свой LCG с 576 бит состояния. Ещё "элементарные генераторы" обычно не заточены под многопоточность. Грубые артефакты в статистических тестах от устаревших генераторах наблюдал лично и неоднократно, и искренне не понимаю, зачем вообще тратить умственные усилия на мысли на размышления о том, будут ли они мешать в конкретной задаче или нет? Когда проще сразу делать как положено. Особенно с учетом того, что ChaCha8 может быть раза в 4 быстрее "книжной" реализации minstd?

Цитата:

Расхожий миф, о каких-то "проблемах" с такими генераторами

Я знаю по меньшей мере одну работу с описанием подобной проблемы, описанный там эффект прекрасно воспроизводится. Вот эта работа: Ferrenberg, A.M., Landau, D.P. and Wong, Y.J. (1992) Monte Carlo Simulations: Hidden Errors from “Good” Random Number Generators. Physical Review Letters, 69, 3382-3384.
https://doi.org/10.1103/PhysRevLett.69.3382

Цитата:

И очень часто это делается такими авторами намеренно с целью кому-то что-то продать.

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

sergey zhukov в сообщении #1712454 писал(а):

Я думаю, что если ты при решении практической задачи столкнулся с проблемой, связанной с "некачественной" псевдослучайностью (и показал, что это именно так и есть), то, видимо, имеет смысл поднимать вопрос о том, что вот, смотрите, а проблемы-то не выдуманные.

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

[sergey zhukov]

Dig386
Вероятно, вы и есть один из тех, кому выпала задача это изменить.

[Dig386]

sergey zhukov в сообщении #1712721 писал(а):

Dig386
Вероятно, вы и есть один из тех, кому выпала задача это изменить.

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

Кстати, я в реальной жизни сталкивался с ситуацией, в которой криптографический генератор ChaCha20 оказывался самым примитивным решением. Это было связано с ситуациями, в которых мне надо было генерировать выборки в многомерном пространстве в параллельном расчёте, для чего штатный вихрь Мерсенна из C++ уже не годился. В стандартной библиотеке C++ и даже в Boost параллельных ГПСЧ нет, а Philox "завезут" только в C++26. И ChaCha оказался одним из самых простых параллельных генераторов, проще Philox или ThreeFry. На низкую скоростью "тупой" реализации в 0.5 ГиБ/с мне было начхать, т.к. это не было узким местом.

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

[SergeyGubanov]

Стесняюсь спросить. На сколько "плохо" вот это?

Используется синтаксис C

static inline uint32_t random_uint32(uint64_t *seed)
{
        const uint64_t x = (*seed) * 940552494067977757ull + 1061019844797388367ull;
        const uint32_t result = ((uint32_t)(x >> 32));
        (*seed) = x;
        return result;
}

static inline double random_double(uint64_t *seed)
{
        return ((1.0 / 4294967296.0) * random_uint32(seed));
}

[realeugene]

SergeyGubanov в сообщении #1712811 писал(а):

На сколько "плохо" вот это?

Это обычный линейный конгруэнтный генератор. В сгенерированном по нему даблу все разряды мантиссы после 32-го нулевые.

[SergeyGubanov]

А, ну это пусть. Оно потом для float используется. Вопрос про random_uint32().

[Dig386]

SergeyGubanov в сообщении #1712811 писал(а):

Стесняюсь спросить. На сколько "плохо" вот это?

Плохой генератор, проваливает тест Birthday Spacings в 2-8мерных пространствах (некоторые из них - меньше, чем за секунду), BigCrush и PractRand оно не пройдет. Я бы такое использовал только для игрушек. Минимально приличный LCG выглядит вот так (https://cas.ee.ic.ac.uk/people/dt10/res ... wc64x.html):

uint32_t MWC64X(uint64_t *state)
{
    uint32_t c=(*state)>>32, x=(*state)&0xFFFFFFFF;
    *state = x*((uint64_t)4294883355U) + c;
    return x^c;
}

В отличие от Вашего варианта, у него делитель m - не 2^{64}, а простое число a\cdot 2^{32} - 1, и младших бит с низким периодом у него просто нет. Также выход снабжен легким скремблером, что "подчищает" провалы Birthday Spacings в 3D. Если немного поколдовать над множителями и скремблерами с использованием теории чисел и Python, то MWC-генераторы можно использовать даже в тех языках, где беззнаковых целых нет, а целочисленное переполнение недопустимо.

UPD: разумеется, MWC64X нельзя инициализировать как нулем, так и максимально возможным значением. Лучше установить нижнюю половину случайным образом, а в верхнюю половину (32-битную) - 1 записать.

[realeugene]

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

и младших бит с низким периодом у него просто нет.

Период младшего бита $2^{32}$ для многих приложений более чем приемлем.